上篇文章中4種數(shù)據(jù)結構相信大家都已經比較熟悉，因此我言簡意賅的介紹一遍。接下來再詳細的介紹下面6種數(shù)據(jù)結構及各自使用場景，會列舉更多的例子。

[[335960]]

5. deque

基本用法 deque 雙端隊列，基于list優(yōu)化了列表兩端的增刪數(shù)據(jù)操作?；居梅ǎ?/p>

from collections import deque 
 
In [3]: d = deque([3,2,4,0])                                                     
 
In [4]: d.popleft() # 左側移除元素，O(1)時間復雜度                                                             
Out[4]: 3 
 
In [5]: d.appendleft(3) # 左側添加元素，O(1)時間復雜度                                                        
 
In [6]: d                                                                        
Out[6]: deque([3, 2, 4, 0]) 

使用場景：list左側添加刪除元素的時間復雜度都為O(n)，所以在Python模擬隊列時切忌使用list，相反使用deque雙端隊列非常適合頻繁在列表兩端操作的場景。但是，加強版的deque犧牲了空間復雜度，所以嵌套deque就要仔細trade-off：

In [9]: sys.getsizeof(deque())                                                   
Out[9]: 640 
 
In [10]: sys.getsizeof(list())                                                   
Out[10]: 72 

實現(xiàn)原理：cpython實現(xiàn)deque使用默認長度64的數(shù)組，每次從左側移除1個元素，leftindex加1，如果超過64釋放原來的內存塊，再重新申請64長度的數(shù)組，并使用雙端鏈表block管理內存塊。

6. Counter

基本用法：Counter一種繼承于dict用于統(tǒng)計元素個數(shù)的數(shù)據(jù)結構，也稱為bag 或 multiset. 基本用法：

from collections import Counter 
In [14]: c = Counter([1,3,2,3,4,2,2]) # 統(tǒng)計每個元素的出現(xiàn)次數(shù) 
In [17]: c                                                                       
Out[17]: Counter({1: 1, 3: 2, 2: 3, 4: 1}) 
 
# 除此之外，還可以統(tǒng)計最常見的項 
# 如統(tǒng)計第1最常見的項，返回元素及其次數(shù)的元組 
In [16]: c.most_common(1)                                                        
Out[16]: [(2, 3)] 

使用場景：基本的dict能解決的問題就不要用Counter，但如遇到統(tǒng)計元素出現(xiàn)頻次的場景，就不要自己去用dict實現(xiàn)了，果斷選用Counter.

需要注意，Counter統(tǒng)計的元素要求可哈希(hashable)，換句話說如果統(tǒng)計list的出現(xiàn)次數(shù)就不可行，不過list轉化為tuple不就可哈希了嗎.

實現(xiàn)原理：Counter實現(xiàn)基于dict，它將元素存儲于keys上，出現(xiàn)次數(shù)為values.

7. OrderedDict

基本用法 繼承于dict，能確保keys值按照順序取出來的數(shù)據(jù)結構，基本用法：

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 

使用場景：基本的dict無法保證順序，keys映射為哈希值，而此值不是按照順序存儲在散列表中的。所以遇到要確保字典keys有序場景，就要使用OrderedDict.

實現(xiàn)原理 ：你一定會好奇OrderedDict如何確保keys順序的，翻看cpython看到它里面維護著一個雙向鏈表self.__root，它維護著keys的順序。既然使用雙向鏈表，細心的讀者可能會有疑問：刪除鍵值對如何保證O(1)時間完成?

cpython使用空間換取時間的做法，內部維護一個self.__map字典，鍵為key，值為指向雙向鏈表節(jié)點的link. 這樣在刪除某個鍵值對時，通過__map在O(1)內找到link，然后O(1)內從雙向鏈表__root中摘除。

8. heapq

基本用法 基于list優(yōu)化的一個數(shù)據(jù)結構：堆隊列，也稱為優(yōu)先隊列。堆隊列特點在于最小的元素總是在根結點：heap[0] 基本用法：

import heapq 
In [41]: a = [3,1,4,5,2,1]                                                       
 
In [42]: heapq.heapify(a) # 對a建堆，建堆后完成對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個最大元素                                                     
Out[46]: [5, 4, 3] 
 
In [47]: heapq.nsmallest(3,a) # a的前3個最小元素                                                   
Out[47]: [1, 1, 2] 

使用場景：如果想要統(tǒng)計list中前幾個最小(大)元素，那么使用heapq很方便，同時它還提供合并多個有序小list為大list的功能。

基本原理：堆是一個二叉樹，它的每個父節(jié)點的值都只會小于或大于所有孩子節(jié)點(的值)，原理與堆排序極為相似。

9. defaultdict

基本用法 defaultdict是一種帶有默認工廠的dict，如果對設計模式不很了解的讀者可能會很疑惑工廠這個詞，準確來說工廠全稱為對象工廠。下面體會它的基本用法。

基本dict鍵的值沒有一個默認數(shù)據(jù)類型，如果值為list，必須要手動創(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)建一個list 

但是使用defaultdict：

from collections import defaultdict 
d = defaultdict(list) # 創(chuàng)建字典值默認為list的字典 
for i,word in enumerate(words): 
    d[word] = i  

省去一層if邏輯判斷，代碼更加清晰。上面defaultdict(list)這行代碼默認創(chuàng)建值為list的字典，還可以構造defaultdict(set), defaultdict(dict)等等，這種模式就是對象工廠，工廠里能制造各種對象：list,set,dict...

使用場景：上面已經說的很清楚，適用于鍵的值必須指定一個默認值的場景，如鍵的值為list,set,dict等。

實現(xiàn)原理：基本原理就是調用工廠函數(shù)去提供缺失的鍵的值。后面設計模式專題再詳細探討。

10. ChainMap

基本用法 如果有多個dict想要合并為一個大dict，那么ChainMap將是你的選擇，它的方便性體現(xiàn)在同步更改。具體來看例子：

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后返回一個大dict視圖，如果修改其對應鍵值對，原小dict也會改變：

In [86]: dm.maps  # 返回一個字典list                                                                
Out[86]: [{'a': 2, 'c': 3, 'b': 2, 'd': 10}, {'d': 1, 'e': 5}] 
 
In [87]: dm.maps[0]['d']=20   # 修改第一個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} 

使用場景 ：具體使用場景是我們有多個字典或者映射，想把它們合并成為一個單獨的映射，有讀者可能說可以用update進行合并，這樣做的問題就是新建了一個內存結構，除了浪費空間外，還有一個缺點就是我們對新字典的更改不會同步到原字典上。

實現(xiàn)原理：通過maps便能觀察出ChainMap聯(lián)合多個小dict裝入list中，實際確實也是這樣實現(xiàn)的，內部維護一個lis實例，其元素為小dict.

總結

以上就是Python常用的10種數(shù)據(jù)結構，4種常用的基本結構，6種基于它們優(yōu)化的適應于特定場景的結構，對它們的學習我將它們總結為三步。