python中的成员资格测试比set()更快

Question

我必须在包含10-100k这些元素的列表中检查数百万个元素(20-30个字母str)的存在.在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

set 和它一样快.

但是,如果您重写代码以创建set一次,而不是更改它,则可以使用frozenset内置类型.除了不可变之外,它完全相同.

如果您仍然遇到速度问题,则需要以其他方式加速程序,例如使用PyPy而不是cPython.

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)

上面的程序在我5岁的机器上以大约6个挂钟时间运行,并且它测试的是大型设备的成员资格而不是你需要的(除非我误解了你).大部分时间实际上是创建集合,所以你甚至不会有这个开销.你引用的字符串很长的事实与此无关; 正如agf解释的那样,创建一个集合会创建一个哈希表.我怀疑(尽管你的问题还不清楚)如果你能在进行任何会员资格测试之前将所有输入数据都集成到一个集合中,那么它会快得多,而不是在一个项目中读取它时间,然后检查集合成员资格