盤(pán)點(diǎn) Python 10 大常用數(shù)據(jù)結(jié)構(gòu)（下篇）

學(xué)習(xí)目的

這個(gè)專(zhuān)題，盡量使用最精簡(jiǎn)的文字，借助典型案例盤(pán)點(diǎn)Python常用的數(shù)據(jù)結(jié)構(gòu)。

如果你還處于Python入門(mén)階段，通常只需掌握list、tuple、set、dict這類(lèi)數(shù)據(jù)結(jié)構(gòu)，做到靈活使用即可。

然而，隨著學(xué)習(xí)的深入，平時(shí)遇到實(shí)際場(chǎng)景變復(fù)雜，很有必要去了解Python內(nèi)置的更加強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)deque、heapq、Counter、OrderedDict、defaultDict、ChainMap，掌握它們，往往能讓你少寫(xiě)一些代碼且能更加高效的實(shí)現(xiàn)功能。

學(xué)習(xí)目標(biāo)

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)第一階段：掌握它們的基本用法，使用它們解決一些基本問(wèn)題；

學(xué)習(xí)第二階段：知道何種場(chǎng)景選用哪種最恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，去解決題問(wèn)題；

學(xué)習(xí)第三階段：了解內(nèi)置數(shù)據(jù)結(jié)構(gòu)的背后源碼實(shí)現(xiàn)，與《算法和數(shù)據(jù)結(jié)構(gòu)》這門(mén)學(xué)問(wèn)里的知識(shí)聯(lián)系起來(lái)，打通任督二脈。

下面根據(jù)定義的這三個(gè)階段，總結(jié)以下10種最常用的數(shù)據(jù)結(jié)構(gòu)：

1 list

基本用法 廢話不多說(shuō)，在前面單獨(dú)有一個(gè)專(zhuān)題詳述了list的使用。

使用場(chǎng)景 list 使用在需要查詢、修改的場(chǎng)景，極不擅長(zhǎng)需要頻繁插入、刪除元素的場(chǎng)景。

實(shí)現(xiàn)原理 list對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)的線性表，列表長(zhǎng)度在初始狀態(tài)時(shí)無(wú)需指定，當(dāng)插入元素超過(guò)初始長(zhǎng)度后再啟動(dòng)動(dòng)態(tài)擴(kuò)容，刪除時(shí)尤其位于列表開(kāi)始處元素，時(shí)間復(fù)雜度為O(n)

2 tuple

元組是一類(lèi)不允許添加刪除元素的特殊列表，也就是一旦創(chuàng)建后續(xù)決不允許增加、刪除、修改。

基本用法 元組大量使用在打包和解包處，如函數(shù)有多個(gè)返回值時(shí)打包為一個(gè)元組，賦值到等號(hào)左側(cè)變量時(shí)解包。

In?[22]:?t=1,2,3?????????????????????????????????????????
In?[23]:?type(t)??????????????????????????????
Out[23]:?tuple

實(shí)際創(chuàng)建一個(gè)元組實(shí)例

使用場(chǎng)景 如果非常確定你的對(duì)象后面不會(huì)被修改，則可以大膽使用元組。為什么？因?yàn)橄啾扔趌ist, tuple實(shí)例更加節(jié)省內(nèi)存，這點(diǎn)尤其重要。

In?[24]:?from?sys?import?getsizeof??????????????????????????????????????????????

In?[25]:?getsizeof(list())??????????????????????????????????????????????????????
Out[25]:?72?#?一個(gè)list實(shí)例占用72個(gè)字節(jié)

In?[26]:?getsizeof(tuple())?????????????????????????????????????????????????????
Out[26]:?56?#?一個(gè)tuple實(shí)例占用56個(gè)字節(jié)

所以創(chuàng)建100個(gè)實(shí)例，tuple能節(jié)省1K多字節(jié)。

3 set

基本用法 set是一種里面不能含有重復(fù)元素的數(shù)據(jù)結(jié)構(gòu)，這種特性天然的使用于列表的去重。

In?[27]:?a=[3,2,5,2,5,3]????????????????????????????????????????????????????????

In?[28]:?set(a)?????????????????????????????????????????????????????????????????
Out[28]:?{2,?3,?5}

除此之外，還有知道set結(jié)構(gòu)可用于兩個(gè)set實(shí)例的求交集、并集、差集等操作。

In?[29]:?a?=?{2,3,5}????????????????????????????????????????????????????????????

In?[30]:?b?=?{3,4,6,2}??????????????????????????????????????????????????????????

In?[31]:?a.intersection(b)?#?求交集??????????????????????????????????????????????????????
Out[31]:?{2,?3}

使用場(chǎng)景 如果只是想緩存某些元素值，且要求元素值不能重復(fù)時(shí)，適合選用此結(jié)構(gòu)。并且set內(nèi)允許增刪元素，且效率很高。

實(shí)現(xiàn)原理 set在內(nèi)部將值哈希為索引，然后按照索引去獲取數(shù)據(jù)，因此刪除、增加、查詢?cè)匦Ч己芨摺?/p>

4 dict

基本用法 dict 是Python中使用最頻繁的數(shù)據(jù)結(jié)構(gòu)之一，字典創(chuàng)建由通過(guò)dict函數(shù)、{}寫(xiě)法、字典生成式等，增刪查元素效率都很高。

d?=?{'a':1,'b':2}?#?{}創(chuàng)建字典

#?列表生成式
In?[38]:?d?=?{a:b?for?a,b?in?zip(['a','b'],[1,2])}??????????????????????????????
In?[39]:?d??????????????????????????????????????????????????????????????????????
Out[39]:?{'a':?1,?'b':?2}

使用場(chǎng)景 字典尤其適合在查詢多的場(chǎng)景，時(shí)間復(fù)雜度為O(1). 如leetcode第一題求解兩數(shù)之和時(shí)，就會(huì)使用到dict的O(1)查詢時(shí)間復(fù)雜度。

同時(shí)，Python類(lèi)中屬性值等信息也都是緩存在__dict__這個(gè)字典型數(shù)據(jù)結(jié)構(gòu)中。

但是值得注意，dict占用字節(jié)數(shù)是list、tuple的3、4倍，因此對(duì)內(nèi)存要求苛刻的場(chǎng)景要慎重考慮。

In?[40]:?getsizeof(dict())??????????????????????????????????????????????????????
Out[40]:?248

實(shí)現(xiàn)原理 字典是一種哈希表，同時(shí)保存了鍵值對(duì)。

以上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ù)操作?；居梅ǎ?/p>

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.