我有一个包含 4*10^8(粗略)条记录的表,我想得到它的 4*10^6(准确)样本。
但我获取样本的方式有些特殊:
- 我从 4*10^8 条记录中随机选择 1 条记录(每条记录被选中的概率相同)。
- 重复步骤1 4*10^6次(不管一条记录是否被多次选中)。
我想到了一个解决这个问题的方法:
- 生成一张表
A(num int)
,A
表的每条记录只有一个数字,是1到n的随机整数(n是大小我的原始表格的大小,如上所述大约为 4*10^8)。 - 将表
A
作为资源文件加载到每个 map 中,如果当前决策的记录的序号在表A
中,则输出这条记录,否则丢弃它。
我觉得我的方法不太好,因为如果我想从原始表中采样更多的记录,表A
会变得非常大,无法作为资源文件加载。
那么,有人能给出一个优雅的算法吗?
最佳答案
我不确定“优雅”是什么意思,但也许您对类似于水库采样的东西感兴趣。令 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
关于algorithm - Map-Reduce实现中的一种特殊示例方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27287501/