列表中的搜索性能优于集合中

Question

在集合中搜索元素需要 O(1) 时间复杂度，而在列表中搜索则需要 O(n) 时间复杂度。 n 是集合或列表中的元素数量。

在我对实际搜索时间成本的测试中，n设置为1,000,000，我认为这是一个很大的数字。测试结果为集合中的48.3毫秒，而列表中的28毫秒，这表明列表中的搜索比集合中的搜索快，这与时间复杂度分析相矛盾。我尝试增加 n 并比较搜索速度，结果发现这个发现成立，直到 n 很大时出现内存错误。

（基）PS C：\ Users> python -m timeit -n 100“集合中的300（范围（1000000））”

100 个循环，5 个循环中最好的：每个循环 48.3 毫秒

（基）PS C：\用户> python -m timeit -n 100“列表中的300（范围（1000000））”

100 个循环，5 个循环中最好的：每个循环 28 毫秒

时间成本结果

你能帮我理解为什么在Python中搜索列表中的序列比在集合中搜索序列的性能更好吗？

我无法理解。

Answer 1

我认为集合创建占用了大部分时间，因为它涉及对每个元素进行哈希处理，正如 @tim-peters 所提到的。

在这里，我在执行搜索操作之前创建了集合和列表，并且集合的搜索似乎要快得多。

import random
import timeit

def setup(n):
    data = list(range(n))
    random.shuffle(data)
    return set(data), data

def test_set(s, value):
    return value in s

def test_list(l, value):
    return value in l

n = 1000000
s, l = setup(n)

# Test with a value that's guaranteed to be in both
value_in = random.choice(l)

# Test with a value that's guaranteed not to be in either
value_out = n + 1

print("Searching for a value that exists:")
print("Set:", timeit.timeit(lambda: test_set(s, value_in), number=1000))
print("List:", timeit.timeit(lambda: test_list(l, value_in), number=1000))

print("\nSearching for a value that doesn't exist:")
print("Set:", timeit.timeit(lambda: test_set(s, value_out), number=1000))
print("List:", timeit.timeit(lambda: test_list(l, value_out), number=1000))

结果

Searching for a value that exists:
Set: 0.00023545200008356915
List: 28.11379308300002

Searching for a value that doesn't exist:
Set: 0.0002436169999100457
List: 52.67750670600003