从Python中庞大的统一发行版中抽取样本

Question

我需要从范围3.7*10^8中选择[0, 3*10^9]唯一值，或者按顺序获得它们，或者将它们保存在内存中。

为了做到这一点，我开始研究一个简单的算法，在这个算法中，我对更小的均匀分布(适合内存)进行了采样，以便间接地对真正感兴趣的大型分布进行采样。

代码可在下面的gist https://gist.github.com/legaultmarc/7290ac4bef4edb591d1e中获得

因为我在实现一些更健壮的东西时遇到了困难，所以我想知道您是否有其他的想法来从一个大型的离散统一中采样唯一的值。我正在寻找一个算法，一个模块，或一个想法，如何直接管理非常大的列表(也许使用硬盘驱动器，而不是内存)。

Answer 1

有一篇有趣的文章，Generating sorted random ints without the sort? O(n)，它建议你可以在指数随机增量上做一个运行和，它给出了一个按排序顺序生成的一致随机结果，而不是生成均匀的随机整数。

它不能保证给出您想要的样本数量，但是应该非常接近，并且需要更快/更低的内存需求。

编辑：，我发现了第二篇文章，generating sorted random numbers without exponentiation involved?，它建议在生成一个确切数量的样本时调整分布密度，但我对这会对您的“统一”分布造成什么影响持怀疑态度。

Edit2:我遇到的另一种可能性是使用逆累积二项分布迭代地分割样本范围(预测有多少均匀生成的随机样本落在范围的下半部分，其余部分必须在上半部分)，直到块大小达到可以很容易地保存在内存中的部分为止。

Answer 2

这是一个没有替换的标准样本。您不能将范围0，3*10^9划分为相同的绑定范围，并在每个桶中对相同的数量进行采样。另外，30亿是相对较大的，许多“准备使用”代码只处理32位整数，大约20亿(+-)。请仔细查看它们的实现。