盤(pán)點(diǎn) Python 10 大常用數(shù)據(jù)結(jié)構(gòu)（下篇）
上篇文章中4種數(shù)據(jù)結(jié)構(gòu)相信大家都已經(jīng)比較熟悉，因此我言簡(jiǎn)意賅的介紹一遍。接下來(lái)再詳細(xì)的介紹下面6種數(shù)據(jù)結(jié)構(gòu)及各自使用場(chǎng)景，會(huì)列舉更多的例子。
5. deque
基本用法 deque 雙端隊(duì)列，基于list優(yōu)化了列表兩端的增刪數(shù)據(jù)操作。基本用法：
- from collections import deque
- In [3]: d = deque([3,2,4,0])
- In [4]: d.popleft() # 左側(cè)移除元素，O(1)時(shí)間復(fù)雜度
- Out[4]: 3
- In [5]: d.appendleft(3) # 左側(cè)添加元素，O(1)時(shí)間復(fù)雜度
- In [6]: d
- Out[6]: deque([3, 2, 4, 0])
使用場(chǎng)景：list左側(cè)添加刪除元素的時(shí)間復(fù)雜度都為O(n)，所以在Python模擬隊(duì)列時(shí)切忌使用list，相反使用deque雙端隊(duì)列非常適合頻繁在列表兩端操作的場(chǎng)景。但是，加強(qiáng)版的deque犧牲了空間復(fù)雜度，所以嵌套deque就要仔細(xì)trade-off：
- In [9]: sys.getsizeof(deque())
- Out[9]: 640
- In [10]: sys.getsizeof(list())
- Out[10]: 72
實(shí)現(xiàn)原理：cpython實(shí)現(xiàn)deque使用默認(rèn)長(zhǎng)度64的數(shù)組，每次從左側(cè)移除1個(gè)元素，leftindex加1，如果超過(guò)64釋放原來(lái)的內(nèi)存塊，再重新申請(qǐng)64長(zhǎng)度的數(shù)組，并使用雙端鏈表block管理內(nèi)存塊。
6. Counter
基本用法：Counter一種繼承于dict用于統(tǒng)計(jì)元素個(gè)數(shù)的數(shù)據(jù)結(jié)構(gòu)，也稱(chēng)為bag 或 multiset. 基本用法：
- from collections import Counter
- In [14]: c = Counter([1,3,2,3,4,2,2]) # 統(tǒng)計(jì)每個(gè)元素的出現(xiàn)次數(shù)
- In [17]: c
- Out[17]: Counter({1: 1, 3: 2, 2: 3, 4: 1})
- # 除此之外，還可以統(tǒng)計(jì)最常見(jiàn)的項(xiàng)
- # 如統(tǒng)計(jì)第1最常見(jiàn)的項(xiàng)，返回元素及其次數(shù)的元組
- In [16]: c.most_common(1)
- Out[16]: [(2, 3)]
使用場(chǎng)景：基本的dict能解決的問(wèn)題就不要用Counter，但如遇到統(tǒng)計(jì)元素出現(xiàn)頻次的場(chǎng)景，就不要自己去用dict實(shí)現(xiàn)了，果斷選用Counter.
需要注意，Counter統(tǒng)計(jì)的元素要求可哈希(hashable)，換句話說(shuō)如果統(tǒng)計(jì)list的出現(xiàn)次數(shù)就不可行，不過(guò)list轉(zhuǎn)化為tuple不就可哈希了嗎.
實(shí)現(xiàn)原理：Counter實(shí)現(xiàn)基于dict，它將元素存儲(chǔ)于keys上，出現(xiàn)次數(shù)為values.
7. OrderedDict
基本用法 繼承于dict，能確保keys值按照順序取出來(lái)的數(shù)據(jù)結(jié)構(gòu)，基本用法：
- In [25]: from collections import OrderedDict
- In [26]: od = OrderedDict({'c':3,'a':1,'b':2})
- In [27]: for k,v in od.items():
- ...: print(k,v)
- ...:
- c 3
- a 1
- b 2
使用場(chǎng)景：基本的dict無(wú)法保證順序，keys映射為哈希值，而此值不是按照順序存儲(chǔ)在散列表中的。所以遇到要確保字典keys有序場(chǎng)景，就要使用OrderedDict.
實(shí)現(xiàn)原理 ：你一定會(huì)好奇OrderedDict如何確保keys順序的，翻看cpython看到它里面維護(hù)著一個(gè)雙向鏈表self.__root，它維護(hù)著keys的順序。既然使用雙向鏈表，細(xì)心的讀者可能會(huì)有疑問(wèn)：刪除鍵值對(duì)如何保證O(1)時(shí)間完成?
cpython使用空間換取時(shí)間的做法，內(nèi)部維護(hù)一個(gè)self.__map字典，鍵為key，值為指向雙向鏈表節(jié)點(diǎn)的link. 這樣在刪除某個(gè)鍵值對(duì)時(shí)，通過(guò)__map在O(1)內(nèi)找到link，然后O(1)內(nèi)從雙向鏈表__root中摘除。
8. heapq
基本用法 基于list優(yōu)化的一個(gè)數(shù)據(jù)結(jié)構(gòu)：堆隊(duì)列，也稱(chēng)為優(yōu)先隊(duì)列。堆隊(duì)列特點(diǎn)在于最小的元素總是在根結(jié)點(diǎn)：heap[0] 基本用法：
- import heapq
- In [41]: a = [3,1,4,5,2,1]
- In [42]: heapq.heapify(a) # 對(duì)a建堆，建堆后完成對(duì)a的就地排序
- In [43]: a[0] # a[0]一定是最小元素
- In [44]: a
- Out[44]: [1, 1, 3, 5, 2, 4]
- In [46]: heapq.nlargest(3,a) # a的前3個(gè)最大元素
- Out[46]: [5, 4, 3]
- In [47]: heapq.nsmallest(3,a) # a的前3個(gè)最小元素
- Out[47]: [1, 1, 2]
使用場(chǎng)景：如果想要統(tǒng)計(jì)list中前幾個(gè)最小(大)元素，那么使用heapq很方便，同時(shí)它還提供合并多個(gè)有序小list為大list的功能。
基本原理：堆是一個(gè)二叉樹(shù)，它的每個(gè)父節(jié)點(diǎn)的值都只會(huì)小于或大于所有孩子節(jié)點(diǎn)(的值)，原理與堆排序極為相似。
9. defaultdict
基本用法 defaultdict是一種帶有默認(rèn)工廠的dict，如果對(duì)設(shè)計(jì)模式不很了解的讀者可能會(huì)很疑惑工廠這個(gè)詞，準(zhǔn)確來(lái)說(shuō)工廠全稱(chēng)為對(duì)象工廠。下面體會(huì)它的基本用法。
基本dict鍵的值沒(méi)有一個(gè)默認(rèn)數(shù)據(jù)類(lèi)型，如果值為list，必須要手動(dòng)創(chuàng)建：
- words=['book','nice','great','book']
- d = {}
- for i,word in enumerate(words):
- if word in d:
- d[word].append(i)
- else:
- d[word]=[i] # 顯示的創(chuàng)建一個(gè)list
但是使用defaultdict：
- from collections import defaultdict
- d = defaultdict(list) # 創(chuàng)建字典值默認(rèn)為list的字典
- for i,word in enumerate(words):
- d[word] = i
省去一層if邏輯判斷，代碼更加清晰。上面defaultdict(list)這行代碼默認(rèn)創(chuàng)建值為list的字典，還可以構(gòu)造defaultdict(set), defaultdict(dict)等等，這種模式就是對(duì)象工廠，工廠里能制造各種對(duì)象：list,set,dict...
使用場(chǎng)景：上面已經(jīng)說(shuō)的很清楚，適用于鍵的值必須指定一個(gè)默認(rèn)值的場(chǎng)景，如鍵的值為list,set,dict等。
實(shí)現(xiàn)原理：基本原理就是調(diào)用工廠函數(shù)去提供缺失的鍵的值。后面設(shè)計(jì)模式專(zhuān)題再詳細(xì)探討。
10. ChainMap
基本用法 如果有多個(gè)dict想要合并為一個(gè)大dict，那么ChainMap將是你的選擇，它的方便性體現(xiàn)在同步更改。具體來(lái)看例子：
- In [55]: from collections import ChainMap
- In [56]: d1 = {'a':1,'c':3,'b':2}
- In [57]: d2 = {'d':1,'e':5}
- In [58]: dm = ChainMap(d1,d2)
- In [59]: dm
- Out[59]: ChainMap({'a': 1, 'c': 3, 'b': 2}, {'d': 1, 'e': 5})
ChainMap后返回一個(gè)大dict視圖，如果修改其對(duì)應(yīng)鍵值對(duì)，原小dict也會(huì)改變：
- In [86]: dm.maps # 返回一個(gè)字典list
- Out[86]: [{'a': 2, 'c': 3, 'b': 2, 'd': 10}, {'d': 1, 'e': 5}]
- In [87]: dm.maps[0]['d']=20 # 修改第一個(gè)dict的鍵等于'd'的值為20
- In [88]: dm
- Out[88]: ChainMap({'a': 2, 'c': 3, 'b': 2, 'd': 20}, {'d': 1, 'e': 5})
- In [89]: d1 # 原小dict的鍵值變?yōu)?0
- Out[89]: {'a': 2, 'c': 3, 'b': 2, 'd': 20}
使用場(chǎng)景 ：具體使用場(chǎng)景是我們有多個(gè)字典或者映射，想把它們合并成為一個(gè)單獨(dú)的映射，有讀者可能說(shuō)可以用update進(jìn)行合并，這樣做的問(wèn)題就是新建了一個(gè)內(nèi)存結(jié)構(gòu)，除了浪費(fèi)空間外，還有一個(gè)缺點(diǎn)就是我們對(duì)新字典的更改不會(huì)同步到原字典上。
實(shí)現(xiàn)原理：通過(guò)maps便能觀察出ChainMap聯(lián)合多個(gè)小dict裝入list中，實(shí)際確實(shí)也是這樣實(shí)現(xiàn)的，內(nèi)部維護(hù)一個(gè)lis實(shí)例，其元素為小dict.
總結(jié)
以上就是Python常用的10種數(shù)據(jù)結(jié)構(gòu)，4種常用的基本結(jié)構(gòu)，6種基于它們優(yōu)化的適應(yīng)于特定場(chǎng)景的結(jié)構(gòu)，對(duì)它們的學(xué)習(xí)我將它們總結(jié)為三步。
