单次遍历,带权随机选取问题(二)
还是同样的问题:有一组数量未知的数据,每个元素有非负权重。要求只遍历一次,随机选取其中的一个元素,任何一个元素被选到的概率与其权重成正比。
在 前一篇 文章中介绍了概率分布的理论值,并用比较简洁高效的函数实现了选取一个元素的方法。现在来看一个神奇的算法,以及相关的证明和实现。
算法很简单:对于任意的 i(1 <= i <= n),按照如下方法给第 i 个元素分配一个键值 key(其中 rᵢ 是一个 0 到 1 之间等概率分布的随机数):
之后,如果要随机选取一个元素,就去 key 最大的那个;如果要选取 m 个元素,就取 key 最大的 m 个。
真不知道是怎么想出来的这样的方法,不过还是先来关注一下证明的过程。
m = 1 证明
对于 m = 1 的证明过程会介绍得详细些,主要是怕我自己过几天就忘记了。概率达人可以直接秒杀之。
m = 1 时,第 i 个元素被选取到的概率,就等于它所对应的键值 key(i) 是最大值的概率,即:
把 key(i) 的计算公式代入,但要注意公式中的 rᵢ 并不是一个固定的数值,而是随机变量。不考虑计算机数值表示的精度,可以假设 rᵢ 是一个在 0 到 1 之间的连续均匀概率分布,因此如果要计算 key(i) 是最大的概率,必须要对 rᵢ 所有的可能值进行概率累加,也就是积分。于是上面的概率表达式就被写成:
再看式子中的 ,它表示每一个 j 都要满足后面的条件,而各个 j 之间相互独立,因此可以写成概率乘积,于是得到:
对于给定的 j,,另外 rⱼ 也是个均匀概率分布,将概率密度函数代入可以得到:
因此,上面的概率算式就变成(其中 w 就是前一篇文章中提到的所有元素的权重之和):
最后的结果跟 前一篇 文章中的理论值相等,证明完毕。
m >= 1 证明
当 m 取任意值时,概率公式变得非常复杂,在前一篇文章中使用了第 i 个元素不被选到的概率来简化表达式。现在的证明也从同样的角度进行。
第 i 个元素不被选到的概率,显然等于这 n 个元素中,至少存在 m 个元素的键值大于 key(i),与之前的讨论一样,不妨设这 m 个元素的下标(按键值从大到小)依次为 j₁, j₂, ..., jₘ,,满足 。注意 jₖ 和 tₖ 的取值范围,为了简单起见,下面的式子中就不再重复了。
为了能够进一步求解,必须把这个连等式拆开。这里要非常小心,各个 jₖ 并不是相互独立的,比如当 j₁ 改变的时候,j₂ 的取值范围也会随之变化,依此类推。拆开之后的式子如下:
看起来还是相当恐怖的,一层套一层。注意等式右边已经没有显式地关于 i 的信息了,这些信息被隐含在 jₖ 和 tₖ 的取值范围中,切记。对每个 jₖ,把 key(jₖ) 的式子代进去,转换成积分;同时把 转换为 。这些在 m = 1 的证明中都提到过了。新出现的是 ,这个显然适用概率加法,因为 jₖ 取不同的值对应于不同的互斥方案。经过这些变换得到:
其中的积分式在之前已经见过了,其运算过程如下(注意 tₖ 的取值范围):
最终,概率计算式子变成:
与 前一篇 文章中的理论值完全一样。
呼,可怕的推导过程。
程序实现
虽然证明过程异常恐怖,但实现起来却很简单。实际运算中,只要维持一个大小为 m 的最小堆(没错,是最小堆)来保存当前已知的最大的 m 个键值,每拿到一个新的元素,算出对应的键值,如果它比堆中的最小值大,就可以放入堆中替换掉最小值。Python 实现函数如下:
| |
每次拿到一个新的元素,通过 key = rand.random() ** (1.0 / weight) 产生一个与其权重有关的随机键值 key。当元素个数小于 m 时,直接将新的元素放入堆空间中(但并不建堆),这样只用 O(1) 时间;当遇到第 m 个元素后,堆空间放满了,这时候进行建堆操作(heapify(heap)),需要 O(m) 时间;之后每拿到一个新的元素,用 O(1) 时间从堆顶拿出最小值与新元素的键值比较,如果后者更大就用后者替换掉堆顶元素,对堆进行必要的操作(O(log m) 时间)以保持其结构(heapreplace(heap, (key, index)))。
关于 Python 中的堆可以参考:http://docs.python.org/library/heapq.html。
总体来看,整段程序用时 O(n * log m),占用 O(m) 辅助空间。这样的处理比较适用于 m << n 的情况。当 m 与 n 接近时,可以用 n 个辅助空间存储所有元素的键值,当遍历结束后用 O(n) 时间对这 n 个元素执行快速选择算法,选出 m 个最大的元素即可,耗时 O(n),辅助空间 O(n)。
用同样一组具有等差分布权重的元素调用 WeightedRandomSample 十万次,得到如下的概率分布,与理论分布非常接近。
查看源代码
{
"legend": {
"width": "80%"
},
"series": [
{
"data": [
0.01824,
0.0371,
0.05426,
0.0723,
0.09161,
0.10988,
0.12501,
0.14523,
0.16448,
0.18189
],
"name": "m=1",
"type": "line"
},
{
"data": [
0.03979,
0.07617,
0.11498,
0.15227,
0.18612,
0.22121,
0.25497,
0.28584,
0.32032,
0.34833
],
"name": "m=2",
"type": "line"
},
{
"data": [
0.06173,
0.12283,
0.17995,
0.23588,
0.28565,
0.33511,
0.38292,
0.4259,
0.46621,
0.50382
],
"name": "m=3",
"type": "line"
},
{
"data": [
0.08874,
0.17467,
0.25423,
0.32381,
0.39314,
0.45378,
0.5103,
0.55865,
0.60438,
0.6383
],
"name": "m=4",
"type": "line"
},
{
"data": [
0.1239,
0.23698,
0.33544,
0.42587,
0.50627,
0.57379,
0.63485,
0.68303,
0.72241,
0.75746
],
"name": "m=5",
"type": "line"
},
{
"data": [
0.16634,
0.31401,
0.43789,
0.54221,
0.62332,
0.6963,
0.74587,
0.79285,
0.82668,
0.85453
],
"name": "m=6",
"type": "line"
},
{
"data": [
0.22243,
0.40975,
0.56211,
0.67063,
0.74944,
0.80965,
0.85354,
0.88449,
0.91023,
0.92773
],
"name": "m=7",
"type": "line"
},
{
"data": [
0.31252,
0.54828,
0.71493,
0.8095,
0.87294,
0.91133,
0.93608,
0.95444,
0.96568,
0.9743
],
"name": "m=8",
"type": "line"
},
{
"data": [
0.48359,
0.78327,
0.89211,
0.93922,
0.96197,
0.97692,
0.98513,
0.98987,
0.99282,
0.9951
],
"name": "m=9",
"type": "line"
},
{
"data": [
1,
1,
1,
1,
1,
1,
1,
1,
1,
1
],
"name": "m=10",
"type": "line"
}
],
"title": {
"text": "WeightedRandomSample 函数随机选取"
},
"tooltip": {
"trigger": "axis"
},
"xAxis": {
"boundaryGap": false,
"data": [
"i=1",
"i=2",
"i=3",
"i=4",
"i=5",
"i=6",
"i=7",
"i=8",
"i=9",
"i=10"
],
"type": "category"
},
"yAxis": {
"max": 1,
"min": 0,
"type": "value"
}
}交互式图表需要 JavaScript。您仍可查看或下载其 JSON 源代码。
评论需要 JavaScript。