java - 外部洗牌 : shuffling large amount of data out of memory

Question

我正在寻找一种方法来随机播放不适合内存(大约 40GB)的大量数据。

我有大约 3000 万个条目，长度可变，存储在一个大文件中。我知道该文件中每个条目的开始和结束位置。我需要随机播放这些不适合 RAM 的数据。

我想到的唯一解决方案是将包含从 1 到 N 的数字的数组打乱，其中 N 是条目数, 与 Fisher-Yates algorithm然后根据此顺序将条目复制到新文件中。不幸的是，此解决方案涉及大量查找操作，因此会非常慢。

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

Answer 1

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

现在您已经将shuffle 转换为sort，您的问题变成了寻找适合您的口袋和内存限制的高效外部排序算法。这现在应该像 google 一样简单。