储水池算法

每天有数十万条日志(数量不固定),需要从中随机抽取2万条。

既然是“随机”,那么就有一个概率问题,比如100条日志随机抽1条,每条日志被抽中的概率就是1/10。要随机抽日志,就要保证每一条被抽中的概率一样。现在问题是不知道有每次抽的日志总共有多少条。

最暴力的解法就是先统计一共多少条日志,然后在这个范围内随机产生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