在大文本文件中搜索字符串 - Python中多种方法的性能分析

Question

这个问题已经被问过很多次了。在花了一些时间阅读答案后，我做了一些快速的性能测试，尝试了之前提到的各种方法……

• 我有一个600 MB的文件，里面有600万行字符串（来自DMOZ项目的分类路径）。
• 每一行的内容都是独一无二的。
• 我想加载这个文件一次，然后在数据中持续搜索匹配项。

我尝试的三种方法列出了加载文件所需的时间、搜索一个未匹配项的时间，以及任务管理器中的内存使用情况。

---

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

加载时间约为10秒，搜索时间约为0.0秒，内存使用约为1.2GB

---

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

加载时间约为6秒，搜索时间约为0.36秒，内存使用约为1.2GB

---

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

加载时间约为0秒，搜索时间约为5.4秒，内存使用情况为NA

---

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

加载时间约为65秒，搜索时间约为0.0秒，内存使用约为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

加载时间约为0秒，搜索时间约为3.2秒，内存使用情况为NA

---

6) sqlite (with primary index on url): 

加载时间约为0秒，搜索时间约为0.0秒，内存使用情况为NA

---

根据我的使用情况，似乎使用集合（set）是最好的选择，只要我有足够的内存可用。我希望能对以下问题得到一些评论：

1. 有没有更好的替代方案，比如sqlite？
2. 如何通过使用mmap来改善搜索时间。我有一个64位的系统。 [编辑] 比如布隆过滤器（bloom filters）
3. 当文件大小增加到几GB时，有没有办法继续使用集合，比如分批处理……

[编辑1] 附言：我需要频繁搜索，添加/删除值，不能单独使用哈希表，因为我需要稍后检索修改后的值。

欢迎任何评论或建议！

[编辑2] 更新了根据答案中建议的方法的结果 [编辑3] 更新了sqlite的结果

解决方案：根据所有的性能测试和反馈，我想我会选择sqlite。第二个选择是方法4。sqlite的一个缺点是数据库的大小是原始csv文件的两倍多，这是因为在url上有主索引。

Answer 1

你也可以试试

with open('input.txt') as f:
    # search_str is matched against each line in turn; returns on the first match:
    print search_str in f

确保search_str以正确的换行符结尾（'\n'或'\r\n'）。这样做会占用很少的内存，因为文件是逐步读取的。同时，这样也会比较快，因为只读取了文件的一部分。

Answer 2

自定义哈希表搜索与外部字符串

为了实现快速访问和更低的内存消耗，你可以这样做：

• 对每一行计算一个字符串的哈希值，并把它添加到哈希表中，比如说 index[hash] = position（注意：不要存储字符串本身）。如果出现哈希冲突，就把所有对应的文件位置存储在一个列表里。
• 查找一个字符串时，先计算它的哈希值，然后在表中查找。如果找到了这个键，就从文件中读取 position 位置的字符串，以确认你找到的确实是匹配的。如果有多个位置，就逐个检查，直到找到匹配的或者没有找到。

编辑 1：将行号替换为位置（正如评论者指出的，显然需要的是实际位置，而不是行号）

编辑 2：提供一个自定义哈希表的实现代码，展示这种方法比其他提到的方法更节省内存：

from collections import namedtuple 
Node = namedtuple('Node', ['pos', 'next'])

def build_table(f, size):
    table = [ None ] * size
    while True:
        pos = f.tell()
        line = f.readline()
        if not line: break
        i = hash(line) % size
        if table[i] is None:
            table[i] = pos
        else:
            table[i] = Node(pos, table[i])
    return table

def search(string, table, f):
    i = hash(string) % len(table)
    entry = table[i]
    while entry is not None:
        pos = entry.pos if isinstance(entry, Node) else entry
        f.seek(pos)
        if f.readline() == string:
            return True
        entry = entry.next if isinstance(entry, Node) else None
    return False

SIZE = 2**24
with open('data.txt', 'r') as f:
    table = build_table(f, SIZE)
    print search('Some test string\n', table, f)

一行的哈希值仅用于在表中索引（如果我们使用普通的字典，哈希值也会作为键存储）。该行的文件位置存储在给定的索引处。哈希冲突通过链式法解决，也就是说，我们创建一个链表。然而，第一个条目不会被包裹在一个节点中（这个优化让代码稍微复杂一些，但节省了不少空间）。

对于一个有600万行的文件，我选择了2^24大小的哈希表。根据我的测试数据，我得到了933132次冲突。（一个大小只有一半的哈希表在内存消耗上是相当的，但导致了更多的冲突。因为更多的冲突意味着搜索时需要更多的文件访问，所以我宁愿使用一个较大的表。）

Hash table: 128MB (sys.getsizeof([None]*(2**24)))
Nodes:       64MB (sys.getsizeof(Node(None, None)) * 933132)
Pos ints:   138MB (6000000 * 24)
-----------------
TOTAL:      330MB (real memory usage of python process was ~350MB)

Answer 3

方案1非常适合需要进行多个连续搜索的情况。因为set内部使用的是哈希表，所以搜索速度很快。不过，它需要一些时间来构建，而且只有在你的数据能够放进内存（RAM）时效果才好。

方案3适合处理非常大的文件，因为你有足够的地址空间来映射这些文件，并且操作系统会缓存足够的数据。你需要进行全面扫描；一旦数据无法完全放入内存，速度可能会变得很慢。

如果你需要连续进行多次搜索，而数据又无法放入内存，SQLite绝对是个不错的选择。你可以把字符串加载到一个表中，建立索引，SQLite会为你构建一个很好的B树。即使数据不能完全放入内存，这棵树也能适应（这有点像@alienhard提到的），而且即使不能，所需的输入输出（I/O）量也会大大减少。当然，你需要创建一个基于磁盘的SQLite数据库。我怀疑基于内存的SQLite能在性能上超过方案1。