python 常见问答题

棒棒鸡不棒

发布于 2022-09-08 11:50:32

4450

发布于 2022-09-08 11:50: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)