沭阳建设网站,企业应该如何进行网站建设,门户网站开发流程视频,WordPress签到打卡本文是龚国玮所写#xff0c;熊哥有所新增修改删减#xff0c;原文见文末。
我说我为什么抽不到SSR#xff0c;原来是加权随机算法在作祟 阅读本文需要做好心理准备#xff0c;建议带着深究到底的决心和毅力进行学习#xff01; 灵魂拷问
为什么有 50% 的几率获得金币熊哥有所新增修改删减原文见文末。
我说我为什么抽不到SSR原来是加权随机算法在作祟 阅读本文需要做好心理准备建议带着深究到底的决心和毅力进行学习 灵魂拷问
为什么有 50% 的几率获得金币
为什么有 40% 的几率获得钻石
为什么只有 9% 的几率获得装备
为什么才有 1% 的几率获得极品装备
是人性的扭曲还是道德的沦丧请和我一起走进今日说法
介绍
元素被选中的机会并不相等而是由相对“权重”或概率被选中的是偏心的这就是加权随机。
举个栗子假如现在有一个权重数组 w {1, 2, 4, 8}它们代表如下规则。
$ \frac{1}{(1248)} \frac{1}{15} \approx 6.6$ % 几率选中第1个 $ \frac{2}{(1248)} \frac{2}{15} \approx 13.3$ % 几率选中第2个 $ \frac{3}{(1248)} \frac{4}{15} \approx 26.6$ % 几率选中第3个 $ \frac{1}{(1248)} \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 []intfor i, weight : range weights {cnt : 0for weight cnt {indexList append(indexList, i)cnt}}rand.Seed(time.Now().UnixNano())return indexList[rand.Intn(len(indexList))]
}
当权重特别大的时候这种方案费时费力又占空间。先别急往下看你能想到更好的办法吗
方案二、略显聪明
由于总权重为 151248我们可以生成一个 [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 - vif 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 : 0var sumWeight []intfor _, v : range weights {sum vsumWeight 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(ij) 1)if a[h] x {i h 1} else {j h}}return i
}
通过基准测试可以看到吞吐量提升了 33% 以上。对于大型数据集优势越明显。 方案七“偷鸡”取巧--轮盘赌
目前为止我们所有的方案都有一个共同点 —— 生成一个介于 0 和“权重之和”之间的随机数并找出它属于哪个“切片”。
还有一种不同的方法。
func weightedRandomS7(weights []float64) int {var sum float64var winner intrand.Seed(time.Now().UnixNano())for i, v : range weights {sum vf : rand.Float64()if f*sum v {winner i}}return winner
}
从命中的角度去考虑。权重越大命中率自然越大了。既然是随机多次随机和单次随机而言都是随机的。
这个算法的一个有趣的特性是你不需要提前知道权重的数量就可以使用它。所以说它或许可以用于某种流。
尽管这种方案很酷但它比其他方案慢得多。相对于方案一它也快了 25% 。
小结
下标直接展开到列表里随机长度取值。if else 取值。遍历随机数减去权重结果小于等于零时。先排序再用方法三。免排序直接加和再二分。优化源码中的二分法。轮盘赌算法每次都去赌。
内联编译器的一个名词。我们的代码最终都是经过编译系统转换成可执行二进制文件。汇编阶段读取的是词法、语法单元输出的结果。而内联是编译器对词法、语法分析器对源代码做出的分析然后产生二进制代码这个过程叫内联。
源代码
https://github.com/guowei-gong/weighted-random
原文加权随机设计与实现
一起进步
你好我是小熊是一个爱技术但是更爱钱的程序员。上进且佛系自律的人。喜欢发小秘密/臭屁又爱炫耀。
奋斗的大学激情的现在。赚了钱买了房写了书出了名。当过面试官带过徒弟搬过转。
大厂外来务工人员。是我我是小熊是不一样的烟火欢迎围观。
我的博客 机智的程序员小熊 欢迎收藏
