我必须检查列表中是否存在数百万个元素(20-30个字母str),其中包含10-100k个元素。在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 )
发布于 2011-08-18 23:49:20
set
是最快的。
但是,如果重写代码以创建一次set
,并且不对其进行更改,则可以使用frozenset
内置类型。除了不可变之外,它是完全相同的。
如果你仍然有速度问题,你需要用其他方法来加速你的程序,比如使用PyPy而不是cPython。
发布于 2011-08-19 01:17:57
您应该尝试拆分您的数据,以使搜索更快。树结构将允许您非常快速地查找数据是否存在。
例如,从一个简单的映射开始,该映射将第一个字母与以该字母开头的所有键相链接,因此您不必搜索所有键,而只需搜索其中较小的一部分。
这看起来像这样:
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倍)。
这是第一步,你可以对第二个字符做同样的事情,依此类推,然后搜索每个字母就会遍历整个树……
发布于 2013-04-03 20:13:53
正如urschrei所提到的,您应该对检查进行“矢量化”。检查一百万个元素是否存在要比检查一个元素一百万次要快得多。
https://stackoverflow.com/questions/7110276
复制相似问题