我有一个数据文件，其中有大量的值（53,000,000+），我想抽出这些值（比如2,000,000）的随机子集n。我实现了一个将列表拖入内存的Perl脚本，使用Fisher-Yates method对数组进行混洗，然后在混洗列表中输出第一个和值。然而，即使在更小的测试集（50,000个值）上，该洗牌过程也会花费大量的时间。从一个巨大的清单中进行有效的随机抽样
我正在寻找更高效，可扩展的方式来识别一组巨大的值的随机子集并打印出来。有什么建议么？
更新：根据答案和一些更多的搜索，它看起来像正确的术语是“随机抽样”。
在上面的aix的回答中详细说明，要从项目流中选择k，请一次一个地读取项目。将第一个k项目保留在一组S中。
现在读m个项目I（m>k现在）时，使之与概率k/m。如果确实保留，请从S随机选择一个项目U，并用I替换U。
证明这产生所有子集的大小为k等概率是基于对m的归纳。请注意，您无需事先知道n（项目总数），并且每个步骤中的S都适用。该算法是“流式传输” - 它不需要存储所有项目，或者进行第二遍。
这是一个在线算法，非常适合未知大小的流。但大小在这里是已知的，所以你可以做得比 –
好，你可以做得更好，因为当你预先知道n时，你需要减少对随机数发生器的调用（k而不是n），并且你可以存储在内存中设置。时间复杂性，两者都是O（n），并且在线算法使用O（1）空间，而不是\ Theta（n） – adnan
nope，如果该集合已经在内存中，则时间复杂度仅为O（k） 。如果没有，那么这是一个记忆vs速度的折衷，所以从这个意义上说，你是对的。 –
首先，检查你的shuffle的实现。如果实施正确，应该给你线性时间。此外，修改算法以在所需数量的元素被洗牌后停止：不需要（实际上和理论上）洗牌比您实际输出更多的数字。
如果你问k个数字，这会花费你k元素的操作。我怀疑你可以做得比这更好。
这是最好的算法，如果你有足够的内存 –
不要洗牌，这是不必要的昂贵。
在Jon Bentley的"Programming Pearls"中讨论过simple linear algorithm（宾利说他从Knuth的"Seminumerical Algorithms"了解到）。改用此方法。
有一些Perl implementations约：
这两个片段来自Knuth的艺术编程实现Algortihm S（3.4.2）和Algortihm R（3.4.2） 。第一个从元素数组中随机选择N个项目 ，并返回对包含元素的数组 的引用。请注意，它不一定会考虑 列表中的所有元素。
第二个从不确定大小的文件 中随机选择N个项目，并返回包含所选元素的数组。 文件中的记录被假定为每行，并且行被读取，而 读取。这只需要1次通过列表。轻微 修改，可向使用情况的片段，其中N 记录将超过内存限制，但是这需要 略多于1通（/味精，如果你需要这个解释）
阅读和洗牌数组会涉及大量不必要的数据移动。
这里有一些想法：
一：当你说你需要一个随机子集，你到底在这方面的意思是“随机”？我的意思是，记录是以任何特定的顺序出现的，还是与您试图随机化的相关的顺序？
因为我的第一个想法是，如果记录没有任何相关的顺序，那么您可以通过简单计算总大小除以样本大小，然后选择每个第n条记录来获得随机选择。例如，如果你有5300万条记录，而你想要200万的样本，则需要5300万/ 200万〜26，所以每26条记录读一遍。
二：如果这还不够，更严格的解决方案是生成200万个随机数，范围在0到5300万之间，确保没有重复。 2-A：如果你的样本量与总记录数相比很小，就好像你刚刚挑选了几百或几千个样本一样，我会生成一个包含很多条目的数组，并为每个条目，将其与以前的所有条目进行比较以检查重复项。如果它是重复的，请循环并重试，直到找到唯一值。
2-B：假设你的数字不仅仅是实例而是实际值，那么你的样本量与总人口相比是很大的。在那种情况下，考虑到现代计算机上有足够的内存，您应该能够通过创建一个5300万个布尔值的数组来初始化为false来实现这一点，当然每个布尔值代表一个记录。然后运行200万次循环。对于每次迭代，生成一个从0到53百万的随机数。检查数组中相应的布尔值：如果为false，则将其设置为true。如果确实如此，则生成另一个随机数并重试。
三：或者等等，给出相对较大的百分比，这里有一个更好的主意：计算你想包括的记录的百分比。然后循环遍历所有记录的计数器。对于每一个，生成从0到1的随机数并将其与所需的百分比进行比较。如果更少，请阅读该记录并将其包含在样本中。如果更大，请跳过该记录。
如果确定样本记录的确切数量很重要，则可以重新计算每条记录的百分比。例如 - 为了保持简单的例子，让我们假装你想要100条记录中的10条：
你会以10/100 = .1开头所以我们生成一个随机数，比方说它出现.04。 .04 <.1，所以我们包含了记录＃1。
现在我们重新计算百分比。我们还需要99个剩余的9个记录给出9/99〜= .0909说我们的随机数是.87。这是更大的，所以我们跳过第2条记录。
再次重新计算。我们仍然需要98个剩余的9个记录。所以魔术数字是9/98，无论如何。等等
一旦我们获得了尽可能多的记录，未来记录的概率将为零，所以我们永远不会过去。如果我们接近尾声并没有拿到足够的记录，概率将会非常接近100％。就像，如果我们仍然需要8条记录，而只剩下8条记录，概率将会是8/8 = 100％，所以我们将保证采取下一条记录。
你如何交换）？ I/O是瓶颈还是洗牌？也许有些代码也会有帮助。 – delnan
@delnan我尝试了链接线程上描述的两种方法。 I/O绝对不是问题。它很快加载到内存中，但随后在洗牌步骤花费大量时间。它永远不会完成并开始打印。现在我已经尝试过了，我认为洗牌方法对于这么多值不会有足够的效率，所以我可能对替代方法更感兴趣。 –
你需要的数据是随机的吗？您可能可以使用循环，通过随机标记进行跳转，然后在检索后将该元素标记为“已使用”以防止出现重复。 –