错误示范😈 falsa demonstratio

[liyiheng]

错误示范😈 falsa demonstratio

[liyiheng]

递归，斐波那契，贼“快”： O(2^n)

func Fib(i uint) uint {
        if i < 2 {
                return 1
        }
        return Fib(i-1) + Fib(i-2)
}

同理，这样求质数一样贼快，
另一种方式： O(n)

func Fib2(i uint) uint {
        tmp := make([]uint, i+1)
        for j := uint(0); j <= i; j++ {
                if j < 2 {
                        tmp[j] = 1
                } else {
                        tmp[j] = tmp[j-1] + tmp[j-2]
                }
        }
        return tmp[i]
}

靠谱些，不过太占内存
正确姿势：

func Fib3(i uint) uint {
	if i < 2 {
		return 1
	}
	var prePre, pre uint = 1, 1
	for j := uint(2); j <= i; j++ {
		tmp := pre + prePre
		prePre = pre
		pre = tmp
	}
	return pre
}

TODO: 矩阵

[liyiheng]

幂运算，仅演示uint情况，O(n)

func Pow(x, y uint) uint {
	result := uint(1)
	for i := uint(0); i < y; i++ {
		result *= x
	}
	return result
}

emmmmm，很直观，但乘操作太多
另一种方式：O(log n)

func myPow(x float64, n int) float64 {
        if x == 0 {
                return 0
        }
        if n == 0 {
                return 1
        }
        if n == 2 {
                return x * x
        } 
        if n == 1 {
                return x
        }
        if n < 0 {
                return 1 / myPow(x, -n)

        }
        if n%2 == 1 {
                return myPow(myPow(x, n/2), 2) * x
        }
        return myPow(myPow(x, n/2), 2)
}

TODO: 最短加法链

[liyiheng]

勇者的游戏：

#  [ $((${RANDOM}%6)) -eq 0 ] && rm -rf / || echo 'winner winner, chicken dinner'

[liyiheng]

golang中切片：

originSlice := []int{0, 1, 2, 3, 4, 5}
s := originSlice[:1]
_ = append(s, 666)
fmt.Println(originSlice) // [0,666,2,3,4,5]

不改变originSlice的姿势是，
s := originSlice[:1:1]
控制新切片的容量，这时再进行append操作就会开辟新缓冲区从而不影响原始切片。
详见切片的底层实现

[liyiheng]

golang中并发安全的map

golang中的map不支持并发读写，早期版本并发读写可能数据会脏，但新版中会直接panic。
golang1.9标准库中引入了sync.Map, 在1.9之前经常这么写：

type SafeMap struct {
	data map[int]string
	sync.Mutex
}

嗯，很安全，很暴力，稍微高明点的做法是把sync.Mutex换成sync.RWMutex
尽管1.9引入了sync.Map，似乎并不完美。由于没有泛型，用起来略不爽。
性能也没有期望中强。
有些时候，还是需要根据具体场景进行简单的封装：
把key均匀分布到多个map，每个map对应一个读写锁，这样就大大减少了对锁的竞争。
举个栗子：

type CMap struct {
	slotCnt int64
	buckets []map[int64]interface{}
	locks   []*sync.RWMutex
}

func (m *CMap) Init(cnt uint8) {
	if cnt == 0 {
		cnt = 1
	}
	m.slotCnt = int64(cnt)
	// 初始化m.buckets
	// 初始化m.locks  
}

func (m *CMap) Set(key int64, v interface{}) {
	if m.slotCnt == 0 {
		m.Init(1)
	}
	slot := key % m.slotCnt
	l := m.locks[slot]
	l.Lock()
	m.buckets[slot][key] = v
	l.Unlock()
}

这里的key类型是int64，简单地通过取余数确定在哪个map，只要key大概是连续递增的，就可以保证均匀分布。
类似的，有concurrent-map，它是用string作为key，用fnv32来确定在哪个桶