Python的群集與ABC

想要認識一門語言，不單只是就語法部份，認識的設計與風格，也是極為重要的一部份。

在標準程式庫為數眾多的API中，從群集API的資料結構分類與階層作為開始，是個不錯的方式，對於Python這類將常用資料結構作為內建型態的語言，更是如此。

從Python內建型態談起

就語言來說，常用的資料結構，都會有一套標準實作。

有些語言將常用資料結構內建為語法的一部份，像是Python的list、set、tuple、dict等，都可使用實字方式撰寫，這讓程式變得簡潔，也能應付大多數處理資料的需求；有些語言將這些實作以獨立的API實作，像是Java的Collection、Map API等，讓這類資料結構用來與程式語法涇渭分明，雖然語法囉嗦，然而，開發者較易（或說是強制要）掌握型態與實作品的特性。

對於熟悉Java的我而言，在使用Python語言，享用過這類資料結構作為直譯器內建型態的好處之後，不免開始有了一些矇朧的疑問，這些內建型態的實作特性呢？我很熟悉Java中Collection、Map API的設計架構，那麼Python中list、set、tuple、dict的分類與階層呢？

若不能掌握API設計架構，不但難以掌握各資料結構實作品的特性，也容易淪為死記API的窘境，更容易撰寫出沒有彈性的程式。

由於熟悉Java，一開始不免想要將Java中的介面與實作品，逐一在Python中找出對照物，不過，不久就發現方向似乎有點錯誤，畢竟兩門語言的設計哲學不同，更何況是API的設計了，最大的差別之一是，Python是動態定型，而Java是靜態定型語言，因此Python沒有Java中Collection、Map那樣的介面階層，而是直接思考行為，將相關資料結構分為了Sequences、Set與Mapping三種型態。

對於Sequence，它們都具有索引取值、切片等一些共同的行為，Python接著將Sequence進一步地區分了Immutable與Mutable兩種，str、tuple、bytes屬於Immutable，而list、bytearray屬於Mutable，並具有Immutable幾乎全部的行為，以及切片操作指定、append、remove等操作，然而，Immutable具備、但Mutable不一定會實作的行為是hash操作，因此Immutable的型態就可以作為dict的鍵，或者是set、frozenset的元素。

collections模組

所謂Sequence型態，並不是指它們真的有繼承一個Sequence類別，而是指具備Sequence的行為，具體而言，就是像實作了len、index這類的操作罷了，這讓設計函式時更有彈性；進一步地，我開始想到‥set、dict的行為，分別看來就像是Java中的HashSet、HashMap，都是無序的，那麼有沒有TreeSet、TreeMap呢？對於這類需求，Python提供了collections模組來滿足。

在collections模組中，可基於dict建立一個OrderedDict，它看來像是Java中的TreeMap，不過是以元素插入順序來定序，這表示，若想在取得鍵值對時，能依自訂順序來取出，就必須先在一個Sequence中自行對鍵值排序，再用排序後的結果建立OrderedDict。

在Java的Collection架構中，有個Queue介面與子介面Deque，而在Python中，list本身可實現Queue甚至是Deque，不過要注意到效能問題——當從list前端取出或新增元素時，時間複雜度會是O(n)，如果元素數量多的話，最好是改用collections模組中的deque，它的popleft、appendleft時間複雜度會是O(1)，當然，作為雙向佇列的實現，deque也提供了rotate之類的方法。

在Python中，tuple的地位總是比較尷尬，很多層面它跟list類似，只不過它是Immutable，佔用比較少的資源；然而，如果看過Haskell的Tuple，就會知道Tuple的元素型態，相當於臨時組成了未命名的新型態，其實在Python的collections模組中，也有個類似的namedtuple函式，可讓既有的tuple跟Haskell中的Tuple類似，充當臨時的資料結構。例如：

Point = namedtuple('Point', ['x', 'y'])
p = Point(11, 22)
print(p.x + p.y)  # 顯示 33

namedtuple是個工廠函式，傳回的實際上是動態建立的tuple子類別，因此具有tuple的行為，然而具有指定的型態名稱與欄位名稱，也可以使用dot來存取欄位，這讓它的實例就像是個Immutable物件，比一般物件節省資源，也可以充當dict來使用。

collections.abc模組

當然，collections中，還有像是Counter類別、defaultdict函式等可以使用，不過，終究還是沒有發現像是Java中LinkedList、TreeSet這類的東西。如果需要這類東西，必須要自行實作。例如，若需要list的全部功能，而且，在某些場合必須被判斷為list實例（像是使用isinstance()判斷，例如OrderedDict就是dict的子類別），那麼可以繼承list；如果只是要包裹一個list，並讓包裹器行為上像個list，可以繼承UserList。

然而，如果只是要實作群集的行為，但不需要是群集中某個類別的子類別時，可以繼承collections.abc模組中的相關類別——abc代表著abstract base classes，也就是這些類別是作為抽象基礎類別，它們本身已經實作了一些行為。不過，還有些必要的抽象方法，必須開發者在繼承之後自行定義，如果開發者忘了定義，建立實例時會引發TypeError，並告知忘了實作哪些抽象方法，這開發者免於記憶或查詢有哪些方法必須實作。

而且，一旦開發者定義了必要的抽象方法，基於這些抽象方法的其他方法實作（Mixin Methods），就能夠運作了，這會比完全自定義一個群集類別來得方便許多且不容易出錯，比方說，在Python的collections.abc官方說明文件中，就有個〈OrderedSet recipe〉的文件鏈結，其中的OrderedSet，就是基於collections.MutableSet而實作。

collections.abc模組中，還有Iterable、Iterator、Hashable等抽象基礎類別，想要清楚地認識Python中的群集特性與行為，認識collections.abc模組是個相當好的管道，規範抽象基礎類別的PEP 3119規格書，也非常值得參考。

若想再更進一步，我們可以針對collections、collections.abc中，研究相關函式或類別的程式碼實現，這樣將更能夠掌握相關特性的實現細節。

清楚而自信地使用資料結構

Pascal之父Niklaus E. Writh曾經說過：「演算法加資料結構就等於程式」，因此是否瞭解常用的、特性與相關的效用函式，對程式的設計影響鉅大。這在我先前專欄〈開發者應認識的資料型態及效用函式〉、以及〈善用程式庫中的資料結構特性〉，也曾經探討過。

因此，面對像Python這類將資料結構內建為語法一部份的語言，雖然一開始用起來順手且具有高產能，然而，最好還是循著對資料結構特性的基本認識，逐一探討這些便捷語法背後的設計與實現，甚至必要時，可基於標準程式庫提供的基礎，試著自行實現相關資料結構。

這麼一來，不但能對相關語法或程式庫能有更深入的瞭解，且進一步地認識語言及API的相關設計哲學，在需要這些資料結構時，也才能清楚而有自信地加以運用。