Python设置查找效率

Question

我知道python集有O(1)查询时间,python列表有O(n)查找时间,但我很好奇容器大小,它将列表转换为集合变得值得.

换句话说,如果我打电话给下面的话:

arr = [1, 2, 3]
for i in range(1000000):
    random.randint(1,3) in arr

它会比调用以下内容更有效吗？

s = set([1, 2, 3])
for i in range(1000000):
    random.randint(1,3) in s

更重要的是,交叉长度是多少？

编辑:共识是,这完全取决于用户定义对象的哈希方法的有效性,但对于字符串,int等原语 - 截止值约为1-3.

Answer 1

以下是您可以使用以下代码自行测试的一些代码timeit:

import timeit
for i in range(10):
    l = list(range(i))
    s = set(l)
    t1 = timeit.timeit(lambda: None in l, )
    t2 = timeit.timeit(lambda: None in s)
    print(i, t1, t2)

您应该在您真正关心的平台和Python实现上运行它.

还要注意我正在搜索None而不是1,因为搜索保证是列表中第一个(或第二个)事物的值是常量时间,并且我在初始测试中使用整数(这是当然,哈希是微不足道的).您应该测试您关心的实际数据.

无论如何,在我方便的所有实现上测试它,我得到0(64位PyPy 2.1.0/2.7.3)截止到3(32位PyPy 1.9.0/2.7.2),大多数他们是1-2.例如,这里的64位Python 3.3.2在1处交叉:

0 0.10865500289946795 0.11782343708910048
1 0.1330389219801873 0.11656044493429363

如果你故意创建一个哈希缓慢且不缓存的对象,当然,你可以根据需要推动该截止值.例如,通过time.sleep(1)在我的__hash__方法中添加一个大约12M的方法.