写在前面
今天下午在阅读负载均衡文章的时候，文章中提到随机负载均衡，需要生成随机序列。根据学习心得总结一下，希望对大家有所帮助。
go语言生成随机数的坑
文中提到洗牌算法生成随机数。
var endpoints = []string {
"100.69.62.1:3232",
"100.69.62.32:3232",
"100.69.62.42:3232",
"100.69.62.81:3232",
"100.69.62.11:3232",
"100.69.62.113:3232",
"100.69.62.101:3232",
}
// 重点在这个 shuffle
func shuffle(slice []int) {
for i := 0; i <len(slice); i++ {
a := rand.Intn(len(slice))
b := rand.Intn(len(slice))
slice[a], slice[b] = slice[b], slice[a]
}
}
func request(params map[string]interface{}) error {
var indexes = []int {0,1,2,3,4,5,6}
var err error
shuffle(indexes)
maxRetryTimes := 3
idx := 0
for i := 0; i < maxRetryTimes; i++ {
err = apiRequest(params, endpoints[indexes[idx]])
if err == nil {
break
}
idx++
}
if err != nil {
// logging
return err
}
return nil
}这个算法有2个问题：
- rand没有给随机种子，生成的数字是一个固定的序列。这是go语言的rand包一个特性，需要尤其注意，每次开始生成的时候最好给一个随机种子。
- shuffle算法不够随机。我们可以用概率知识来简单证明一下。假设每次挑选都是真随机，我们假设第一个位置的节点在
len(slice)次交换中都不被选中的概率是((6/7)*(6/7))^7≈0.1155。而分布均匀的情况下，我们肯定希望被第一个元素在任意位置上分布的概率均等，所以其被随机选到的概率应该约等于1/7≈0.1428。所以第一个初始位置被选中的概率变小了。
洗牌算法
其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：
1. 初始化原始数组和新数组，原始数组长度为n(已知)；
2. 从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）；
3. 从剩下的k个数中把第p个数取出；
4. 重复步骤2和3直到数字全部取完；
5. 从步骤3取出的数字序列便是一个打乱了的数列。
下面证明其随机性，即每个元素被放置在新数组中的第i个位置是1/n（假设数组大小是n）。
证明：一个元素m被放入第i个位置的概率P = 前i-1个位置选择元素时没有选中m的概率 * 第i个位置选中m的概率，即
func shuffle1(data []int64) []int64 {
if len(data) < 2 {
return data
}
rand.Seed(time.Now().Unix())
count := len(data)
for i := count - 1; i >= 0; i-- {
idx := rand.Intn(i + 1)
data[i], data[idx] = data[idx], data[i]
}
return data
}时间复杂度是O(n),空间复杂度是O(1)
Go内置洗牌算法
go语言rand包已经内置了一个精简的洗牌算法
// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
// in the half-open interval [0,n).
func (r *Rand) Perm(n int) []int {
m := make([]int, n)
// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
// A change to remove this useless iteration is to assign 1 to i in the init
// statement. But Perm also effects r. Making this change will affect
// the final state of r. So this change can't be made for compatibility
// reasons for Go 1.
for i := 0; i < n; i++ {
j := r.Intn(i + 1)
m[i] = m[j]
m[j] = i
}
return m
}其中，有一个地方有点迷惑，m[j]=i这一句为什么把i赋值给m[j]?
其实，这个算法等同于下面这段代码
// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers
// in the half-open interval [0,n).
func (r *Rand) Perm(n int) []int {
m := make([]int, n)
for i :=0; i < n; i++ {
m[i] = i
}
// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
// A change to remove this useless iteration is to assign 1 to i in the init
// statement. But Perm also effects r. Making this change will affect
// the final state of r. So this change can't be made for compatibility
// reasons for Go 1.
for i := 0; i < n; i++ {
j := r.Intn(i + 1)
m[i] = m[j]
m[j] = m[i]
}
return m
}这样看就容易懂了，Perm的for循环，是把数组m的前[0:i]看成是一个有序数组，每次循环都是把第i位将前面的[i:i]位中的某一位交换。而第m[i]位的值是i，只是它在初始化m的时候没有初始化m的值（它的值是{0,1,2,…,n-1}），而是在交换的时候直接用i进行交换，这里用法挺秒的。这种思想让我想到了经典限流算法中的令牌桶，它也不是提前生成好令牌，而是在获取令牌的时候根据时间计算当前还剩多少令牌，算法非常巧妙，感兴趣的同学可以去研究一下。
go里面还实现了一版交换洗牌算法
// Shuffle pseudo-randomizes the order of elements.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func (r *Rand) Shuffle(n int, swap func(i, j int)) {
if n < 0 {
panic("invalid argument to Shuffle")
}
// Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
// Shuffle really ought not be called with n that doesn't fit in 32 bits.
// Not only will it take a very long time, but with 2³¹! possible permutations,
// there's no way that any PRNG can have a big enough internal state to
// generate even a minuscule percentage of the possible permutations.
// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
i := n - 1
for ; i > 1<<31-1-1; i-- {
j := int(r.Int63n(int64(i + 1)))
swap(i, j)
}
for ; i > 0; i-- {
j := int(r.int31n(int32(i + 1)))
swap(i, j)
}
}
