关于随机数权重的交流
本帖最后由 wang1cole 于 2013-04-11 17:00:16 编辑 我想问下有一个数组，这些数组中的值都有自己的权重，怎样设计才能高效的优先取出权重高的数？？数据量大概400条左右。
我的想法是先random这些数组的索引M条，然后将这些索引乘上自己的权重得到一个值，再在这些值中由大到小排列，取出前N条值对应索引中的数据。
想法貌似效率低下没什么含量。问下有没有了解这方面的给指点下，或者给些资料我拓展下思路？？
谢谢了！ random 算法 权重
[解决办法]
轮盘赌,俄罗斯轮盘
[解决办法]
把数组转换为一个区间，假设数组只有两个元素
比如假设 a[0] 权重为 0.5 , a[1] 权重为 2， 那从 [0,0.5) 属于a[0], [0.5,2.5) 属于a[1]
然后就在[0,2.5)区间随机， 随机数出来后， 二分找到它是对一哪个元素。
这个是通用算法， 如果你的权重精度要求不高的话， 说不定直接可以把400个数组转换为另一个长一点的数组， 比如上面例子， 我可以建另外一个数组, b[0]=0, b[1]=b[2]=b[3]=b[4]=1, 这样在b数组里随机N次， 直接读到a中的索引了。
[解决办法]
提供一个思路, 首先假设数组中的权重都是整数. (如果是浮点, 思路一样)
假设
数组为: a b c d
权重为: 88 23 10 7
按照权重排序后为:
数组为: d c b a
权重为: 7 10 23 88
权重和为128, 那么在1~128之间随机一个数字, 这个数字落在如下范围就选择对于的元素.
1~7: d
8~17: c
18~40: b
41~128: a
具体做法就是
预处理:
1. 对数组按照权重排序. (堆排序或者快排, 效率: N*LogN)
2. 遍历数组, 建立Map, key为权重范围, 值为元素的index. 同时统计权重总和. (效率: N*LogN, 空间: O(N) )
每次使用:
3. 随机1到权重总和的数字, 在Map中搜索, 根据命中的元素的index选择随机到的元素即可. (效率: LogN, 400个元素的情况下, 平均比较2.6次)
如果是浮点的话, 需要转化为正数. 假设浮点数进度为6位, 那么所有权重乘以(10^6)取整即可. 如果存在溢出可能, 用long long存储权重值. 空间占用稍微大一些了.
[解决办法]
