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

在標準程式庫為數眾多的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的相關設計哲學,在需要這些資料結構時,也才能清楚而有自信地加以運用。

作者簡介


Advertisement

更多 iThome相關內容