储水池算法

每天有数十万条日志（数量不固定），需要从中随机抽取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