python

python 常见问答题

Continuous update :D

Posted by kevin on July 16, 2022

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

CATALOG
    FEATURED TAGS
    GitHub git markdown say something 单片机 ROM 中断 linux shell ssh MatLab Regular Expression C Programming cpp python algorithm security Reverse Engineering writeup ctf machine learning reading notes deep learning JavaScript OpenCV Machine Vision php troubleshoot sql nginx base64 Forensics router web XSS docker curl computer network LaTeX iptables sqlmap sql injection object detection paper job pytorch matplotlib blog socket torchscript weakly supervised image matting model deployment onnx mmdetection MOT macOS tools mmcv
    FRIENDS