有没有更高效的方法来调和大型数据集？

Question

有没有更高效的方法来调和大型数据集？

5

我被分配了一个任务，需要对两个大数据集（两个大事务列表）进行对账。基本上，我从两个数据源中提取相关字段到两个相同格式的文件中，然后比较这些文件，以找到在A中但不在B中的任何记录，反之亦然，并报告它们。我在我的最佳努力下写了一篇博客文章（如果感兴趣，请点击）。其要点是将两个数据集加载到一个大的哈希表中，其中键为行，值为每次出现在文件A中加1，在文件B中出现时减1。然后在最后，我查找任何值不等于0的键/值对。

我的算法似乎足够快（2个100mb文件的10秒），但它有点耗费内存：比较两组100mb文件需要280mb，我希望将其降至100mb峰值内存使用量，并且如果两个数据集的排序大致相同，则可能会更低。

有什么想法吗？

另外，请告诉我这是否对SO来说过于开放。

- Chris

4个回答

1

我能想到的唯一方法是不要一次性将所有数据加载到内存中。如果你改变处理方式，逐步获取每个文件的一部分，则可以减少内存占用，但会增加磁盘IO，这可能导致处理时间更长。

- mezoid

我准备为了使用更少的内存而牺牲一些处理时间。你有任何想法如何不一次性将至少一个数据集的所有数据都加载到内存中？这可能很困难，因为这两个数据集的顺序不同。 - Chris

不知道是否重要，但你引用的内存是在数据极少重叠（因此报告几乎为A.txt + B.txt大小）还是在数据高度匹配时？如果是针对大量匹配，并且您不关心报告中的匹配数据，则可以尝试在找到匹配项后立即删除匹配项。您可以尝试在内存数据结构中删除。此外，您可以尝试从文件中删除匹配项。 - umar

存在非常低的不匹配率 - 例如可能有几十个记录不匹配。那么您是建议在加载第二个文件时从哈希表中删除匹配键吗？我想我尝试过，但内存使用量并没有减少很多。然而，这可能是因为垃圾回收器没有经常进行回收。 - Chris

1

一种选择可能是改变内存中数据的格式。如果您的数据是以文本形式存储的一系列数字，则将它们作为整数存储在内存中可能会降低内存占用。

另一个选择可能是使用某种外部程序来对行进行排序--然后你可以按顺序简单地扫描这两个文件，寻找差异。

回到你的问题上来，对于比较一对100mb文件而言，280mb听起来有点高了--你只需要将其中一个加载到内存中（较小的那个），并滚动浏览另一个即可，不需要同时将两个文件的全部内容都加载到内存中。

- Jonathan Rupp

我喜欢使用另一个程序事先对行进行排序的想法。那肯定会简化比较过程。但你能想到一种使用更少内存来进行行排序的方法吗？ - Chris

我已经使用DOS sort命令进行了测试：每个文件需要10秒钟，并且使用225MB的内存。因此，内存使用与我的解决方案相当。但是我认为你发现了一些东西。 - Chris

归并排序的好处在于理论上可以通过两遍系统选择内存限制--读取X行，对其进行排序，并将其写入文件1，然后重复处理文件的剩余部分。接下来，同时读取所有文件，仅写出最低行并推进该文件。如果您设置了一个从文件中读取的IEnumerable<string>实现和一个接受N个IEnumerable<string>的MergeSort，那么让它工作起来应该相对简单。 - Jonathan Rupp

现在我看到了Chris对Kevin的回答的评论——显然那被称为“外部排序”。很有道理。 - Jonathan Rupp

没错，你刚刚描述了一个“外部归并排序”。嘿，两个人想出类似的解决方案没有任何问题，这说明它是一个好的解决方案。 - Chris

刚刚实现了归并排序：http://splinter.com.au/blog/?p=142 - Chris

0

使用这种方法，您必须始终在内存中保留其中一个文件的内容。从内存角度来看，更有效的方法是将文件的一半取出，逐行与第二个文件进行比较。然后将第二部分移到内存中并执行相同操作。此重叠将确保没有记录被遗漏。并且消除了需要暂时存储整个文件的需要。

- slimbo

此外，如果您需要使用更少的内存，您可以将文件的前三分之一与第一部分进行比较，然后将文件的第二个三分之一与第一部分进行比较，以此类推。显然，随着时间的推移，增加内存会牺牲程序速度。 - slimbo

这听起来与Kevin的答案相似，但他只建议一次读入单行而不是半个文件。结合外部排序，这是调和大型数据集的方法。 - Chris

他建议的方法对于大数据文件不起作用。他的方法是外部排序两个文件（像我的方法一样），然后打开两个文件（与我的方法不同）并逐行比较它们。计算机没有足够的内存来执行此操作。我建议先打开文件的一半，然后将其逐行与第二个文件进行比较。因此，每次只使用一个文件的一半（或更少）。Kevin的方法同时打开两个文件（至少需要4倍的内存）。 - slimbo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kevin Nisbet · Accepted Answer

我以前在Unix上使用Shell和Perl脚本完成了类似的任务，理论可能相同。

第一步，按照相同的标准排序两个文件。我使用了Unix的sort命令来做到这一点（我需要唯一标识符，但你只需要某种内存高效的文件排序）。这很可能是自己解决的棘手部分。

第二步，打开两个文件，基本上逐行扫描它们（如果是二进制格式，则一条记录一条记录地扫描）。如果左侧文件中的行与右侧文件中的行相等，则这些行匹配，然后继续向下执行（记住，我们已经对文件进行了排序，因此最小的记录应该在最前面）。

如果左记录大于右记录，则你的右记录缺失，请将其添加到列表中，并阅读右侧文件的下一行。然后再次进行检查。如果你的右记录更大，则你的左记录缺失，请报告并继续进行。

扫描记录应该非常高效。也许不会很快，但对于我来说，我能够在几分钟内处理多个字段的几千兆字节数据。