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

我有一个包含4 * 10^8（粗略）记录的表，我想要得到一个4 * 10^6（完全）的样本。Map-Reduce实现中的特殊示例方法

但我的方式获得样品有些特殊：

我选择随机的4 * 10^8条记录1（每条记录都有相同的概率要选择）。
重复步骤1 4 * 10^6次（不管多次选择一条记录）。

我想起来解决此一方法：

生成表A(num int)，并有在表A的每个记录只有一个号码是随机整数从1到n（n为大小我原来的桌子，大约4 * 10^8如上所述）。
加载表A作为每个地图的资源文件，如果现在决定的记录的序号现在在表A中，则输出该记录，否则将其丢弃。

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

那么，有没有人可以给一个优雅的算法？

来源

2014-12-04 Sayakiss

我不确定“优雅”是什么意思，但也许你对类似于油藏采样的东西感兴趣。令k为样本的大小并用空值初始化k元素数组。我们抽样的要素逐一到达。当第j个（从1开始计数）元素到达时，我们遍历数组，并且对于每个单元格，以当前元素以概率1/j独立替换其内容。天真地，运行时间非常糟糕 - 从n更换k个元素，并且更换成本为O（k n）。然而，写入数组的数量却是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

来源

2014-12-04 13:23:22

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

回答

相关问题