接下來的三篇都是關於Python的數據結構，本篇主要是Python中的各序列類型

1. 內置序列類型概覽

Python標準庫用C實現了豐富的序列類型，可分為兩大類：

• 容器序列：list，tuple和collections.deque等這些序列能存放不同類型的數據。

• 扁平序列：str，bytes，bytearray，memoryview和array.array等，這些序列只能容納一種類型。

容器序列存放的是它們所包含的任意類型的對象的引用，而扁平序列存放的是值而不是引用。即，扁平序列其實是一段連續的內存空間，更加緊湊。

序列類型還可以按能否被修改來分來：

• 可變序列（MutableSequence）：list，bytearray，array.array，collections.deque和memoryview；

• 不可變序列（Sequence）：tuple，str和bytes。

以下是這兩大類的繼承關係：

雖然Python中內置的序列類型並不是直接從Sequence和MutableSequence這兩個抽象基類繼承而來，但瞭解這些基類可以總結出那些完整的序列類型包含了哪些功能，以及將上述兩種分類方式融會貫通。

下面我們從最常用的列表（list）開始。

2. 列表推導和生成器表達式

列表推導（list comprehension，簡稱listcomps）是構建列表的快捷方式，而生成器表達式（generator expression, 簡稱genexps）則可以用來創建其它任何類型的序列。

有時候，比起用for循環，列表推導可能會更簡單可讀。通常的原則是，只用列表推導來創建新的列表，並且儘量保持簡短。如果列表推導的代碼超過了兩行，應該考慮是不是得用for循環重寫，不過這個度得自己把握。（句法提示：Python會忽略[],{},()中的換行，所以可以省略不太好看的換行符 \)

注意：在Python3中，列表推導、生成器表達式，以及和它們很相似的集合（set）推導和字典（dict）推導都有了自己的局部作用域，不會影響外部的同名變量（Python2中則可能會影響），如下：

2.1 列表推導同filter和map比較

列表推導可以過濾或加工一個序列或其他可迭代類型中的元素，然後生成一個新列表。而Python內置的filter和map函數組合起來也能達到這一效果（一般需要藉助lambda表達式），但可讀性卻比不上列表推導，比如下面的代碼：

原本以為map/filter組合起來會比列表推導快一些，但有測試證明該結論不一定成立。對於map, filter的詳細介紹將放在後面的文章中。

2.2 笛卡爾積

簡單說就是簡化嵌套for循環，例子如下：

列表推導的作用只有一個：生成列表。如果想生成其他類型的序列，則需要使用生成器表達式。

2.3 生成器表達式

雖然也可以用列表推導式來初始化元組，數組或其他序列類型，但生成器表達式是更好的選擇，因為生成器表達式背後

生成器表達式語法跟列表推導差不多，只是把方括號換成了圓括號而已，如下：

①如果生成器表達式是一個函數調用過程中的唯一參數，則可不加括號將其圍起來；

②array的構造方法需要兩個參數，因此括號是必需的。

下面用生成器表達式改寫上面的笛卡爾積代碼：

生成器表達式逐個生成元素，不會一次性生成一個含有6個元素的列表。關於生成器表達式的工作原理將在後面的文章中介紹。

3. 元組

元組除了用作不可變的列表，它還可以用於沒有字段名的記錄，比如座標，身份信息等，這裡不再舉例。

3.1 元祖拆包

此概念之前涉及過，這裡將其總結一下：

3.2 嵌套元組拆包

接受表達式的元組可以是嵌套式的，例如(a, b, (c, d))，只要這個接受元組的嵌套結構符合表達式本身的嵌套結構，以下用嵌套元組來獲取經緯度：

3.3 具名元組（命名元組）

上篇中有所涉及。collections.namedtuple是一個工廠函數，它可以創建一個帶字段名的元組和一個有名字的類——這個帶名字的類對調試程序有很大幫助。

namedtuple構造的類的實例所消耗的內存跟元組是一樣的，因為字段名都存在對於的類中。這個實例跟普通對象實例比起來要小一些，因為Python不會用__dict__來存放這些實例的屬性。

• 第3行：創建一個具名元組需要兩個參數，一個是類名，一個是類的各字段名。後者可以是由數個字符串組成的可迭代對象，或者是由空格分隔的字符串；

• 第6,7行：可通過字段名或位置來獲取一個字段的信息；

• 第9行：_fields屬性是一個包含這個類所有字段名的元組；

• 第12行：_make()通過接受一個可迭代對象來生成這個類的一個實例，它的作用跟City(*delhi_data)是一樣的。

• 第13行：_asdict()把具名元組以collections.OrderedDict的形式返回。

• 注意第10，27行！

3.4 作為不可變列表的元組

除了跟增減元素相關的方法外，元組支持列表的其他所有方法。還有一個例外就是元組沒有__reversed__方法，但這方法只是個優化，reversed(my_tuple)這個方法在沒有__reversed__的情況下也是合法的。

4. 切片

切片在Python基礎中介紹了一些遍歷的基本操作，這裡補充一些高級的用法。

4.1 切片賦值

4.2 有名字的切片

Python中有一個切片類（slice），可以用它創建切片對象：

4.3 多維切片和省略

[ ]運算符中還可以使用以逗號分開的多個索引或者切片，比如第三方庫Numpy中就用到了這個特性，二維的numpy.ndarray就可以用a[i, j]來獲取值（這裡的語法和C#一樣，相當於C/C++中的a[i][j]），或者a[m:n, k:l]來獲得二維切片。要正確處理這種語法，對象的特殊方法__getitem__和__setitem__需要以元組的形式來接收a[i, j]中的索引，即，如果要得到a[i, j]，Python會調用a.__getitem__((i, j))。關於多維切片的例子在本文後面演示。

省略（ellipsis）的寫法是三個英語句點（…)，而不是Unicode碼位U+2026表示的半個省略號（和前面三個句點幾乎一模一樣）。省略在Python解釋器眼裡是一個符號，而實際上它是Elllipsis對象的別名，而Ellipsis對象又是ellipsis類的單一實例（ellipsis是類名，全小寫，而它的內置實例寫作Ellipsis。這跟bool是小寫，而它的兩個實例True和False是大寫一個道理）。它可以當做切片規範的一部分，也可用在函數的參數列表中，如f(a,…,z)，或a[i: …]。在Numpy中，…用作多維數組切片的快捷方式，即x[i, …]就是x[i, :, :, :]的縮寫。

筆者暫時還沒發現Python標準庫中有任何Ellipsis或者多維索引的用法。這些句法上的特性主要是為了支持用戶自定義類或者擴展，Numpy就是一個例子。

5. 對序列使用+和*

通常+號兩側的序列由相同類型的數據所構成（當然不同類型的也可以相加），返回一個新序列。如果想把一個序列複製幾份再拼接，剛快捷的做法是乘一個整數：

注意：這裡有深淺複製的問題，如果在A * n這個語句中，序列A中的元素b是對其他可變對象的引用的話，則新序列中A2中的n個元素b1……bn都指向同一個位置，即對b1到bn中任意一個賦值，都會影響其他元素。下面以一個創建多維數組的例子來說明這個情況（字符串是不可變對象，而列表是可變對象！）：

正確的寫法：

錯誤的寫法：

6. 序列的增量賦值

增量賦值運算符+=和*=的表現取決於它們的第一個操作對象，以+=為例。+=背後的特殊方法是__iadd__(用於“就地加法”)，如果一個類沒有實現該方法，則會調用__add__。例如 a += b，如果a實現了__iadd__，則直接調用該方法，修改的是a，不會產生新對象，而如果沒有實現該方法，則會調用__add__，執行的運算實際是 a = a + b，該運算會生成一個新變量，存儲a + b的結果，然後再把該新變量賦值給a。

總體來說，可變序列一般都實現了__iadd__，而不可變序列根本就不支持這個操作。對不可變序列執行重複拼接操作的話，效率很低，因為每次都會生成新對象，而解釋器需要把原來對象中的元素先複製到新對象中，然後再追加新元素。但str是個例外，因為對字符串做+=操作是在太普遍了，於是CPython對它做了優化：str初始化時，程序會為它預留額外的可擴展空間，因此做增量操作時不會涉及複製原有字符串到新位置的操作。

一個關於+=的謎題

對於以下操作，大家猜想會得到什麼樣的結果：

它的結果是報錯，但t依然被改變了：

如果我們看Python表達式 s[a] += b的字節碼，便不難理解上述結果：

從上述結果可以看出：

• 第6行：將s[a]的值存入TOS(Top Of Stack，棧頂)；

• 第8行：計算TOS += b， 這一步能夠完成，因為TOS指向一個可變對象；

• 第14行：s[a] = TOS，報錯，因為s是個元組，不可變。

從上述操作可以得到3個教訓：

• 不要把可變對象放在元組中；

• 增量賦值不是一個原子操作。從上面的結果可以看出，它雖拋出了異常，但仍完成了操作；

• 查看Python字節碼並不難，而且它對我們瞭解代碼背後的運行機制很有幫助。

7. 用bisect來管理已排序的序列

bisect模塊包含兩個主要函數，bisect和insort，這兩個函數都利用二分查找算法在有序列表中查找或插入元素。

bisect用於查找元素的位置：biisect(haystack, needle)。它返回needle在haystack中的位置index，如果要插入元素，可以在找到位置後，再調用haystack.insert(index, new_ele)，但也可以用bisect模塊中的insert直接插入，並且該方法速度更快。

Python的高產貢獻者Raymond Hettinger寫了一個排序集合模塊sortedcollection，該模塊集成了bisect功能，且比獨立的bisect更易用。

bisect需要注意兩點：

• 兩個可選參數lo和hi：lo默認值是0，hi默認值是序列的長度，即len()作用域該序列的返回值。

• bisect函數其實是bisect_right函數的別名，它返回的位置是與needle相等的元素的後一個位置，而它的兄弟函數bisect_left則返回的是與needle相等的元素的位置。

相應的，模塊中insort也有兩個版本，insort是insort_right的別名，它也有兩個可選參數lo和hi，insort_left的背後調用的就是bisect_left。

8. 當列表不是首選時

當我們有特定的數據集時，list並不一定是首選，比如存放1000萬個浮點數，數組（array）的效率就要高很多，因為數組的背後並不是float對象，而是數字的機器翻譯，也就是字節表述。這點和C語言中的數組一樣。再比如，如果要頻繁對序列做先進先出的操作，deque（雙端隊列）的速度應該會更快。

8.1 數組

如果需要一個只含數字的列表，array.array會比list更高效，它支持所有跟可變列表有關的操作，包括.pop，.insert，.extend等。另外數組還支持從文件讀取和存入文件的更快的方法，比如.frombytes和.tofile。

數組跟C語言數組一樣精簡，創建一個數組需要指定一個類型碼，這個類型碼用來表示在底層的C語言應該存放怎樣的數據類型，以下是array.array的操作例子：

有人做過實驗，用array.fromfile從一個二進制文件讀出1000萬個雙精度浮點數只需要0.1秒（筆者電腦有點年代了，達不到這個速度），速度是從文本文件裡讀取的60倍，因為後者會使用內置的float方法把每一行文字轉換成浮點數。另外，array.tofile寫入二進制文件也比寫入文本文件快7倍。另外，這1000萬個數的bin文件只佔8千萬字節，如果是文本文件的話，需要181515739字節。

另一個快速序列化數字類型的方法是使用pickle模塊，pickle.dump處理浮點數組的速度幾乎和array.tofile一樣快，而且pickle可以處理幾乎所有的內置數字類型

8.2 內存視圖memoryview

memoryview是個內置類，它讓用戶在不復制內存的情況下操作同一個數組的不同切片。memoryview的概念受到了Numpy的啟發。

內存視圖其實是泛化和去數學化的Numpy數組。它讓你在不需要複製內容的前提下，在數據結構之間共享內存。其中數據結構可以是任何形式，比如PIL圖片、SQLite數據庫和Numpy數組等待。這個功能在處理大型數據集合的時候非常重要。

memoryview.cast的概念跟數組模型類似，能用不同的方式讀取同一塊內存數據，而且內存字節不會隨意移動。這有點類似於C語言的類型轉換。memoryview.cast會把同一塊內存裡的內容打包成一個全新的memoryview對象返回。

下面這個例子精確地修改一個數組的某個字節：

8.3 NumPy和SciPy

拼接這NumPy和SciPy提供的高階數組和矩陣操作，Python稱為科學計算應用的主流語言。NumPy實現了多維同質數組（homogeneous array）和矩陣，這些數據結構不但能處理數字，還能存放其他由用戶定義的記錄。SciPy是基於NumPy的另一個庫，他提供了很多跟科學計算有關的算法，專為線性代數、數值積分和統計學而設計。SciPy的高校和可靠性歸功於背後的C和Fortran代碼，而這些跟計算有關的部分都源自於Netlib。SciPy把基於C和Fortran的工業級數學計算功能用交互式且高度抽象的Python包裝起來。

以下是一些NumPy二維數組的基本操作：

NumPy也可讀取、寫入文件：

這兩個庫都異常強大，它們也是一些其他庫的基礎，比如Pandas和Blaze數據分析庫。

8.4 雙向隊列和其他形式的隊列

利用.append和.pop方法，可以將列表（list）變成棧和隊列。但刪除列表的第一個元素或在第一個元素前插入元素之類的操作會很耗時，因為會移動數據。如果經常要在列表兩端操作數據，推薦使用collections.deque類（雙向隊列）。它是一個線程安全、可快速從兩端添加刪除元素的數據類型。下面是它的操作示範：

該數據結構還有許多其他操作，append和popleft是原子操作，可在多線程中安全地使用，不用擔心資源鎖的問題。

8.5 Python標準庫中的隊列

• queue：提供了同步（線程安全）類Queue，LifoQueue和PriorityQueue，不同的線程可以利用這些數據類型來交換信息。這三個類在隊列滿的時候不會丟掉舊元素，而是被鎖住，直到某線程移除了某個元素。這一特性讓這些類很適合用來控制活躍線程的數量。

• multiprocessing：實現了自己的Queue，和queue.Queue類似，設計給進程間通信用的。同時還有一個專門的multiprocessing.JoinableQueue類，該類讓任務管理變得方便。

• asyncio：從Python3.4新增的包，包含Queue，LifoQueue，PriorityQueue和JoinableQueue，這些類受queue和multiprocessing模塊的影響，但是為異步編程裡的任務管理提供了專門的便利。

• heapq：和上述三個模塊不同，它沒有隊列類，而是提供了heappush和heappop方法，讓用戶可以把可變序列當作堆隊列或者優先隊列來使用。

9. 補充

• Python入門教材往往會強調列表可以容納不同類型的元素，但實際上這樣做並沒有什麼特別的好處。之所以用列表來存放東西，是期待在稍後使用它的時候，其中的元素能有一些共有的特性。Python3中，如果列表裡的元素不能比較大小，則是不能對列表進行排序的。元組則恰恰相反，它經常用來存放不同類型的元素，這也符合它的本質，元組就是用作存放彼此之間沒有關係的數據的記錄。

• list.sort，sorted，max和min函數的key參數是個很棒的設計，相比於其他語言中雙參數比較函數，這裡的參數key只需提供一個單參數函數來提取或計算一個值作為比較大小的標準。說它更高效，是因為在每個元素上，key函數只被調用一次。誠然，在排序的時候，Python總會比較兩個鍵（key），但那一階段的計算發生在C語言那一層，這樣會比調用用戶自定義的Python比較函數更快。key參數也能讓你對一個混有數字字符和數值的列表進行排序，只需決定到底是將字符看做數值（數值排序），還是將數值看成字符（ASCII排序），即key到底是等於int還是等於str。

閱讀更多 VPointer701 的文章

關鍵字: C語言 數據結構 序列