提供了Python编程的基础技术教程

Python程序教程

您现在的位置是：首页 >  Python

当前栏目

python 常见问答题

python,常见,问答题
2025-04-07 09:01:32 时间

1. list set dict 的查询效率

在一个长度为一百万（1000000）的列表中搜索某个元素是否存在，用哪个数据结构的速度是最快的呢

答案是 set 最快，dict 其次，list 是最慢的。

set 对列表进行了去重，底层相当于是一颗红黑树，复杂度 O(logn)；

dict 对 key 进行了 hash，然后再通过 hash 的结果进行二分查找从而确定是否有这个 key，其查询的复杂度是 O(logn)，并不是的 O(1)，O(1) 是已知存在 key 的情况下查 value 的情况；

list 就是纯纯的 O(n)。

import random
import time

# 生成随机数
nums = random.sample(range(1,1000000000), 10000000)
# print(nums)

my_list = []
my_set = set()
my_dict = {}

# 赋值
my_list.extend(nums)
my_set = set(nums)
my_dict = { i : 1 for i in nums}

# set查询效率
start_time = time.time()
for i in range(10000000):
    flag = i in my_set
print(time.time() - start_time)

# dict查询效率
start_time = time.time()
for i in range(10000000):
    flag = i in my_dict
print(time.time() - start_time)

# list查找效率
start_time = time.time()
for i in range(10000000):
    flag = i in my_list
print(time.time() - start_time)

reference: https://blog.csdn.net/weixin_48629601/article/details/107532754

相关文章