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

Question

我有一个包含 4*10^8(粗略)条记录的表，我想得到它的 4*10^6(准确)样本。

但我获取样本的方式有些特殊:

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

我想到了一个解决这个问题的方法:

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

我觉得我的方法不太好，因为如果我想从原始表中采样更多的记录，表A会变得非常大，无法作为资源文件加载。

那么，有人能给出一个优雅的算法吗？

Answer 1

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

天真地，运行时间非常糟糕——以 O(k n) 的替换成本从 n 中采样 k 个元素。然而，写入数组的次数在预期中为 O(k log n)，因为流中后面的元素很少导致写入。这是一种基于 exponential distribution 的有效方法(警告:前面对 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