给定两个文件，在file1中查找单词，但在file2中查找单词

Question

给定两个文件会产生一个算法/程序来查找文件1中的单词，而不是文件2中的单词。请注意，文件中的单词不是按顺序排列的。

这是我的思考过程：

• 步骤1：读取文件2的单词并将其添加到哈希集

如果两个文件中的字数都只有100或1000个，那么这个算法就可以正常工作
但是，如果两个文件都很大（数十亿字），那么此解决方案将无法工作，因此我提出了一个改进的解决方案：

• 步骤1：逐字阅读文件2，并按字母顺序对单词进行排序为单词分配一个存储桶，对所有以“a”开头的单词说一个存储桶

所以地图看起来像['a'：{'sample'，'and'…}]。这将帮助我在log（n）时间复杂度内搜索bucket，然后在log（n）中查找单词是否包含在排序列表中。

• 步骤2：读取file1并检查file1中的一个单词是否没有bucket或不在bucket中包含的列表中

这个解决方案会奏效，但我相信还有改进的余地
如何进一步改进此解决方案？

Answer 1

一个可能的解决方案是使用一些外部排序来排序两个文件，然后并行迭代它们以找到一个只出现在文件1中的单词：

伪代码（排序后）：

iter1 = 0
iter2 = 0
while iter1 < file1.length:
    if file1[iter1] == file2[iter2]:
         iter1 = iter1 + 1
         iter2 = iter2 + 1
    else if file1[iter1] > file2[iter2]:
         iter2 = iter2 + 1
    else: //we know for sure the item is only in file1
         iter1 = iter1 + 1
         yield file1[iter1]

此解决方案占用O（nlogn）时间，并且只需要很少的空间（外部排序所需的空间量）。

还要注意的是，该问题是元素差异性问题的一个变体，因此在使用基于比较的算法时，它很可能具有Omega（nl0gn）的下限，或者使用散列的Omega（n）时间空间。