储水池算法
每天有数十万条日志(数量不固定),需要从中随机抽取2万条。
既然是“随机”,那么就有一个概率问题,比如 100 条日志随机抽 1 条,每条日志被抽中的概率就是 1/100。要随机抽日志,就要保证每一条被抽中的概率一样。现在问题是不知道有每次抽的日志总共有多少条。
最暴力的解法就是先统计一共多少条日志,然后在这个范围内随机产生 2 万个数字,再把这 2 万个数字作为行号,遍历日志取出来。
为了解决在未知行数中随机抽取的问题,就用到储水池算法,算法本身比较简单, 可见维基百科。
一段简单的 demo 代码:
# coding=utf-8 import random k = 5 # 输出数量 n = 0 lines = list() with open('/etc/passwd') as f: for line in f: line = line.strip() if n < k: lines.append(line) else: # 以 r/k 的概率抽取数据 r = random.randint(0, n) if r < k: lines[r] = line n = n + 1 # output result for line in lines: print line