1

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

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

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

hosts_file 很大，我们正在谈论约 10000 个主机，我注意到搜索花费的时间比预期的要长。

我写了一个小测试：

import random, time
test_list = [x for x in range(10000)]
test_dict = dict(zip(test_list, [True for x in range(10000)]))

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)

结果如下：

list: 5.58524107933
dict: 0.195574045181

所以，对于我的问题。是否可以以更方便的方式执行此搜索？创建列表的字典似乎是一种 hack，因为我想搜索它们的键而不是它包含的值。

4

3 回答 3

5

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

于 2012-06-04T13:20:27.693 回答
2

我同意你应该为这样的事情使用字典，设置在更新的 python 上，如果你的应用程序可能的话，考虑移动到比 2.2 更新的 python。

但是，如果您的列表是按排序顺序排列的，您可以使用 bisect 模块快速搜索列表以查找元素。没有字典那么快，但非常接近。

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 上测试）：

list: 1.19566082954
dict: 0.0248260498047
blist 0.0598628520966
于 2012-06-04T13:42:32.743 回答
1

如果您的列表已排序，您可以使用bisect带有此辅助功能的模块：

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

编辑：bisect当我发布这个时，我没有看到马特安德森的答案。我将把它作为替代实现。

于 2012-06-04T13:47:02.537 回答