在大型文本文件中搜索字符串-在python中分析各种方法

Question

这个问题已经被问过很多次了。花了一些时间阅读答案之后，我进行了一些简要的分析，以尝试前面提到的各种方法…

• 我有一个 600 MB的 文件，其中包含 600万 行字符串（来自DMOZ项目的类别路径）。
• 每行上的条目都是唯一的。
• 我想 一次* 加载 文件并 继续在 数据中 搜索 匹配项 ***
  
  

我在下面尝试的三种方法列出了加载文件所需的时间，任务管理器中 负匹配的 搜索时间和内存使用情况

1) set :
    (i)  data   = set(f.read().splitlines())
    (ii) result = search_str in data

加载时间〜10s，搜索时间〜0.0s，内存使用量〜1.2GB

2) list :
    (i)  data   = f.read().splitlines()
    (ii) result = search_str in data

加载时间〜6s，搜索时间〜0.36s，内存使用量〜1.2GB

3) mmap :
    (i)  data   = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
    (ii) result = data.find(search_str)

加载时间〜0s，搜索时间〜5.4s，内存使用率〜NA

4) Hash lookup (using code from @alienhard below):

加载时间〜65s，搜索时间〜0.0s，内存使用量〜250MB

5) File search (using code from @EOL below):   
   with open('input.txt') as f:
       print search_str in f #search_str ends with the ('\n' or '\r\n') as in the file

加载时间〜0s，搜索时间〜3.2s，内存使用率〜NA

6) sqlite (with primary index on url):

加载时间〜0s，搜索时间〜0.0s，内存使用率〜NA

对于我的用例，只要我有足够的可用内存，似乎最好使用该设置。我希望对这些问题发表一些评论：

1. 一个 更好的替代品， 例如sqlite？
2. 的方式来 使用mmap改善搜索时间 。我有一个64位安装程序。[编辑]例如绽放过滤器
3. 随着文件大小增加到几GB，我有什么办法可以继续使用“设置”，例如，将其分成几批..
   
   

[编辑1] PS我需要经常搜索，添加/删除值，并且不能单独使用哈希表，因为稍后需要检索修改后的值。

欢迎任何意见/建议！

[edit 2]更新答案中建议的方法的结果[edit 3]更新sqlite结果

解决方案
：基于所有分析和费用分摊，我认为我将使用sqlite。第二种选择是方法4。sqlite的缺点是数据库大小是带有url的原始csv文件的两倍多。这是由于url上的主索引

Answer 1

如果您需要启动许多顺序搜索，则变式1非常有用。由于set在内部是哈希表，因此在搜索中相当不错。但是，构建需要花费时间，并且只有在您的数据适合RAM的情况下才能正常工作。

变体3适用于非常大的文件，因为您有足够的地址空间来映射它们，并且OS缓存了足够的数据。您进行全面扫描；一旦您的数据停止装入RAM，它就会变得相当慢。

如果您需要在行中进行多次搜索并且无法将数据放入RAM中，则SQLite绝对是一个好主意。将字符串加载到表中，构建索引，然后SQLite为您构建一个漂亮的b树。即使没有数据，树也可以放入RAM中（有点像@alienhard提出的内容），即使没有，也可以大大减少I
/ O所需的数量。当然，您需要创建一个基于磁盘的SQLite数据库。我怀疑基于内存的SQLite是否会明显击败Variant 1。