“x in[]”与“x in{}”的搜索次数

Question

我遇到了一个问题，我必须查看代理日志，看看用户是否访问过站点列表。在

我编写了一个小脚本来读取所有代理日志，将访问的主机与列表进行匹配：

for proxyfile in proxyfiles:
    for line in proxyfile.readlines():
        if line[4] in hosts_list:
            print line

hosts_文件很大，我们正在讨论大约10000个主机，我注意到搜索时间比预期的要长。在

我写了一个小测试：

^{pr2}$

结果如下：

list: 5.58524107933
dict: 0.195574045181

所以，关于我的问题。 有没有可能以更方便的方式进行搜索？创建一个列表字典看起来像是一个黑客，因为我想搜索它们的键，而不是它包含的值。在

Answer 1

我同意您应该使用字典来处理这类事情，在更新的python上设置，如果您的应用程序可能的话，考虑迁移到比2.2更新的python。在

但是，如果列表是按排序顺序排列的，则可以使用“对分”模块快速搜索列表以查找元素。虽然不如迪克特快，但很接近。在

import random, time
import bisect

class BisectContainsList(list):
    def __contains__(self, elem):
        i = bisect.bisect_left(self, elem)
        if i != len(self) and self[i] == elem:
            return True
        return False

test_list = [x for x in range(10000)]
test_dict = dict(zip(test_list, [True for x in range(10000)]))
test_blist = BisectContainsList(test_list)

def test(test_obj):
 s_time = time.time()
 for i in range(10000):
  random.randint(0,10000) in test_obj
 d_time = time.time() - s_time
 return d_time

print "list:", test(test_list)
print "dict:", test(test_dict)
print "blist", test(test_blist)

对于（2.7测试）：

^{pr2}$

Answer 2

“因为我想搜索他们的键而不是它包含的值”=>；然后只需使用set

Answer 3

如果您的列表已排序，则可以将bisect模块与此助手函数一起使用：

def sorted_list_contains(alist, item):
    i = bisect.bisect_left(alist, item)
    return i != len(alist) and alist[i] == item

编辑：当我发布这篇文章时，我没有看到MattAnderson用bisect的回答。我将把这个作为一个替代的实现。在