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]})