外部随机播放:将大量数据从内存中移出

Question

我正在寻找一种方法来重新调整大量不适合内存的数据(大约40GB).

我有大约3000万个可变长度的条目,存储在一个大文件中.我知道该文件中每个条目的起始位置和结束位置.我需要将这些不适合RAM的数据洗牌.

我想到的唯一解决方案是使用Fisher-Yates算法1对包含数字的数组进行混洗N,其中N是条目数,然后根据此顺序将条目复制到新文件中.不幸的是,这个解决方案涉及大量的搜索操作,因此会非常慢.

是否有更好的解决方案来均匀分布大量数据？

Answer 1

首先解决您的shuffle问题。为此，请为您的条目发明一种哈希算法，该算法会产生类似随机的结果，然后对哈希进行常规的外部排序。

现在，您已将自己shuffle变成了一个sort难题，您的问题就变成了找到适合您的口袋和内存限制的高效外部排序算法。现在应该像一样简单google。

Answer 2

一个简单的方法是选择一个适合内存的数据K。1/K也许K=4是为了你的数据，假设你有 16GB RAM。我假设您的随机数函数具有从到rnd(n)生成统一随机数的形式。0n-1

然后：

for i = 0 .. K-1
   Initialize your random number generator to a known state.
   Read through the input data, generating a random number rnd(K) for each item as you go.
   Retain items in memory whenever rnd(K) == i.
   After you've read the input file, shuffle the retained data in memory.
   Write the shuffled retained items to the output file.

这非常容易实现，会避免大量的查找，并且显然是正确的。

另一种方法是根据随机数将输入数据分区到K文件中，然后遍历每个文件，在内存中进行洗牌并写入磁盘。这减少了磁盘IO（每个项目读取两次并写入两次，与第一种方法相比，每个项目读取K次并写入一次），但是您需要小心缓冲IO以避免大量查找，它使用中间盘较多，实施起来也比较困难。如果您只有 40GB 的数据（所以K很小），那么通过输入数据进行多次迭代的简单方法可能是最好的。

如果使用 20ms 作为读取或写入 1MB 数据的时间（并且假设内存中的 shuffle 成本微不足道），那么简单的方法将需要 40*1024*(K+1)*20ms，即 1 分 8 秒（假设K=4）。中间文件方法将花费 40*1024*4*20ms，大约 55 秒，假设您可以最小化查找。请注意，SSD 的读取和写入速度大约快 20 倍（甚至忽略查找），因此您应该期望使用 SSD 在远低于 10 秒的时间内执行此任务。每个程序员都应该知道的延迟数字

Answer 3

• 对数据库条目进行逻辑分区（例如按字母顺序）
• 根据您创建的分区创建索引
• 构建DAO，基于索引进行敏化