博文
根据值的大小随机取数组元素的方法
|||
前两天需要做一个程序，从一个数组中，按照正比于元素数值大小的概率随机选取数组元素。
以前处理过值为整数的情形（模拟BA模型中的度优先连接），这种情况解决起来比较简单，大致思路为：遍历数组，对每一个元素i（具有元素值a），将a个i添加到一个新数组中。假设最终得到的新数组长度为M，则生成0到M-1之间均匀分布的随机数j（高级语言里都会提供生成0-1之间均匀分布随机数的算法，放大M-1倍后取整就可以了）。则Mj即为所求的数组元素索引。
不过现在处理的数值是小数，而且最大值和最小值会相差几个数量级。如果按最小值取整，系统开销受不了（例如，最小值是0.001，最大值是1000，如果按最小值取整，最大值需要离散为1000000个数组元素）。所以必须想别的办法。
上网搜索一下关于这方面的代码，找到两个：
在《如何根据选择概率进行选择》（见http://hi.baidu.com/milkyadel/blog/item/33d60f54fd56a45d574e0021.html）这篇blog里，作者的做法是：
1、将nodeList数组按照value从大到小排序：（value大的node的位置值小）
2、生成一个指数分布的随机数（取小的概率大，取大的概率很小），取这个随机数的整数部分
3、截断处理，太大的就不要了（大于等于SIZE的），就是你选择的node的位置，返回它的num即可。
算法虽然简单，而且值越大的元素被选择的概率也越大，但很明显这个概率不是正比于元素值的，与要求不符合。
另一篇文章：《根据概率取随机数的php算法》（见http://hi.baidu.com/horseluke/blog/item/d4a1be268a7fec1c8a82a1fc.html），采用了以下思路：
“把1——100看成是一条线段。然后概率就是用于切割这条线条的，我们要做的其实只需要随机产生一个数，然后看这个数对应于哪一条分线条就 OK了。这样，数组不需太大，而且还能得到同样的效果。
举个例子，A字母为30%概率，B字母为70%概率。那么可以把这条0——100的线段分割为2段。一段为0——30，为A字母；其余的分属B字段。好了，程序现在随机抽取了30这个数，那么很明显，结果就是A了。
|-----------|-----------------------|
0 30 100
………………
开始是从1,1000这个概率范围内筛选第一个数是否在他的出现概率范围之内，如果不在，则将概率空间，也就是k的值减去刚刚的那个数字的概率空间，在本例当中就是减去100，也就是说第二个数是在1，900这个范围内筛选的。我想应该很容易理解，这样筛选到最终，总会有一个数满足要求（比如说前三个都不幸成为了非Luck Num，那么k已经-100-200-300=400了，那么最后一个数无论如何也会满足要求的。相当于拿东西，第一个不是，第二个不是，第三个还不是，那最后一个一定是。
这个算法的优点是，对于没有概率重叠的数字进行筛选，最多只需要遍览一次数组就足够了。程序简单，效率高………………
”
上述思路是对的，但作者给出的代码中，要求元素值必须为大于1的整数，实际上是没必要的。只要把数组元素值求和（记为S），那么生成一个0-S之间的均匀分布随机数P，然后从头到尾遍历数组，并在每步迭代中用P与数组当前位置i的累加值Si进行比较，就可以找到所需的数组元素。
下面是我的算法（用Python实现）：
#根据值的大小随机选择函数，seq是一个数组，值为正实数。返回数组元素索引
def RanChoice(seq):
ran = random.random()*sum(seq)
sumtmp = 0
N = seq.__len__()
for i in xrange(N):
sumtmp += seq[i]
if sumtmp > ran:
a = i
return a
return -1
对上述算法的测试，被测试数组test = [ 6.1 , 2.2 , 1.7 ]，运行10000次后统计各元素出现频率如下：
6.1 - 0.6174
2.2 - 0.2138
1.7 - 0.1688
结果看起来是正确的，速度也不慢。当然肯定还有更好的办法，不过暂时能达到我的要求了，够用就好。
https://blog.sciencenet.cn/blog-404069-335920.html
上一篇：推荐一本好书：公共交通规划与运营——理论、建模及应用
下一篇：复杂网络分析库NetworkX学习笔记（1）：入门
以前处理过值为整数的情形（模拟BA模型中的度优先连接），这种情况解决起来比较简单，大致思路为：遍历数组，对每一个元素i（具有元素值a），将a个i添加到一个新数组中。假设最终得到的新数组长度为M，则生成0到M-1之间均匀分布的随机数j（高级语言里都会提供生成0-1之间均匀分布随机数的算法，放大M-1倍后取整就可以了）。则Mj即为所求的数组元素索引。
不过现在处理的数值是小数，而且最大值和最小值会相差几个数量级。如果按最小值取整，系统开销受不了（例如，最小值是0.001，最大值是1000，如果按最小值取整，最大值需要离散为1000000个数组元素）。所以必须想别的办法。
上网搜索一下关于这方面的代码，找到两个：
在《如何根据选择概率进行选择》（见http://hi.baidu.com/milkyadel/blog/item/33d60f54fd56a45d574e0021.html）这篇blog里，作者的做法是：
1、将nodeList数组按照value从大到小排序：（value大的node的位置值小）
2、生成一个指数分布的随机数（取小的概率大，取大的概率很小），取这个随机数的整数部分
3、截断处理，太大的就不要了（大于等于SIZE的），就是你选择的node的位置，返回它的num即可。
算法虽然简单，而且值越大的元素被选择的概率也越大，但很明显这个概率不是正比于元素值的，与要求不符合。
另一篇文章：《根据概率取随机数的php算法》（见http://hi.baidu.com/horseluke/blog/item/d4a1be268a7fec1c8a82a1fc.html），采用了以下思路：
“把1——100看成是一条线段。然后概率就是用于切割这条线条的，我们要做的其实只需要随机产生一个数，然后看这个数对应于哪一条分线条就 OK了。这样，数组不需太大，而且还能得到同样的效果。
举个例子，A字母为30%概率，B字母为70%概率。那么可以把这条0——100的线段分割为2段。一段为0——30，为A字母；其余的分属B字段。好了，程序现在随机抽取了30这个数，那么很明显，结果就是A了。
|-----------|-----------------------|
0 30 100
………………
开始是从1,1000这个概率范围内筛选第一个数是否在他的出现概率范围之内，如果不在，则将概率空间，也就是k的值减去刚刚的那个数字的概率空间，在本例当中就是减去100，也就是说第二个数是在1，900这个范围内筛选的。我想应该很容易理解，这样筛选到最终，总会有一个数满足要求（比如说前三个都不幸成为了非Luck Num，那么k已经-100-200-300=400了，那么最后一个数无论如何也会满足要求的。相当于拿东西，第一个不是，第二个不是，第三个还不是，那最后一个一定是。
这个算法的优点是，对于没有概率重叠的数字进行筛选，最多只需要遍览一次数组就足够了。程序简单，效率高………………
”
上述思路是对的，但作者给出的代码中，要求元素值必须为大于1的整数，实际上是没必要的。只要把数组元素值求和（记为S），那么生成一个0-S之间的均匀分布随机数P，然后从头到尾遍历数组，并在每步迭代中用P与数组当前位置i的累加值Si进行比较，就可以找到所需的数组元素。
下面是我的算法（用Python实现）：
#根据值的大小随机选择函数，seq是一个数组，值为正实数。返回数组元素索引
def RanChoice(seq):
ran = random.random()*sum(seq)
sumtmp = 0
N = seq.__len__()
for i in xrange(N):
sumtmp += seq[i]
if sumtmp > ran:
a = i
return a
return -1
对上述算法的测试，被测试数组test = [ 6.1 , 2.2 , 1.7 ]，运行10000次后统计各元素出现频率如下：
6.1 - 0.6174
2.2 - 0.2138
1.7 - 0.1688
结果看起来是正确的，速度也不慢。当然肯定还有更好的办法，不过暂时能达到我的要求了，够用就好。
https://blog.sciencenet.cn/blog-404069-335920.html
上一篇：推荐一本好书：公共交通规划与运营——理论、建模及应用
下一篇：复杂网络分析库NetworkX学习笔记（1）：入门
