共计 3282 个字符，预计需要花费 9 分钟才能阅读完成。
本文是龚国玮所写，熊哥有所新增批改删减，原文见文末。
我说我为什么抽不到 SSR，原来是加权随机算法在作怪
浏览本文须要做好心理准备，倡议带着深究到底的信心和毅力进行学习！
灵魂拷问
为什么有 50% 的几率取得金币？
为什么有 40% 的几率取得钻石？
为什么只有 9% 的几率取得配备？
为什么才有 1% 的几率取得极品配备？
是兽性的扭曲，还是道德的沦丧，请和我一起走进 今日说法！
介绍
元素被选中的机会并不相等，而是由绝对“权重”（或概率）被选中的，是偏心的，这就是加权随机。
举个栗子，如果当初有一个权重数组 w = {1, 2, 4, 8}，它们代表如下规定。
- $ \frac{1}{(1+2+4+8)} = \frac{1}{15} \approx 6.6$ \% 几率选中第 1 个
- $ \frac{2}{(1+2+4+8)} = \frac{2}{15} \approx 13.3$ \% 几率选中第 2 个
- $ \frac{3}{(1+2+4+8)} = \frac{4}{15} \approx 26.6$ \% 几率选中第 3 个
- $ \frac{1}{(1+2+4+8)} = \frac{8}{15} \approx 53.3$ \% 几率选中第 4 个
一个小小的概率问题，竟然引出了大大的思考。
计划一、笨笨的方法
所以要设计一个加权算法的程序，你会怎么写呢？
第一个办法把权重所在的地位开展，而后从该列表中随机抉择。
假如当初有权重列表 {1, 2, 4, 8}。
那咱们失去的候选列表将是
{0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3}而后通过 rand.Intn()，获取一个随机数，就实现了，代码如下。
func weightedRandomS1(weights []int) int {if len(weights) == 0 {return 0}
var indexList []int
for i, weight := range weights {
cnt := 0
for weight > cnt {indexList = append(indexList, i)
cnt++
}
}
rand.Seed(time.Now().UnixNano())
return indexList[rand.Intn(len(indexList))]
}当权重特地大的时候，这种计划 费时费力，又占空间。先别急往下看，你能想到更好的方法吗？
计划二、略显聪慧
因为总权重为 15（1+2+4+8），咱们能够生成一个 [0,15) 的随机整数，而后依据这个数字返回索引。代码如下。
func weightedRandomS2() int {rand.Seed(time.Now().UnixNano())
r := rand.Intn(15)
if r <= 1 {return 0} else if 1 < r && r <= 3 {return 1} else if 3 < r && r <= 7 {return 2} else {return 3}
}妙不妙！！但你认为这就是效率最高的方法吗？
写那么多 if else 不苦楚吗我的宝贝。
计划三、神之一手
何必将随机数和所有的范畴进行比拟呢？间接遍历随机数减去权重，如果后果小于等于零，不就是咱们要的后果下标吗？
func weightedRandomS3(weights []int) int {rand.Seed(time.Now().UnixNano())
r := rand.Intn(len(weights))
for i, v := range weights {
r = r - v
if r <= 0 {return i}
}
return len(weights) - 1
}这种办法叫放弃长期名单。想不明确就评论问！
计划四、小小优化
对于计划三，怎么无效的缩小遍历次数呢？
当 r 小于等于 0 的速度越快，算法越高效。那咱们就让 r 达到 0 更快。先排序这样就能先减去权重大的，缩小遍历次数。
func weightedRandomS4(weights []int) int {sort.Sort(sort.Reverse(sort.IntSlice(weights)))
....有人就不服了，排序不是更浪费时间？
是的！尽管看起来缩小遍历次数！但排序自身就要遍历就是更浪费时间。。。
然而一次排序，重复应用，还是能提高效率的！
计划五、不堪设想！
有没有方法不必排序，而让原数组有序呢？
有人就说了，你这不是扯么？
如果每次遍历都加上上一个权重，那整个数字就是递增的！
再用二分就能加快速度了，工夫复杂度从 $ O(n) $ 间接变为 $ O(log(n)) $。
func weightedRandomS5(weights []int) int {rand.Seed(time.Now().UnixNano())
sum := 0
var sumWeight []int
for _, v := range weights {
sum += v
sumWeight = append(sumWeight, sum)
}
r := rand.Intn(sum)
idx := sort.SearchInts(sumWeight, r)
return weights[idx]
}
读到这里，对源码没有信念学习的敌人，能够间接撤了。 真正的高阶优化要来了。
计划六、不死不休
到目前的地位，咱们的解决方案曾经足够好了，然而依然有改良的余地。
计划五中，咱们应用了 Go 规范库的二分查找算法 sort.SearchInts()，是封装了通用的 sort.Search() 函数，如下。
sort.Search() 的函数参数须要一个闭包函数，并且这个闭包函数是在 for 循环中应用的，如下。
闭包函数重复调用，在编译期会产生额定的开销。因为会产生更多的跳转，跳转会引起压栈（函数参数都是会压栈的）。
咱们手动提出取函数，就能够缩小编译器的内联（文末会解释）。
func weightedRandomS5(weights []int) int {
...
idx := sort.SearchInts(sumWeight, r)
return weights[idx]
}
func searchInts(a []int, x int) int {i, j := 0, len(a)
for i < j {h := int(uint(i+j) >> 1)
if a[h] < x {i = h + 1} else {j = h}
}
return i
}通过基准测试能够看到吞吐量晋升了 33% 以上。对于大型数据集，劣势越显著。
计划七，“偷鸡”取巧 – 轮盘赌
目前为止咱们所有的计划都有一个共同点 —— 生成一个介于 0 和“权重之和”之间的随机数，并找出它属于哪个“切片”。
还有一种不同的办法。
func weightedRandomS7(weights []float64) int {
var sum float64
var winner int
rand.Seed(time.Now().UnixNano())
for i, v := range weights {
sum += v
f := rand.Float64()
if f*sum < v {winner = i}
}
return winner
}- 从命中的角度去思考。
- 权重越大，命中率天然越大了。
- 既然是随机，屡次随机和单次随机而言都是随机的。
这个算法的一个乏味的个性是你不须要提前晓得权重的数量就能够应用它。所以说，它或者能够用于某种流。
只管这种计划很酷，但它比其余计划慢得多。绝对于计划一，它也快了 25%。
小结
- 下标间接开展到列表里，随机长度取值。
if else取值。- 遍历随机数减去权重，后果小于等于零时。
- 先排序，再用办法三。
- 免排序，间接加和，再二分。
- 优化源码中的二分法。
- 轮盘赌算法，每次都去赌。
内联：编译器的一个名词。咱们的代码最终都是通过编译系统转换成可执行二进制文件。汇编阶段读取的是词法、语法单元输入的后果。而内联是编译器对词法、语法分析器对源代码做出的剖析，而后产生二进制代码这个过程叫内联。
源代码
https://github.com/guowei-gong/weighted-random
原文：加权随机设计与实现
一起提高
你好，我是小熊，是一个爱技术然而更爱钱的程序员。上进且佛系自律的人。喜爱发小机密 / 臭屁又爱夸耀。
奋斗的大学，激情的当初。赚了钱买了房，写了书出了名。当过面试官，带过师傅搬过转。
大厂外来务工人员。是我，我是小熊，是不一样的烟火欢送围观。
我的博客 机智的程序员小熊 欢送珍藏
