python3 的 defaultdict

python3中的dict在對不存在的鍵進行操作時，可能會産生KeyError。例如

In [15]: d = {}

In [16]: d['x'].append(1)
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-16-08933ca8d2fa> in <module>
----> 1 d['x'].append(1)

KeyError: 'x'

In [17]: x = d['x']
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-17-f89310486160> in <module>
----> 1 x = d['x']

KeyError: 'x'
           

如果我們要把每個鍵的值設定為清單，然後進行插入和右值操作時，需要這樣子做：

In [18]: d['x'] = []

In [19]: d['x'].append(1)

In [20]: x = d['x']

In [21]: d
Out[21]: {'x': [1]}
           

這樣子操作比較繁瑣。為了減少程式設計複雜度，我們可以使用collections包中的defaultdict類。defaultdict類是dict類的子類，繼承了dict類的方法。defaultdict會将原本不存在的鍵，賦予預設的初始值，比如空清單。上面那些操作，我們可以這樣子做：

In [1]: from collections import defaultdict
           

In [22]: d2 = defaultdict(list)

In [23]: d2['x'].append(1)

In [24]: d2['x'].append(2)

In [25]: x2 = d2['x']

In [26]: d2
Out[26]: defaultdict(list, {'x': [1, 2]})

In [27]: x2
Out[27]: [1, 2]

In [28]: d2['y']
Out[28]: []
           

defaultdict類的第一個參數是預設的鍵值初始化函數，必須是可以調用函數或者類名，預設是None。

有了defaultdict類，我們就省去了給鍵賦初始值的步驟了。

我們可以使用defaultdict來做表示圖的鄰接表。

In [38]: adjacent_list = defaultdict(list)

In [39]: graph = [[0,1], [0,2], [0,3], [0, 4], [1, 0], [1, 2], [2, 4], [3, 1], [3, 2], [4, 0], [4, 1], [4, 2]]

In [40]: for link in graph:
    ...:     adjacent_list[link[0]].append(link[1])
    ...:

In [41]: adjacent_list
Out[41]:
defaultdict(list,
            {0: [1, 2, 3, 4], 1: [0, 2], 2: [4], 3: [1, 2], 4: [0, 1, 2]})
           

dict的方法在defaultdict上可以正常使用。比如update方法：

In [44]: adjacent_list.update(a=[0,1,4], b=[1,2,4])

In [45]: adjacent_list
Out[45]:
defaultdict(list,
            {0: [1, 2, 3, 4],
             1: [0, 2],
             2: [4],
             3: [1, 2],
             4: [0, 1, 2],
             'a': [0, 1, 4],
             'b': [1, 2, 4]})
           

比如copy方法：

In [46]: adjlist2 = adjacent_list.copy()

In [47]: id(adjlist2) == id(adjacent_list)
Out[47]: False

In [48]: adjlist2
Out[48]:
defaultdict(list,
            {0: [1, 2, 3, 4],
             1: [0, 2],
             2: [4],
             3: [1, 2],
             4: [0, 1, 2],
             'a': [0, 1, 4],
             'b': [1, 2, 4]})