23

我必须检查包含 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 )
4

4 回答 4

30

set尽可能快。

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

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

于 2011-08-18T15:49:19.677 回答
14

正如我在评论中指出的那样，可能让您放慢速度的原因是您正在按顺序检查每一行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 所解释的，创建一个集合会创建一个哈希表。我怀疑（尽管再次从您的问题中不清楚），如果您可以在进行任何成员资格测试之前将所有输入数据放入一个集合中，那么它会快得多，而不是在一个项目中读取它时间，然后检查集合成员

于 2011-08-18T18:32:49.147 回答
0

您应该尝试拆分数据以加快搜索速度。树结构将使您能够非常快速地找到数据是否存在。

例如，从一个简单的映射开始，它将第一个字母与以该字母开头的所有键链接起来，因此您不必搜索所有键，而只需搜索其中的一小部分。

这看起来像：

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 倍）。

这是第一步，您可以对第二个字符做同样的事情，依此类推，然后搜索将只是用每个字母在树上行走......

于 2011-08-18T17:17:56.823 回答
-3

正如 urschrei 所提到的，您应该“矢量化”支票。一次检查一百万个元素的存在（就像在 C 中所做的那样）比检查一个元素一百万次要快。

于 2013-04-03T12:13:53.000 回答