十月份的时候写了一篇 面试题, 随机抽样问题及扩展, 当时这个 blog 没整好, 发在了好几个地方
- http://www.yewen.us/blog/2011/10/random-select-problem/
- http://hi.baidu.com/whusnoopy/blog/item/4f54b3de5d708344cdbf1a08.html
- http://blog.renren.com/blog/bp/Q7fr2sueah
前几天跟 Lee.Mars 聊, 又把这堆问题解答了一遍, 并指出其中一个问题的 bug.
原始版, 数据流 n 选 1. 构建一个可容纳一个数的 buffer, 数据流中第 i 个数过来时做一次 [0, 1] 的 random, 如果小于 1/i, 则更新 buffer. (证明过程略, 很简单的)
buf = 0
cnt = 0
for i in sys.stdin:
cnt += 1
if random.random() < 1.0/cnt:
buf = int(i)
print buf
加强版, 数据流 n 选 k. 同上, 构建的 buffer 大小变为 k, 每次 rand 小于 k/i 时, 将 rand*i 对应的 buffer 更新
k = 3
buf = []
cnt = 0
for i in sys.stdin:
cnt += 1
rd = int(random.random()*cnt)
if rd < k:
if cnt <= k:
buf.append(int(i))
buf[cnt-1] = buf[rd]
buf[rd] = int(i)
print buf
带权版, 带权数据流 n 选 1. 同原始版, 只是对权重为 w[i] 的第 i 个数, rand 时判断是否小于 w[i]/SUM(w)
sum = 0
buf = 0
cnt = 0
for i in sys.stdin:
cnt += 1
sum += int(i)
if random.random() < float(i)/sum:
buf = int(i)
print buf
带权选 k 版. 这个有 bug, 无解, 因为无法保证最后选出来的 k 个数, 其 SUM(w[k1..kk])/sum(w[1..n]) = k/n, 那个概率无法算
分布式版, m 个序列最后选 k. 每个序列先按加强版选 k 个, 然后将 m*k 个数放到一起, 做带权版的 n 选 k. 由于带权选 k 版有 bug, 所以这里会有一定误差. 而实际上一般的分布式框架是可以保证每个序列数据规模分布都比较均匀, 所以最后的 m*k 个数可以当无权版直接选 k, 这样的误差在工业应用是可以接受的
注: 从 n 选 k 那个就可以很容易看出来, 这其实就是那个把一个序列打乱成随机状态的算法简化, n 选 1 只是 n 选 k 的一个特例