储水池算法

每天有数十万条日志产生，条数不固定，需要从中随机抽取 2 万条。

“随机”就代表和概率有关，100 条日志随机抽 1 条，每条被抽中的概率是 1/100。现在，不知道每次抽取时，总共有多少条日志，如何去保证每条被抽中的概率一样。

简单点，可以先计算出一共多少条日志，再在这个范围内随机产生 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