比较Python中列表和集合查找的效率

Python中，列表和集合的查找速率在大数据量的情况下，相差非常大。设置实验来验证这一点。

实验设置

为了比较查找时间，我们创建了一个包含一百万个元素的列表和一个集合。我们要查找的元素是这些集合中的最后一个元素。使用timeit模块测量执行查找操作1000次所需的时间。

import timeit

# 创建一个包含一百万个元素的列表和集合
num_elements = 1000000
elements = list(range(num_elements))
element_set = set(elements)

# 要查找的元素
search_element = num_elements - 1

# 测量列表查询的时间
list_time = timeit.timeit(stmt=f'{search_element} in elements', globals=globals(), number=1000)

# 测量集合查询的时间
set_time = timeit.timeit(stmt=f'{search_element} in element_set', globals=globals(), number=1000)

print(f'List lookup time: {list_time} seconds')
print(f'Set lookup time: {set_time} seconds')
print(f'Set lookup is {list_time / set_time:.2f} times faster than list lookup')

实验结果

程序输出如下：

List lookup time: 6.4358711000022595 seconds
Set lookup time: 2.970000059576705e-05 seconds
Set lookup is 216695.99 times faster than list lookup

可以看到，当前数量的查找，集合查找是列表查找速度的21W倍！

理解列表和集合查找

列表:

• Python中的列表是动态数组。
• 在列表中查找元素需要遍历每个元素，直到找到目标元素。
• 该操作的时间复杂度为O(n)，其中n是列表中的元素数量。

集合:

• Python中的集合使用哈希表实现。
• 在集合中查找元素涉及计算元素的哈希值并直接查找。
• 该操作的平均时间复杂度为O(1)，由于哈希表的直接访问。