字典也是python中的一個(gè)常用數(shù)據(jù)結(jié)構(gòu)睦授。字典的 get 和 set 操作都是 O(1)伊约。另一個(gè)重要的操作是 contains劈狐，檢查一個(gè)鍵是否在字典中也是 O(1)疙咸。這是非常重要的一個(gè)性質(zhì)尤蛮。
contains操作在列表與字典間的比較
我們將在實(shí)驗(yàn)中列出一系列數(shù)字媳友。然后隨機(jī)選擇數(shù)字，并檢查數(shù)字是否在列表和字典中产捞。
import matplotlib.pyplot as plt
from timeit import Timer
import random
list_length = [] ##記錄數(shù)據(jù)總量
list_list = [] ##記錄列表查詢時(shí)間
list_dict = [] ##記錄字典查詢時(shí)間
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 ##釋放列表的存儲(chǔ)空間
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()
運(yùn)行結(jié)果如下：
可以看出醇锚，在此過程中，列表越大坯临，確定列表中是否包含任意一個(gè)數(shù)字應(yīng)該花費(fèi)的時(shí)間越長(zhǎng)焊唬；而同樣的操作在字典中花費(fèi)的時(shí)間是恒定的。從圖中也可以確認(rèn)列表的 contains 操作符是 O(n)看靠，字典的 contains 操作符是 O(1)赶促。
python中字典主要操作的時(shí)間復(fù)雜度（來自網(wǎng)絡(luò)）：
