比set()更快的Python成员测试

Question

我需要检查在一个包含10到10万个元素的列表中，是否存在数百万个元素（每个元素是20到30个字母的字符串）。在Python中，有没有比使用set()更快的方法来做到这一点呢？

import sys
#load ids
ids = set( x.strip() for x in open(idfile) )

for line in sys.stdin:
    id=line.strip()
    if id in ids:
        #print fastq
        print id
        #update ids
        ids.remove( id )

Answer 1

你应该尝试把数据分开，这样搜索会更快。树形结构可以让你很快找到数据是否存在。

比如，先用一个简单的映射，把每个字母和所有以这个字母开头的键联系起来。这样你就不需要搜索所有的键，只需要找一小部分。

这看起来像这样：

ids = {}
for id in open(idfile):
    ids.setdefault(id[0], set()).add(id)

for line in sys.stdin:
    id=line.strip()
    if id in ids.get(id[0], set()):
       #print fastq
       print id
       #update ids
       ids[id[0]].remove( id )

创建这个结构可能会慢一点，但搜索会快很多（如果你的键的第一个字符分布得当，而不是总是一样的，我预计会快20倍）。

这只是第一步，你可以对第二个字符做同样的事情，依此类推，搜索时就只需要沿着树走每个字母...

Answer 2

正如我在评论中提到的，可能让你程序运行变慢的原因是你在逐行检查来自 sys.stdin 的每一行，看它是否在你的“主”集合里。这种做法会非常非常慢，而且没有利用到集合操作的速度。举个例子：

#!/usr/bin/env python

import random

# create two million-element sets of random numbers
a = set(random.sample(xrange(10000000),1000000))
b = set(random.sample(xrange(10000000),1000000))
# a intersection b
c = a & b
# a difference c
d = list(a - c) 
print "set d is all remaining elements in a not common to a intersection b"
print "length of d is %s" % len(d)

在我这台五年历史的电脑上，上面的代码大约需要6秒钟才能运行完，而且它测试的集合比你需要的要大（除非我理解错了）。大部分时间其实是用来创建集合的，所以你并不会有这个额外的开销。你提到的字符串很长这一点在这里并不重要；创建集合时会生成一个哈希表，正如agf所解释的那样。我怀疑（虽然从你的问题中不太清楚）如果你能在进行任何成员测试之前，把所有输入数据放进一个集合里，这样会快很多，而不是一个一个地读取数据，然后再检查它是否在集合里。

Answer 3

set 是最快的选择。

不过，如果你把代码改成只创建一次 set，而不去修改它，那么可以使用 frozenset 这个内置类型。它和 set 一样，只是不能被改变。

如果你还是觉得速度不够快，那就需要通过其他方法来加速你的程序，比如使用 PyPy 而不是 cPython。