序言

這是 “Python 工匠”系列的第 4 篇文章

原文鏈接：https://www./articles/mastering-container-types/

”容器”這兩個字很少被 Python 技術(shù)文章提起。一看到“容器”,，大家想到的多是那頭藍(lán)色小鯨魚：Docker,，但這篇文章和它沒有任何關(guān)系。本文里的容器,，是 Python 中的一個抽象概念,，是對專門用來裝其他對象的數(shù)據(jù)類型的統(tǒng)稱。

在 Python 中，有四類最常見的內(nèi)建容器類型： 列表（list）,、 元組（tuple）,、 字典（dict）、 集合（set）,。通過單獨(dú)或是組合使用它們，可以高效的完成很多事情,。

Python 語言自身的內(nèi)部實現(xiàn)細(xì)節(jié)也與這些容器類型息息相關(guān),。比如 Python 的類實例屬性、全局變量 globals() 等就都是通過字典類型來存儲的,。

在這篇文章里,，我首先會從容器類型的定義出發(fā)，嘗試總結(jié)出一些日常編碼的最佳實踐,。之后再圍繞各個容器類型提供的特殊機(jī)能,，分享一些編程的小技巧。

當(dāng)我們談?wù)撊萜鲿r,，我們在談些什么,？

我在前面給了“容器”一個簡單的定義：專門用來裝其他對象的就是容器。但這個定義太寬泛了,，無法對我們的日常編程產(chǎn)生什么指導(dǎo)價值,。要真正掌握 Python 里的容器，需要分別從兩個層面入手：

• 底層實現(xiàn)：內(nèi)置容器類型使用了什么數(shù)據(jù)結(jié)構(gòu),？某項操作如何工作,？

• 高層抽象：什么決定了某個對象是不是容器？哪些行為定義了容器,？

下面,，讓我們一起站在這兩個不同的層面上，重新認(rèn)識容器,。

底層看容器

Python 是一門高級編程語言,，它所提供的內(nèi)置容器類型，都是經(jīng)過高度封裝和抽象后的結(jié)果,。和“鏈表”,、“紅黑樹”、“哈希表”這些名字相比,，所有 Python 內(nèi)建類型的名字,，都只描述了這個類型的功能特點(diǎn)，其他人完全沒法只通過這些名字了解它們的哪怕一丁點(diǎn)內(nèi)部細(xì)節(jié),。

這是 Python 編程語言的優(yōu)勢之一,。相比 C 語言這類更接近計算機(jī)底層的編程語言，Python 重新設(shè)計并實現(xiàn)了對編程者更友好的內(nèi)置容器類型，屏蔽掉了內(nèi)存管理等額外工作,。為我們提供了更好的開發(fā)體驗,。

但如果這是 Python 語言的優(yōu)勢的話，為什么我們還要費(fèi)勁去了解容器類型的實現(xiàn)細(xì)節(jié)呢,？答案是：關(guān)注細(xì)節(jié)可以幫助我們編寫出更快的代碼,。

寫更快的代碼

1. 避免頻繁擴(kuò)充列表/創(chuàng)建新列表

所有的內(nèi)建容器類型都不限制容量。如果你愿意,，你可以把遞增的數(shù)字不斷塞進(jìn)一個空列表,，最終撐爆整臺機(jī)器的內(nèi)存。

在 Python 語言的實現(xiàn)細(xì)節(jié)里,，列表的內(nèi)存是按需分配的[注1],，當(dāng)某個列表當(dāng)前擁有的內(nèi)存不夠時，便會觸發(fā)內(nèi)存擴(kuò)容邏輯,。而分配內(nèi)存是一項昂貴的操作,。雖然大部分情況下，它不會對你的程序性能產(chǎn)生什么嚴(yán)重的影響,。但是當(dāng)你處理的數(shù)據(jù)量特別大時,，很容易因為內(nèi)存分配拖累整個程序的性能。

還好,，Python 早就意識到了這個問題,，并提供了官方的問題解決指引，那就是：“變懶”,。

如何解釋“變懶”,？ range() 函數(shù)的進(jìn)化是一個非常好的例子。

在 Python 2 中,，如果你調(diào)用 range(100000000),，需要等待好幾秒才能拿到結(jié)果，因為它需要返回一個巨大的列表,，花費(fèi)了非常多的時間在內(nèi)存分配與計算上,。但在 Python 3 中，同樣的調(diào)用馬上就能拿到結(jié)果,。因為函數(shù)返回的不再是列表,，而是一個類型為 range 的懶惰對象，只有在你迭代它,、或是對它進(jìn)行切片時,，它才會返回真正的數(shù)字給你。

所以說,，為了提高性能,，內(nèi)建函數(shù) range “變懶”了,。而為了避免過于頻繁的內(nèi)存分配，在日常編碼中,，我們的函數(shù)同樣也需要變懶,，這包括：

• 更多的使用 yield 關(guān)鍵字，返回生成器對象

• 盡量使用生成器表達(dá)式替代列表推導(dǎo)表達(dá)式

• 生成器表達(dá)式： (iforinrange(100)) ??

• 列表推導(dǎo)表達(dá)式： [iforinrange(100)]

• 盡量使用模塊提供的懶惰對象：

• 使用 re.finditer 替代 re.findall

• 直接使用可迭代的文件對象： forlineinfp,，而不是 forlineinfp.readlines()

2. 在列表頭部操作多的場景使用 deque 模塊

列表是基于數(shù)組結(jié)構(gòu)（Array）實現(xiàn)的,，當(dāng)你在列表的頭部插入新成員（ list.insert(0,item)）時，它后面的所有其他成員都需要被移動,，操作的時間復(fù)雜度是 O(n),。這導(dǎo)致在列表的頭部插入成員遠(yuǎn)比在尾部追加（ list.append(item) 時間復(fù)雜度為 O(1)）要慢。

如果你的代碼需要執(zhí)行很多次這類操作,，請考慮使用 collections.deque 類型來替代列表。因為 deque 是基于雙端隊列實現(xiàn)的,，無論是在頭部還是尾部追加元素,，時間復(fù)雜度都是 O(1)。

3. 使用集合/字典來判斷成員是否存在

當(dāng)你需要判斷成員是否存在于某個容器時,，用集合比列表更合適,。因為 itemin[...] 操作的時間復(fù)雜度是 O(n)，而 itemin{...} 的時間復(fù)雜度是 O(1),。這是因為字典與集合都是基于哈希表（Hash Table）數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的,。

Hint: 強(qiáng)烈建議閱讀 TimeComplexity - Python Wiki,，了解更多關(guān)于常見容器類型的時間復(fù)雜度相關(guān)內(nèi)容。

如果你對字典的實現(xiàn)細(xì)節(jié)感興趣,，也強(qiáng)烈建議觀看 Raymond Hettinger 的演講 Modern Dictionaries(YouTube)

高層看容器

Python 是一門“鴨子類型”語言：“當(dāng)看到一只鳥走起來像鴨子,、游泳起來像鴨子、叫起來也像鴨子,，那么這只鳥就可以被稱為鴨子,。”所以,，當(dāng)我們說某個對象是什么類型時,，在根本上其實指的是：這個對象滿足了該類型的特定接口規(guī)范，可以被當(dāng)成這個類型來使用,。而對于所有內(nèi)置容器類型來說,，同樣如此。

打開位于 collections 模塊下的 abc（“抽象類 Abstract Base Classes”的首字母縮寫）子模塊,，可以找到所有與容器相關(guān)的接口（抽象類）[注2]定義,。讓我們分別看看那些內(nèi)建容器類型都滿足了什么接口：

• 列表（list）：滿足 Iterable、 Sequence、 MutableSequence 等接口

• 元組（tuple）：滿足 Iterable,、 Sequence

• 字典（dict）：滿足 Iterable,、 Mapping、 MutableMapping [注3]

• 集合（set）：滿足 Iterable,、 Set,、 MutableSet [注4]

每個內(nèi)置容器類型，其實就是滿足了多個接口定義的組合實體,。比如所有的容器類型都滿足 “可被迭代的”（Iterable） 這個接口,，這意味著它們都是“可被迭代”的。但是反過來,，不是所有“可被迭代”的對象都是容器,。就像字符串雖然可以被迭代，但我們通常不會把它當(dāng)做“容器”來看待,。

了解這個事實后,，我們將在 Python 里重新認(rèn)識面向?qū)ο缶幊讨凶钪匾脑瓌t之一：面向接口而非具體實現(xiàn)來編程。

讓我們通過一個例子,，看看如何理解 Python 里的“面向接口編程”,。

寫擴(kuò)展性更好的代碼

某日，我們接到一個需求：有一個列表,，里面裝著很多用戶評論,，為了在頁面正常展示，需要將所有超過一定長度的評論用省略號替代,。

這個需求很好做,，很快我們就寫出了第一個版本的代碼：

# 注：為了加強(qiáng)示例代碼的說明性，本文中的部分代碼片段使用了Python 3.5
# 版本添加的 Type Hinting 特性

def add_ellipsis(comments: typing.List[str], max_length: int = 12):
    '''如果評論列表里的內(nèi)容超過 max_length,，剩下的字符用省略號代替
    '''
    index = 0
    for comment in comments:
        comment = comment.strip()
        if len(comment) > max_length:
            comments[index] = comment[:max_length] + '...'
        index += 1
    return comments


comments = [
    'Implementation note',
    'Changed',
    'ABC for generator',
]
print('\n'.join(add_ellipsis(comments)))
# OUTPUT:
# Implementati...
# Changed
# ABC for gene...

上面的代碼里,， add_ellipsis 函數(shù)接收一個列表作為參數(shù)，然后遍歷它,，替換掉需要修改的成員,。這一切看上去很合理，因為我們接到的最原始需求就是：“有一個 列表,，里面...”,。但如果有一天，我們拿到的評論不再是被繼續(xù)裝在列表里,，而是在不可變的元組里呢,？

那樣的話，現(xiàn)有的函數(shù)設(shè)計就會逼迫我們寫出 add_ellipsis(list(comments)) 這種即慢又難看的代碼了,。??

面向容器接口編程

我們需要改進(jìn)函數(shù)來避免這個問題,。因為 add_ellipsis 函數(shù)強(qiáng)依賴了列表類型,，所以當(dāng)參數(shù)類型變?yōu)樵M時，現(xiàn)在的函數(shù)就不再適用了（原因：給 comments[index] 賦值的地方會拋出 TypeError 異常）,。如何改善這部分的設(shè)計,？秘訣就是：讓函數(shù)依賴“可迭代對象”這個抽象概念，而非實體列表類型,。

使用生成器特性,，函數(shù)可以被改成這樣：

在新函數(shù)里,，我們將依賴的參數(shù)類型從列表改成了可迭代的抽象類,。這樣做有很多好處，一個最明顯的就是：無論評論是來自列表,、元組或是某個文件,，新函數(shù)都可以輕松滿足：

# 處理放在元組里的評論
comments = ('Implementation note', 'Changed', 'ABC for generator')
print('\n'.join(add_ellipsis_gen(comments)))

# 處理放在文件里的評論
with open('comments') as fp:
    for comment in add_ellipsis_gen(fp):
        print(comment)

將依賴由某個具體的容器類型改為抽象接口后，函數(shù)的適用面變得更廣了,。除此之外,，新函數(shù)在執(zhí)行效率等方面也都更有優(yōu)勢。現(xiàn)在讓我們再回到之前的問題,。從高層來看,，什么定義了容器,？

答案是：各個容器類型實現(xiàn)的接口協(xié)議定義了容器,。不同的容器類型在我們的眼里，應(yīng)該是 是否可以迭代,、 是否可以修改,、 有沒有長度 等各種特性的組合。我們需要在編寫相關(guān)代碼時,，更多的關(guān)注容器的抽象屬性,，而非容器類型本身，這樣可以幫助我們寫出更優(yōu)雅,、擴(kuò)展性更好的代碼,。

Hint：在 itertools 內(nèi)置模塊里可以找到更多關(guān)于處理可迭代對象的寶藏。

常用技巧

1. 使用元組改善分支代碼

有時,，我們的代碼里會出現(xiàn)超過三個分支的 if/else ,。就像下面這樣：

上面這個函數(shù)挑不出太多毛病,，很多很多人都會寫出類似的代碼,。但是，如果你仔細(xì)觀察它,，可以在分支代碼部分找到一些明顯的“邊界”,。比如,，當(dāng)函數(shù)判斷某個時間是否應(yīng)該用“秒數(shù)”展示時，用到了 60,。而判斷是否應(yīng)該用分鐘時,，用到了 3600。

從邊界提煉規(guī)律是優(yōu)化這段代碼的關(guān)鍵,。如果我們將所有的這些邊界放在一個有序元組中,，然后配合二分查找模塊 bisect。整個函數(shù)的控制流就能被大大簡化：

import bisect


# BREAKPOINTS 必須是已經(jīng)排好序的,，不然無法進(jìn)行二分查找
BREAKPOINTS = (1, 60, 3600, 3600 * 24)
TMPLS = (
    # unit, template
    (1, 'less than 1 second ago'),
    (1, '{units} seconds ago'),
    (60, '{units} minutes ago'),
    (3600, '{units} hours ago'),
    (3600 * 24, '{units} days ago'),
)


def from_now(ts):
    '''接收一個過去的時間戳,，返回距離當(dāng)前時間的相對時間文字描述
    '''
    seconds_delta = int(time.time() - ts)
    unit, tmpl = TMPLS[bisect.bisect(BREAKPOINTS, seconds_delta)]
    return tmpl.format(units=seconds_delta // unit)

除了用元組可以優(yōu)化過多的 if/else 分支外，有些情況下字典也能被用來做同樣的事情,。關(guān)鍵在于從現(xiàn)有代碼找到重復(fù)的邏輯與規(guī)律,，并多多嘗試。

2. 在更多地方使用動態(tài)解包

動態(tài)解包操作是指使用 * 或 ** 運(yùn)算符將可迭代對象“解開”的行為,，在 Python 2 時代,，這個操作只能被用在函數(shù)參數(shù)部分，并且對出現(xiàn)順序和數(shù)量都有非常嚴(yán)格的要求,，使用場景非常單一,。

不過，Python 3 尤其是 3.5 版本后,， * 和 ** 的使用場景被大大擴(kuò)充了,。舉個例子，在 Python 2 中,，如果我們需要合并兩個字典,，需要這么做：

def merge_dict(d1, d2):
    # 因為字典是可被修改的對象，為了避免修改原對象,，此處需要復(fù)制一個 d1 的淺拷貝
    result = d1.copy()
    result.update(d2)
    return result

user = merge_dict({'name': 'piglei'}, {'movies': ['Fight Club']})

但是在 Python 3.5 以后的版本,，你可以直接用 ** 運(yùn)算符來快速完成字典的合并操作：

除此之外，你還可以在普通賦值語句中使用 * 運(yùn)算符來動態(tài)的解包可迭代對象,。如果你想詳細(xì)了解相關(guān)內(nèi)容,，可以閱讀下面推薦的 PEP。

Hint：推進(jìn)動態(tài)解包場景擴(kuò)充的兩個 PEP：

• PEP 3132 -- Extended Iterable Unpacking | Python.org

• PEP 448 -- Additional Unpacking Generalizations | Python.org

3. 最好不用“獲取許可”,，也無需“要求原諒”

這個小標(biāo)題可能會稍微讓人有點(diǎn)懵,，讓我來簡短的解釋一下：“獲取許可”與“要求原諒”是兩種不同的編程風(fēng)格。如果用一個經(jīng)典的需求：“計算列表內(nèi)各個元素出現(xiàn)的次數(shù)” 來作為例子,，兩種不同風(fēng)格的代碼會是這樣：

# AF: Ask for Forgiveness
# 要做就做,，如果拋出異常了，再處理異常
def counter_af(l):
    result = {}
    for key in l:
        try:
            result[key] += 1
        except KeyError:
            result[key] = 1
    return result


# AP: Ask for Permission
# 做之前,，先問問能不能做,，可以做再做
def counter_ap(l):
    result = {}
    for key in l:
        if key in result:
            result[key] += 1
        else:
            result[key] = 1
    return result

整個 Python 社區(qū)對第一種 Ask for Forgiveness 的異常捕獲式編程風(fēng)格有著明顯的偏愛,。這其中有很多原因，首先,，在 Python 中拋出異常是一個很輕量的操作,。其次，第一種做法在性能上也要優(yōu)于第二種,，因為它不用在每次循環(huán)的時候都做一次額外的成員檢查,。

不過，示例里的兩段代碼在現(xiàn)實世界中都非常少見,。為什么,？因為如果你想統(tǒng)計次數(shù)的話，直接用 collections.defaultdict 就可以了：

這樣的代碼既不用“獲取許可”,，也無需“請求原諒”,。整個代碼的控制流變得更清晰自然了。所以,，如果可能的話,，請盡量想辦法省略掉那些非核心的異常捕獲邏輯。一些小提示：

• 操作字典成員時：使用 collections.defaultdict 類型

• 或者使用 dict[key]=dict.setdefault(key,0)+1 內(nèi)建函數(shù)

• 如果移除字典成員,，不關(guān)心是否存在：

• 調(diào)用 pop 函數(shù)時設(shè)置默認(rèn)值,，比如 dict.pop(key,None)

• 在字典獲取成員時指定默認(rèn)值： dict.get(key,default_value)

• 對列表進(jìn)行不存在的切片訪問不會拋出 IndexError 異常： ['foo'][100:200]

4. 使用 next() 函數(shù)

next() 是一個非常實用的內(nèi)建函數(shù)，它接收一個迭代器作為參數(shù),，然后返回該迭代器的下一個元素,。使用它配合生成器表達(dá)式，可以高效的實現(xiàn)“從列表中查找第一個滿足條件的成員”之類的需求,。

numbers = [3, 7, 8, 2, 21]
# 獲取并 **立即返回** 列表里的第一個偶數(shù)
print(next(i for i in numbers if i % 2 == 0))
# OUTPUT: 8

5. 使用有序字典來去重

字典和集合的結(jié)構(gòu)特點(diǎn)保證了它們的成員不會重復(fù),，所以它們經(jīng)常被用來去重,。但是,，使用它們倆去重后的結(jié)果會丟失原有列表的順序。這是由底層數(shù)據(jù)結(jié)構(gòu)“哈希表（Hash Table）”的特點(diǎn)決定的,。

如果既需要去重又必須保留順序怎么辦,？我們可以使用 collections.OrderedDict 模塊:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys(l).keys())
[10, 2, 3, 21]

Hint: 在 Python 3.6 中，默認(rèn)的字典類型修改了實現(xiàn)方式,，已經(jīng)變成有序的了,。并且在 Python 3.7 中，該功能已經(jīng)從 語言的實現(xiàn)細(xì)節(jié) 變成了為 可依賴的正式語言特性,。

但是我覺得讓整個 Python 社區(qū)習(xí)慣這一點(diǎn)還需要一些時間,，畢竟目前“字典是無序的”還是被印在無數(shù)本 Python 書上。所以,，我仍然建議在一切需要有序字典的地方使用 OrderedDict,。

常見誤區(qū)

1. 當(dāng)心那些已經(jīng)枯竭的迭代器

在文章前面,，我們提到了使用“懶惰”生成器的種種好處。但是,，所有事物都有它的兩面性,。生成器的最大的缺點(diǎn)之一就是：它會枯竭。當(dāng)你完整遍歷過它們后,，之后的重復(fù)遍歷就不能拿到任何新內(nèi)容了,。

而且不光是生成器表達(dá)式,，Python 3 里的 map,、filter 內(nèi)建函數(shù)也都有一樣的特點(diǎn)。忽視這個特點(diǎn)很容易導(dǎo)致代碼中出現(xiàn)一些難以察覺的 Bug,。

Instagram 就在項目從 Python 2 到 Python 3 的遷移過程中碰到了這個問題,。它們在 PyCon 2017 上分享了對付這個問題的故事。訪問文章 Instagram 在 PyCon 2017 的演講摘要,，搜索“迭代器”可以查看詳細(xì)內(nèi)容,。

2. 別在循環(huán)體內(nèi)修改被迭代對象

這是一個很多 Python 初學(xué)者會犯的錯誤。比如,，我們需要一個函數(shù)來刪掉列表里的所有偶數(shù)：

def remove_even(numbers):
    '''去掉列表里所有的偶數(shù)
    '''
    for i, number in enumerate(numbers):
        if number % 2 == 0:
            # 有問題的代碼
            del numbers[i]


numbers = [1, 2, 7, 4, 8, 11]
remove_even(numbers)
print(numbers)
# OUTPUT: [1, 7, 8, 11]

注意到結(jié)果里那個多出來的 “8” 了嗎,？當(dāng)你在遍歷一個列表的同時修改它，就會出現(xiàn)這樣的事情,。因為被迭代的對象 numbers 在循環(huán)過程中被修改了,。遍歷的下標(biāo)在不斷增長，而列表本身的長度同時又在不斷縮減,。這樣就會導(dǎo)致列表里的一些成員其實根本就沒有被遍歷到,。

所以對于這類操作，請使用一個新的空列表保存結(jié)果,，或者利用 yield 返回一個生成器,。而不是修改被迭代的列表或是字典對象本身。

總結(jié)

在這篇文章中,，我們首先從“容器類型”的定義出發(fā),，在底層和高層兩個層面探討了容器類型。之后遵循系列文章傳統(tǒng),，提供了一些編寫容器相關(guān)代碼時的技巧,。

讓我們最后再總結(jié)一下要點(diǎn)：

• 了解容器類型的底層實現(xiàn)，可以幫助你寫出性能更好的代碼

• 提煉需求里的抽象概念,，面向接口而非實現(xiàn)編程

• 多使用“懶惰”的對象,，少生成“迫切”的列表

• 使用元組和字典可以簡化分支代碼結(jié)構(gòu)

• 使用 next() 函數(shù)配合迭代器可以高效完成很多事情，但是也需要注意“枯竭”問題

• collections,、itertools 模塊里有非常多有用的工具,，快去看看吧,！

看完文章的你，有沒有什么想吐槽的,？請留言或者在 項目 Github Issues 告訴我吧,。

系列其他文章

• 所有文章索引 [https://github.com/piglei/one-python-craftsman]

• Python 工匠：善用變量改善代碼質(zhì)量

• Python 工匠：編寫條件分支代碼的技巧

• Python 工匠：使用數(shù)字與字符串的技巧

注解

1. Python 這門語言除了 CPython 外，還有許許多多的其他版本實現(xiàn),。如無特別說明,，本文以及 “Python 工匠” 系列里出現(xiàn)的所有 Python 都特指 Python 的 C 語言實現(xiàn) CPython

2. Python 里沒有類似其他編程語言里的“Interface 接口”類型，只有類似的“抽象類”概念,。為了表達(dá)方便,，后面的內(nèi)容均統(tǒng)一使用“接口”來替代“抽象類”。

3. 有沒有只實現(xiàn)了 Mapping 但又不是 MutableMapping 的類型,？試試 MappingProxyType({})

4. 有沒有只實現(xiàn)了 Set 但又不是 MutableSet 的類型,？試試 frozenset()