4

我有一个可能是30+GB或更多的文件。该文件中的每一行称为一条记录，由2 个 cols组成，如下所示

id1 id2

所有这 2 个 id 都是整数（32 位）。我的工作是编写一个程序来删除所有重复记录，使记录唯一，最后将唯一的 id2 输出到文件中。

有一些限制，最多允许30G 内存，最好由非多线程/进程程序有效地完成工作。

最初我想出了一个想法：由于内存限制，我决定读取文件n次，每次只将那些记录在内存中id1 % n = i (i = 0,1,2,..,n-1)。我使用的数据结构是 a std::map<int, std::set<int> >，它以 id1 为 key，并将 id2 放在 id1's 中std::set。

这样，不会违反内存约束，但速度很慢。我认为这是因为随着std::map和std::set变大，插入速度会下降。此外，我需要读取文件 n 次，当每一轮完成后，我必须清除std::map下一轮的文件，这也需要一些时间。

我也尝试过hash，但它也不能让我满意，我认为即使使用300W桶也可能存在太多冲突。

所以，我在这里发布我的问题，帮助你们提供更好的数据结构或算法。

非常感谢。

附言

需要脚本（shell、python），如果它可以有效地做到这一点。

4

4 回答 4

8

除非我忽略了一个要求，否则应该可以在 Linux shell 上这样做

sort -u inputfile > outputfile

许多实现也使您能够sort以并行方式使用：

sort --parallel=4 -u inputfile > outputfile

最多四个并行执行。

请注意，可能会暂时sort使用大量空间。/tmp如果那里的磁盘空间不足，您可以使用该-T选项将其指向磁盘上的另一个位置以用作临时目录。

（编辑：）关于效率的一些评论：

  • 在执行期间花费的大部分时间（任何解决您的问题的方法）将花费在 IO 上，这sort是高度优化的。
  • 除非您有非常多的 RAM，否则您的解决方案可能最终会在磁盘上执行一些工作（就像sort）。同样，优化这意味着大量的工作，而sort所有这些工作都已经完成。
  • 一个缺点sort是它对输入行的字符串表示进行操作。如果您要编写自己的代码，您可以做的一件事（类似于您已经建议的）是将输入行转换为 64 位整数并散列它们。sort如果您有足够的 RAM，如果您使 IO 和整数转换非常快，那么这可能是一种在速度方面击败的方法。我怀疑它可能不值得付出努力，因为sort它易于使用并且——我认为——足够快。
于 2012-09-17T03:44:28.243 回答
1

而不是std::map<int, std::set<int> >使用std::unordered_multimap<int,int>. 如果您不能使用 C++11 - 请自己编写。

它std::map是基于节点的，它在每次插入时调用 malloc，这可能是它很慢的原因。使用未排序的映射（哈希表），如果您知道记录数，则可以预先分配。即使您不这样做，malloc 的数量也将O(log N)代替O(N)with std::map。

我敢打赌，这将比使用 external 快几倍，内存效率更高sort -u。

于 2012-09-17T05:38:58.067 回答
1

当文件中没有太多重复记录时，这种方法可能会有所帮助。

第一次通过。为Bloom filter分配大部分内存。从输入文件中散列每一对并将结果放入布隆过滤器。将 Bloom 过滤器找到的每个重复项写入临时文件（该文件还将包含一些误报，它们不是重复项）。

第 2 次通过。加载临时文件并根据其记录构建地图。键是std::pair<int,int>，值是布尔标志。该映射可以实现为 std::unordered_map/boost::unordered_map 或 std::map。

第三关。再次读取输入文件，搜索映射中的每条记录，id2如果未找到或尚未设置标志，则输出其，然后设置此标志。

于 2012-09-17T10:02:42.087 回答
1

我只是认为如果不使用一堆磁盘就无法有效地做到这一点。任何形式的数据结构都会引入如此多的内存和/或存储开销，从而使您的算法受到影响。所以我希望排序解决方案在这里是最好的。

我认为您可以一次对文件的大块进行排序，然后在之后合并（即从合并排序）这些块。对一个块进行排序后，显然它必须回到磁盘。您可以只替换输入文件中的数据（假设它是二进制文件），或写入临时文件。

就记录而言，您只有一堆 64 位值。借助 30GB RAM，您一次可以保存近 40 亿条记录。这很甜蜜。您可以使用快速排序就地排序那么多，或者使用归并排序一半。您可能不会获得该大小的连续内存块。所以你将不得不打破它。这将使快速排序有点棘手，因此您可能还想在 RAM 中使用合并排序。

在最终合并期间，丢弃重复项是微不足道的。合并可能完全基于文件，但在最坏的情况下，您将使用相当于输入文件中记录数量两倍的磁盘量（一个文件用于暂存，一个文件用于输出）。如果您可以将输入文件用作临时文件，那么您没有超出 RAM 限制或磁盘限制（如果有）。

我认为这里的关键是它不应该是多线程的要求。这非常适合基于磁盘的存储。您的大部分时间将花在磁盘访问上。所以你要确保尽可能高效地做到这一点。特别是，当您进行合并排序时，您希望最大限度地减少搜索量。你有大量的内存作为缓冲区，所以我相信你可以让它变得非常高效。

所以假设你的文件是 60GB（我假设它是二进制的），所以大约有 80 亿条记录。如果您在 RAM 中进行合并排序，则一次可以处理 15GB。这相当于一次读取和（覆盖）写入文件。现在有四个块。如果你想做纯粹的合并排序，那么你总是只处理两个数组。这意味着您再读取和写入文件两次：一次将每个 15GB 块合并为 30GB，最后一次合并这些文件（包括丢弃重复项）。

我不认为这太糟糕了。三进三出。如果您找到了一种快速排序的好方法，那么您可以通过更少的文件来完成此操作。我想像这样的数据结构deque可以很好地工作，因为它可以处理不连续的内存块......但是您可能想要构建自己的并微调您的排序算法以利用它。

于 2012-09-17T04:28:29.980 回答