Map-Reduce实现中的一个特殊示例方法

Question

我有一个包含 4*10^8(大致(记录的表，我想得到一个 4*10^6(确切(的样本。

但是我获取样本的方式有些特别：

1. 我从 1*4^8 条记录中随机选择 8 条记录(每条记录都有相同的概率被选择(。
2. 重复步骤1 4*10^6次(无论是否多次选择一条记录(。

我想出了一个解决这个问题的方法：

1. 生成一个表A(num int)，表A的每条记录中只有一个数字，它是从 1 到 n 的随机整数(n 是我原始表的大小，如上所述大约 4*10^8(。
2. 将表A作为资源文件加载到每个映射中，如果现在正在决定的记录的序号在表 A 中，则输出此记录，否则丢弃它。

我认为我的方法不是很好，因为如果我想从原始表中采样更多记录，表A将变得非常大并且无法加载为资源文件。

那么，任何人都可以给出一个优雅的算法吗？

Answer 1

我不确定"优雅"是什么意思，但也许您对类似于水库采样的东西感兴趣。设 k 为样本的大小，并使用 null 初始化 k 元素数组。我们正在采样的元素一个接一个地到达。当第 jth(从 1 开始计数(元素到达时，我们遍历数组，对于每个单元格，以概率 1/j 独立地将其内容替换为当前元素。

天真地，运行时间非常糟糕 - 从n中采样k个元素，更换成本O(k n(。但是，写入数组的次数在预期中为 O(k log n(，因为流中稍后的元素很少导致写入。这是一个基于指数分布的有效方法(警告：前面的 Python 测试很轻(。运行时间为 O(n + k log n(。

import math
import random

def sample_from(population, k):
    for i, x in enumerate(population):
        if i == 0:
            sample = [x] * k
        else:
            t = float(k) * math.log(1.0 - 1.0 / float(i + 1))
            while True:
                t -= math.log(1.0 - random.random())
                if t >= 0.0:
                    break
                sample[random.randrange(k)] = x
    return sample