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

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

编辑:共识是这完全取决于用户定义对象的哈希方法的效率，但对于字符串、整数等原语——截止值大约为 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。