algorithm - 从两个文件中查找常用词

Question

给定两个包含单词列表(大约百万)的文件，我们需要找出共同的单词。

使用一些高效的算法，也没有足够的可用内存(100 万，当然不是)。如果可能的话，一些基本的 C 编程代码会有所帮助。

文件没有排序..我们可以使用某种算法...请用基本代码支持它...

排序外部文件......用最小可用内存，如何用C编程实现。

任何对文件进行外部排序的游戏...请为此分享一些代码。

Answer 1

另一种方法。

一般。首先，请注意按顺序执行此操作需要 O(N^2) .与 N=1,000,000 ，这是很多。对每个列表进行排序需要 O(N*log(N)) ;然后您可以通过合并文件一次性找到交集(见下文)。所以总数是O(2N*log(N) + 2N) = O(N*log(N)) .

排序文件。现在让我们解决一个事实，即处理文件比处理内存要慢得多，尤其是在需要移动东西的地方进行排序时。解决这个问题的一种方法是 - 确定可以加载到内存中的 block 的大小。一次加载一个文件 block ，高效地对其进行排序并保存到一个单独的临时文件中。排序后的 block 可以一次合并(再次参见下文)到一个排序文件中。

Merging 。当您有 2 个排序列表(文件与否)时，您可以一次轻松地将它们合并到一个排序列表中:有 2 个“指针”，最初指向每个列表中的第一个条目。在每一步中，比较指针指向的值。将较小的值移动到合并列表(您正在构建的列表)并推进其指针。

您可以轻松修改合并算法以使其找到交集 - 如果指向的值相等，则将其移动到结果(考虑您要如何处理重复项)。

要合并超过 2 个列表(如上面的文件排序)，您可以概括使用 k 的算法指针。