【Python】（四）Python中的字典

字典也是python中的一个常用数据结构。字典的 get 和 set 操作都是 O(1)。另一个重要的操作是 contains，检查一个键是否在字典中也是 O(1)。这是非常重要的一个性质。

contains操作在列表与字典间的比较

我们将在实验中列出一系列数字。然后随机选择数字，并检查数字是否在列表和字典中。

import matplotlib.pyplot as plt
from timeit import Timer
import random

list_length = [] ##记录数据总量
list_list = [] ##记录列表查询时间
list_dict = [] ##记录字典查询时间

for i in range(10000,1000001,20000):
    list_length.append(i)
    print(i)
    
    x = list(range(i)) ##建立列表
    t_list = Timer("random.randrange(%d) in x"%i, "from __main__ import random,x")
    list_list.append(t_list.timeit(number=1000))
    del x ##释放列表的存储空间
    
    y = {j:None for j in range(i)} ##建立字典
    t_dict = Timer("random.randrange(%d) in y"%i, "from __main__ import random,y")
    list_dict.append(t_dict.timeit(number=1000))
    del y

plt.figure(figsize=(8,4))
plt.plot(list_length,list_list,label="$List$",color="red",linewidth=2)
plt.plot(list_length,list_dict,"b--",label="$Dictionary$")
plt.xlabel("List Length")
plt.ylabel("ms")
plt.legend()
plt.show()

运行结果如下：

可以看出，在此过程中，列表越大，确定列表中是否包含任意一个数字应该花费的时间越长；而同样的操作在字典中花费的时间是恒定的。从图中也可以确认列表的 contains 操作符是 O(n)，字典的 contains 操作符是 O(1)。

python中字典主要操作的时间复杂度（来自网络）：