BBruceyuan

Python实现蓄水池算法

蓄水池算法

蓄水池算法采样算法难的点不在于怎么实现蓄水池算法,难的点在于证明每一个点都能被同等的概率抽取。

蓄水池算法证明最好的两个教程是:

  1. https://www.cnblogs.com/snowInPluto/p/5996269.html
  2. https://www.jianshu.com/p/7a9ea6ece2af

其他的感觉说的不是很清楚。

蓄水池算法的主要逻辑:
image.png

蓄水池算法的Pthon实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random

def reservior_sampling(n, k):
"""
表示有 n 个数,随机采样 k 个
"""
nums = [i for i in range(1, n + 1)]

res = []
for i in range(k):
# 前K个数字可以直接填充
res.append(nums[i])

for i in range(k, len(nums)):
# 假设 i == k (也是说这是 第 k + 1个元素), 那么 该数字有 k / (k + 1) 的概率被选中去去换
replace_idx = random.randint(0, i)
if replace_idx < k:
res[replace_idx] = nums[i]
return res

pool = reservior_sampling(100, 10)
print(pool)
# [78, 52, 41, 84, 66, 43, 25, 71, 45, 24]

专题:

本文发表于 2020-08-15,最后修改于 2020-10-18。

本站永久域名bbruceyuan.github.io,也可搜索「 BBruceyuan 」找到我。

期待关注我的 知乎专栏微博 ,查看最近的文章和动态。


上一篇 « 简单方法增加Query召回的多样性 下一篇 » 我为什么没有满意的offer?

赞赏支持

谢谢支持~

i ali

支付宝

i wechat

微信

推荐阅读

Big Image