python collection雜談之四

在講第五個數據結構OrderedDict之前，我們再來補充點多一點基礎知識吧！python的高可讀性和易用性讓其可以用來作為快速開發的高階語言，但相對的代價就是較低的程式效能，在python中，萬物皆是object，甚至是number和string也是，光是要處理其中的初始化、記憶體管理或是動態型別處理，就難免會花上一些時間。

但因為在python的內部運作之中，會很常運用到dict這個資料結構(比如說python在運行時，會有一個dict來維護變數(reference)與其指向的實際值(object)的key-value pair，當要操作這個變數時，必須即時找到這個變數的指向對象)，因此python對於dict的搜索效能是相對標準較高的。

如果拿C++的stl library的map來比較，會發現python的dict是更有效率的，C++的map是用紅黑樹(RB-tree)來維護，雖其操作複雜，但其確保了在最差狀況下還能有不錯的搜索效率O(log n)，因其非常良好的管控了樹的高度，讓每個分支間的高度儘量保持一樣，但搜索效率就是O(log n)，而python則是維持了一個大範圍的hash table，對於每一個key，理想上會維持一個1對1的hash function mapping，也就是每個不同的key，用hash function都會計算出不一樣的value，並將其對應在hash table上的不同位置，因此理想上搜索效率會維持在O(1)，至於若發生了衝突(collision)，也就是不同的key，經過了hash function計算卻得到了相同的值，那就是比較複雜的議題了，在這裡不會詳細探討，但若遇到這種狀況，python會試著讓其中一個key再通過第二個hash function，也就是替這個key找一個新的value來解決問題。

5. OrderedDict:

OrderedDict是dict的一個子類別，他具有一個很實用的特性就是他會對key做排序，而這個排序的依據在於這個key被插入的先後順序，而如果更新了某個key的value值並不會影響他在OrderedDict的排序位置，除非這個key被刪除並被重新插入，才會從原始的排序位置變成最末位，因為其變成最新插入的一個key：

In python3 shell:
>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> d['first']=5
>>> d['second']=4
>>> d['third']=8
>>> d['fourth']=7
>>> d
OrderedDict([('first', 5), ('second', 4), ('third', 8), ('fourth', 7)])
>>> d['first']=10 # first 位置不會變動
>>> d
OrderedDict([('first', 10), ('second', 4), ('third', 8), ('fourth', 7)])
>>> d.pop('third')
8
>>> d
OrderedDict([('first', 10), ('second', 4), ('fourth', 7)])
>>> d['third']=8 # 刪除再重新插入才會改變位置
>>> d
OrderedDict([('first', 10), ('second', 4), ('fourth', 7), ('third', 8)])
>>> for k,v in d.items(): # 對於key順序的遍歷
...     print(k,v) 
... 
first 10
second 4
fourth 7
third 8
>>>

OrderedDict最重要的用處在於，我們可以實現一個能夠排序的字典，雖然預設是以插入順序來排序，但我們可以與sorted()結合使用，讓這個OrderedDict可以照我們所希望的依據來排序：

In python3 shell:
>>> from collections import OrderedDict
>>> OrderedDict([('1', 4), ('2', 3), ('3', 2), ('4', 1)]) # OrderedDict會依賴著tuple構成的list的順序來排序，我們可以藉此特性來排序
OrderedDict([('1', 4), ('2', 3), ('3', 2), ('4', 1)])
>>> d = {'1':4,'2':3,'3':5,'4':2}
>>> d
{'3': 5, '1': 4, '2': 3, '4': 2}
>>> sorted(d.items(),key=lambda x:x[0]) # 以key值排序
[('1', 4), ('2', 3), ('3', 5), ('4', 2)]
>>> sorted(d.items(),key=lambda x:x[1]) # 以value值排序
[('4', 2), ('2', 3), ('1', 4), ('3', 5)]
>>> OrderedDict(sorted(d.items(),key=lambda x:x[0]))
OrderedDict([('1', 4), ('2', 3), ('3', 5), ('4', 2)])
>>> OrderedDict(sorted(d.items(),key=lambda x:x[1]))
OrderedDict([('4', 2), ('2', 3), ('1', 4), ('3', 5)])

OrderedDict要說的東西不多，只要掌握了其排序的方式，就能夠好好發揮其效用。

6. ChainMap

顧名思義，ChainMap就是把多個map，也就是dict鏈在一起，在功能上可以理解成，把所有的dict合併成一個大的dict，但在比較底層的實現中，這些dict還是維持著自己原本的樣子，ChainMap的作法就像是把他們存在一個list裡。

他方便的地方在於，現在我們有很多的dicts，但是我們有一些功能希望以"把這些dicts視為一個大的dict"的方式來實現，但又不想花費時間重造一個dict然後把我們這些已有的dicts全部update進去，這樣不只花費開發人員的時間，也浪費程式執行的時間，所以ChainMap的出現就是來解決這類的問題。

比如說，我們有3個dict: a_dict, b_dict, c_dict，我想要在這些dicts中查詢某一個key的值，查找的順序為，先找a，找不到再找b，如果也沒有才找c，如果不用ChainMap，最土法煉鋼的型式為：

example.py:

a_dict = {'a1':1, 'a2':2, 'c1':3} # a_dict裏面的key:'c1',會和c_dict裡重複
b_dict = {'b1':4, 'b2':5, 'b3':6}
c_dict = {'c1':7, 'c2':8, 'c3':9}

def find_from_dicts(key,dicts):
    for d in dicts:
        if key in d:
            return d[key]

    raise KeyError

dicts = (a_dict,b_dict,c_dict)

print(find_from_dicts('a2',dicts)) # 2
print(find_from_dicts('c1',dicts)) # 3 而不是 7
print(find_from_dicts('c2',dicts)) # 8
print(find_from_dicts('b2',dicts)) # 5
print(find_from_dicts('b4',dicts)) # KeyError

如果使用了ChainMap，同樣功能程式碼會精簡許多：

example2.py:

from collections import ChainMap

a_dict = {'a1':1, 'a2':2, 'c1':3} # a_dict裏面的key:'c1',會和c_dict裡重複
b_dict = {'b1':4, 'b2':5, 'b3':6}
c_dict = {'c1':7, 'c2':8, 'c3':9}

dicts = ChainMap(a_dict,b_dict,c_dict)

print(dicts['a2']) # 2
print(dicts['c1']) # 3 而不是 7
print(dicts['c2']) # 8
print(dicts['b2']) # 5
print(dicts['b4']) # KeyError

原本是想說更多的，但因為之前打這篇草稿到了半夜，覺得好累，然後今天還是懶的補XD，忙著後面幾篇文章的偷跑，還是先這樣吧，collection雜談到今天結束，剩下的功能就請有興趣的讀者們自行查閱囉！