在大型文本文件中搜索字符串 - 在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

---

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

1. 一个更好的选择,例如sqlite？
2. 的方式来使用mmap改善搜索时间.我有一个64位的设置.[编辑]例如布隆过滤器
3. 随着文件大小增加到几GB,有什么方法可以继续使用'set',例如分批分割它.

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

欢迎任何意见/建议!

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

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

Answer 1

如果您需要启动许多顺序搜索,变体1非常棒.由于set内部是哈希表,因此它在搜索方面相当不错.但是,构建需要时间,并且只有在数据适合RAM时才能正常工作.

Variant 3适用于非常大的文件,因为您有足够的地址空间来映射它们并且OS缓存足够的数据.你做了全扫描; 一旦数据停止适应RAM,它就会变得相当慢.

如果您需要在行中进行多次搜索而无法将数据放入RAM中,那么SQLite绝对是一个不错的主意.将字符串加载到表中,构建索引,SQLite为您构建一个漂亮的b树.树可以放入RAM,即使数据没有(这是一个有点像@alienhard什么建议),即使没有,如果I/O所需要的量显着降低.当然,您需要创建基于磁盘的SQLite数据库.我怀疑基于内存的SQLite会显着击败Variant 1.

Answer 2

使用外部化字符串自定义哈希表搜索

要获得快速访问时间和较低的内存消耗,您可以执行以下操作:

• 每行计算哈希值的字符串,并将其添加到一个哈希表,例如,index[hash] = position(千万不能存储字符串).如果发生冲突,请将该密钥的所有文件位置存储在列表中.
• 查找字符串,计算其哈希并在表中查找.如果找到密钥,请position从文件中读取字符串以验证您确实匹配.如果有多个位置检查每个位置,直到找到匹配或没有.

编辑1:按位置替换line_number(由评论者指出,显然需要实际位置而不是行号)

编辑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)

一行的哈希仅用于索引表(如果我们使用普通的dict,则哈希也将存储为键).该行的文件位置存储在给定的索引处.通过链接解决冲突,即我们创建链接列表.但是,第一个条目永远不会包含在节点中(这种优化使代码更复杂,但它节省了相当多的空间).

对于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

你也可以试试

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'）结尾。这应该使用很少的内存，因为文件是逐步读取的。它也应该非常快，因为只读取文件的一部分。