我的施工之路雖然艱辛，卻有讀者們陪伴

Python 常用數據結構

此專題《盤點Python10大常用數據結構》目錄：

• 學習目的

• 學習目標

• 1 list

• 2 tuple

• 3 set

• 4 dict

• 5 deque

• 6 Counter

• 7 OrderedDict

• 8 heapq

• 9 defaultdict

• 10 ChainMap

• 總結

學習目的

這個專題，盡量使用最精簡的文字，借助典型案例盤點Python常用的數據結構。

如果你還處于Python入門階段，通常只需掌握list、tuple、set、dict這類數據結構，做到靈活使用即可。

然而，隨著學習的深入，平時遇到實際場景變復雜，很有必要去了解Python內置的更加強大的數據結構deque、heapq、Counter、OrderedDict、defaultDict、ChainMap，掌握它們，往往能讓你少寫一些代碼且能更加高效的實現功能。

學習目標

學習數據結構第一階段：掌握它們的基本用法，使用它們解決一些基本問題；

學習第二階段：知道何種場景選用哪種最恰當的數據結構，去解決題問題；

學習第三階段：了解內置數據結構的背后源碼實現，與《算法和數據結構》這門學問里的知識聯系起來，打通任督二脈。

下面根據定義的這三個階段，總結以下10種最常用的數據結構：

1 list

基本用法 廢話不多說，在前面單獨有一個專題詳述了list的使用。

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

實現原理 list對應數據結構的線性表，列表長度在初始狀態時無需指定，當插入元素超過初始長度后再啟動動態擴容，刪除時尤其位于列表開始處元素，時間復雜度為O(n)

2 tuple

元組是一類不允許添加刪除元素的特殊列表，也就是一旦創建后續決不允許增加、刪除、修改。

基本用法 元組大量使用在打包和解包處，如函數有多個返回值時打包為一個元組，賦值到等號左側變量時解包。

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

實際創建一個元組實例

使用場景 如果非常確定你的對象后面不會被修改，則可以大膽使用元組。為什么？因為相比于list, tuple實例更加節省內存，這點尤其重要。

In?[24]:?from?sys?import?getsizeof??????????????????????????????????????????????In?[25]:?getsizeof(list())?????????????????????????????????????????????????????? Out[25]:?72?#?一個list實例占用72個字節In?[26]:?getsizeof(tuple())????????????????????????????????????????????????????? Out[26]:?56?#?一個tuple實例占用56個字節

所以創建100個實例，tuple能節省1K多字節。

3 set

基本用法 set是一種里面不能含有重復元素的數據結構，這種特性天然的使用于列表的去重。

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

除此之外，還有知道set結構可用于兩個set實例的求交集、并集、差集等操作。

In?[29]:?a?=?{2,3,5}????????????????????????????????????????????????????????????In?[30]:?b?=?{3,4,6,2}??????????????????????????????????????????????????????????In?[31]:?a.interp(b)?#?求交集?????????????????????????????????????????????????????? Out[31]:?{2,?3}

使用場景 如果只是想緩存某些元素值，且要求元素值不能重復時，適合選用此結構。并且set內允許增刪元素，且效率很高。

實現原理 set在內部將值哈希為索引，然后按照索引去獲取數據，因此刪除、增加、查詢元素效果都很高。

4 dict

基本用法 dict 是Python中使用最頻繁的數據結構之一，字典創建由通過dict函數、{}寫法、字典生成式等，增刪查元素效率都很高。

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

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

同時，Python類中屬性值等信息也都是緩存在__dict__這個字典型數據結構中。

但是值得注意，dict占用字節數是list、tuple的3、4倍，因此對內存要求苛刻的場景要慎重考慮。

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

實現原理 字典是一種哈希表，同時保存了鍵值對。

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

5 deque

基本用法 deque 雙端隊列，基于list優化了列表兩端的增刪數據操作?；居梅?#xff1a;

from?collections?import?dequeIn?[3]:?d?=?deque([3,2,4,0])????????????????????????????????????????????????????In?[4]:?d.popleft()?#?左側移除元素，O(1)時間復雜度???????????????????????????????????????????????????????????? Out[4]:?3In?[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]:?640In?[10]:?sys.getsizeof(list())?????????????????????????????????????????????????? Out[10]:?72

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

6 Counter

基本用法 Counter一種繼承于dict用于統計元素個數的數據結構，也稱為bag 或 multiset. 基本用法：

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

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

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

實現原理 Counter實現基于dict，它將元素存儲于keys上，出現次數為values.

7 OrderedDict

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

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.

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

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

8 heapq

基本用法 基于list優化的一個數據結構：堆隊列，也稱為優先隊列。堆隊列特點在于最小的元素總是在根結點：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]

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

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

9 defaultdict

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

基本dict鍵的值沒有一個默認數據類型，如果值為list，必須要手動創建：

words=['book','nice','great','book'] d?=?{} for?i,word?in?enumerate(words):if?word?in?d:d[word].append(i)else:d[word]=[i]?#?顯示的創建一個list

但是使用defaultdict：

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

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

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

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

10 ChainMap

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

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的鍵值變為20???????????????????????????????????????????????????????????????????? Out[89]:?{'a':?2,?'c':?3,?'b':?2,?'d':?20}

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

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

總結

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

當下定決心真心要為讀者們奉獻一些精品原創，且受到讀者們的積極點贊、在看、轉發反饋時，我將會有更大的動力持續的寫下去。希望此專題對大家有幫助，歡迎點贊、在看、轉發。

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯獲取一折本站知識星球優惠券，復制鏈接直接打開：https://t.zsxq.com/662nyZF本站qq群1003271085。加入微信群請掃碼進群（如果是博士或者準備讀博士請說明）：

總結

以上是生活随笔為你收集整理的【Python基础】盘点 Python 10 大常用数据结构（下篇）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。