Dan*_*age 5 random performance sampling
我有一个包含大量值（53,000,000+）的数据文件，我想提取这些值中n 个的随机子集（例如 2,000,000）。我实现了一个 Perl 脚本，它将列表拉入内存，使用Fisher-Yates 方法对数组进行洗牌，然后打印出洗牌列表中的前n个值。然而，即使在较小的测试集（50,000 个值）上，这种改组过程也需要花费大量时间。
我正在寻找一种更有效、可扩展的方法来识别大量值的随机子集并将其打印出来。有什么建议么？
更新：根据答案和更多搜索，看起来正确的术语是“随机采样”。
详细阐述上面 aix 的答案，要从k一系列项目中进行选择，请一次阅读一个项目。k保留一组中的第一个项目S。
现在，当阅读m第-项I（m>k现在）时，将其保留为概率k/m。如果保留，U则从 中均匀随机选择一项S，并替换U为I。
证明这会k以相同的概率产生所有大小子集，这是基于 的归纳m。请注意，您不需要n提前知道（项目总数），并且S每一步都是合适的。该算法是“流式”的——它不需要存储所有项目，或进行第二次传递。