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

Question

这个问题已经被问过很多次了。在花了一些时间阅读答案后，我做了一些快速分析以尝试前面提到的各种方法......

• I have a 600 MB file with 6 million lines of strings (Category paths from DMOZ project).
• The entry on each line is unique.
• I want to load the file once & keep searching for matches in the data

我在下面尝试的三种方法列出了加载文件所花费的时间、否定匹配的搜索时间以及任务管理器中的内存使用情况

---

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

Load time ~ 10s, Search time ~ 0.0s, Memory usage ~ 1.2GB

---

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

Load time ~ 6s, Search time ~ 0.36s, Memory usage ~ 1.2GB

---

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

Load time ~ 0s, Search time ~ 5.4s, Memory usage ~ NA

---

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

Load time ~ 65s, Search time ~ 0.0s, Memory usage ~ 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

Load time ~ 0s, Search time ~ 3.2s, Memory usage ~ NA

---

6) sqlite (with primary index on url): 

Load time ~ 0s, Search time ~ 0.0s, Memory usage ~ NA

---

对于我的用例，只要我有足够的可用内存，似乎使用 set 是最好的选择。我希望就这些问题得到一些评论:

1. A better alternative e.g. sqlite ?
2. Ways to improve the search time using mmap. I have a 64-bit setup. [edit] e.g. bloom filters
3. As the file size grows to a couple of GB, is there any way I can keep using 'set' e.g. split it in batches ..

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

欢迎任何意见/建议!

[编辑 2] 使用答案中建议的方法的结果进行更新[编辑 3] 使用 sqlite 结果更新

解决方案:基于所有的分析和反馈，我想我会选择 sqlite。第二种选择是方法 4。 sqlite 的一个缺点是数据库大小是带有 url 的原始 csv 文件的两倍多。这是由于 url 上的主索引

Answer 1

如果您需要启动许多顺序搜索，变体 1 非常适合。由于 set 内部是一个哈希表，所以它比较擅长搜索。但是，构建需要时间，并且只有在您的数据适合 RAM 时才能正常工作。

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

如果您需要连续进行多次搜索并且无法将数据放入 RAM，那么 SQLite 绝对是一个好主意。将您的字符串加载到表中，构建索引，SQLite 会为您构建一个漂亮的 b-tree。即使数据不适合，树也可以放入 RAM(这有点像@alienhard 提出的建议)，即使不适合，所需的 I/O 数量也会大大降低。当然，您需要创建一个基于磁盘的 SQLite 数据库。我怀疑基于内存的 SQLite 会显着击败 Variant 1。