Python集合查找效率

Question

Python集合查找效率

7

我知道Python中的集合具有O（1）的查找时间，而列表具有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。

- Madison May

6

你可以尝试使用timeit来测试它 ;) - Joel Cornett

2

交叉点会因不同的Python实现、平台等而异。因此，显然需要自己进行测试。 - abarnert

1

这也取决于列表/集合中有哪些对象。对象可以定义它们的哈希如何计算，因此某些对象可能比其他对象更快地进行哈希。 - BrenBarn

1

我觉得数据结构的选择应该是显而易见的，并取决于你的使用/算法。 - Jonathon Reinhart

1

@abarnert：这也是正确的，因此它还取决于您有多频繁地对相同对象进行哈希处理，而不是新对象。正如所有这些评论所显示的那样，对于这个问题没有简单的答案 :-) - BrenBarn

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- abarnert · Accepted Answer

以下是您可以使用的代码，使用timeit测试它自己的方法：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

如果你有意地创建一个哈希缓慢且不进行缓存的对象，那么你当然可以将截止点推得更高。例如，在我的__hash__方法中加入time.sleep(1)，它最终会达到大约12M。