sorting - 大数据排序和搜索

Question

我有两个数据文件，每个文件 100 个字符行。文件 A：10 ⁸行，文件 B：10 ⁶行。而且我需要从文件 B 中找到不在文件 A 中的所有字符串。
起初我想将这两个文件都提供给 mysql，但看起来它永远不会完成在 10 ⁸条记录上创建唯一键。

我正在等待您对此的建议。

Answer 1

您可以在没有数据库的情况下执行此操作。关键是要减小 A 的大小，因为 A 比 B 大得多。下面是如何做到这一点：

对 B 文件中的字符串使用合适的散列函数计算 64 位散列。将它们存储在内存中（在哈希表中），您可以这样做，因为 B 很小。然后逐行散列 A 文件中的所有字符串，并查看每个字符串是否与 B 文件的散列匹配。任何具有匹配哈希的行（从 B 到一个）都应该存储在文件 C 中。

当这个过程完成时，文件 C 将具有 A 的一小部分可能匹配的字符串（到 B）。现在您有一个小得多的文件 C，您需要将其与 B 的行进行比较。这将问题简化为一个问题，您实际上可以将所有行从 C 加载到内存中（作为哈希表）并比较 B 的每一行以查看它是否在 C 中。

Answer 2

您可以稍微改进@michael-goldshteyn 的答案（https://stackoverflow.com/a/3926745/179529）。由于您需要找到 B 中不在 A 中的所有字符串，因此您可以从 B 的元素的哈希表中删除任何项目，当您将其与 A 中的元素进行比较并找到匹配项时。将保留在哈希表中的是文件 A 中未找到的元素。

Answer 3

对于您提到的大小，您应该能够一次将所有 B 保存在内存中，因此您可以做 Goldshteyn 答案的简化版本；在python中是这样的：

#!/usr/bin/python3

import sys

if __name__=='__main__':
  b = open(sys.argv[2],'r')
  bs = set()
  for l in b:
    bs.add(l.strip())
  b.close()
  a = open(sys.argv[1],'r')
  for l in a:
    l = l.strip()
    if l in bs:
      bs.remove(l)
  for x in bs:
    print(x)

我已经在两个 10^5 和 10^7 的文件上测试了这个，原子处理器上每行大约 8 个字符。/usr/bin/time 的输出：

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244