大数据排序和搜索

Question

我有两个数据文件，每条100条字符。文件A：10⁸ 线，文件B：10⁶ 线。我需要从文件B中找到所有文件B中的所有字符串。
起初，我在考虑将两个文件馈送到MySQL，但看起来它永远不会完成10的唯一键⁸ 记录。

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

Answer 1

您可以在没有数据库的情况下执行此操作。关键是减小A的大小，因为A比B大得多。这是这样做的方法：

使用B文件中的字符串的不错的哈希功能计算64位哈希。将它们存储在内存中（在哈希表中），您可以这样做，因为B很小。然后哈希a文件中的所有字符串，逐行排列，然后查看每个字符串是否匹配您的b文件的hash。任何具有匹配哈希的线（从B中的一条）都应存储在文件C中。

当此过程完整时，文件C将具有潜在匹配字符串的a的小子集（to b）。现在，您需要比较B与B的线路的较小的文件C。这将问题降低到一个问题，您可以实际将所有C中的所有线加载到内存中（作为Hash表）并比较B的每一行以查看是否在C中。

Answer 2

您可以在 @Michael-Goldshteyn的答案上稍微改进（https://stackoverflow.com/a/3926745/179529）。由于您需要查找不在A中的B中的所有字符串，因此可以从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