此链接"http://had00b.blogspot.com/2013/07/random-subset-in-mapreduce.html"谈到了如何使用map reduce框架实现储层采样。我觉得他们的解决方案很复杂，下面更简单的方法会起作用。
问题：给定非常大量的样本，生成一个大小为k的集合，使得每个样本在该集合中存在的概率相等。
建议的解决方案：
- 映射操作：对于每个输入数字n，输出（i，n），其中i在0到k-1的范围内随机选择
- 减少操作：在所有具有相同键的数字中，随机选择一个
索赔：k大小集合中任何数字的概率为k/n（其中n是样本总数）
证明直觉：
由于映射操作将每个输入样本随机分配给桶编号i（0<=i<=k-1），因此每个桶的大小将是n/k。现在每个数字只存在于一个桶中，假设桶i。在桶i的reduce操作中，它被选中的概率是1/（n/k）=k/n
对于我的解决方案，无论它看起来是否正确，我都非常感激
您的参数中有一个小缺陷。您的算法可能不会返回大小为k的样本，因为可能没有任何元素映射到特定的键。在极端情况下（即使可能性很小），可能会发生所有输入元素只映射到一个键的情况，在这种情况下，您的算法只返回一个元素。
"丢失"特定密钥的事件具有概率（（k-1）/k）^n=（1-1/k）^n，其近似（使用泰勒近似）e^{-n/k}。如果k比n小得多，这是可以忽略的，但如果k与n成比例，比如k=n/2，那么这个坏事件实际上以恒定的概率发生。