【python】defaultdictは使い方をミスると重くて遅い

　defaultdictはpythonで使えるとても便利なコレクション型です。

　しかし、使い方には注意が必要な場合があります。

　目次

defaultdictの概要

　これはご存じない方向けの章なので、「知ってるよ」という方は読み飛ばしても構いません。

　defaultdictは標準ライブラリのcollectionsモジュールに含まれるデータ型です。辞書に存在しないキーにアクセスしたとき、デフォルト値が設定されたキーを自動で作ってくれるのがメリットです。

　次のように使えます。

>>> dict()["hoge"] # 通常のdictは存在しないキーにアクセスすると例外を吐く
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'hoge'
>>> from collections import defaultdict
>>> d = defaultdict(int)
>>> d["hoge"] # defaultdictはこうできる
0
>>> d["fuga"] += 1 # こんなことも
>>> d["fuga"]
1

　とても便利そうですが、アクセスするだけでキーが生成されてしまうということは問題を引き起こすことがあります。

問題点

　こんなコードを実行してみます。

# coding: UTF-8

from collections import defaultdict

def main():
    d = defaultdict(str)

    d[0] = "hoge"
    d[10] = "fuga"
    d[100] = "piyo"

    lst = [d[i] for i in range(10000000)]
    print(len(d.keys()))

if __name__ == "__main__":
    main()

　タスクマネージャーなどでメモリ消費を監視しながら実行を見守ってください。けっこうなメモリが消費された後、10000000という数字が出てきます。

　line_profilerで確認してみます（mainの前に@profileデコレータを付ける必要があります）。

$ kernprof -l -v test_defaultdict.py 
10000000
Wrote profile results to test_defaultdict.py.lprof
Timer unit: 1e-06 s

Total time: 5.97851 s
File: test_defaultdict.py
Function: main at line 5

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     5                                           @profile
     6                                           def main():
     7         1          8.0      8.0      0.0      d = defaultdict(str)
     8                                           
     9         1          2.0      2.0      0.0      d[0] = "hoge"
    10         1          1.0      1.0      0.0      d[10] = "fuga"
    11         1          1.0      1.0      0.0      d[100] = "piyo"
    12                                           
    13         1    5978354.0 5978354.0    100.0      lst = [d[i] for i in range(10000000)]
    14         1        141.0    141.0      0.0      print(len(d.keys()))

　やはり恐ろしいほど時間がかかっています。

　この処理時間の大半は、キーの生成に費やされているはずです。メモリ消費が膨れ上がるのも、default値を持つキーを大量に作ったからdictオブジェクトが膨れ上がった、と説明できます。

　つまり、こういう処理を書くとリーズナブルではないと言えます。

解決策

　defaultdictと言えども、単に初期値を期待して参照するようなときはキーのあるなしを判定するべきです。

# coding: UTF-8

from collections import defaultdict

def main():
    d = defaultdict(str)

    d[0] = "hoge"
    d[10] = "fuga"
    d[100] = "piyo"

    lst = [d[i] if i in d else "" for i in range(10000000)]
    print(len(d.keys()))

if __name__ == "__main__":
    main()

　今度は心なしか少ない実行時間で3と表示され、メモリ消費も膨れ上がらないはずです。line_profilerで見ても、

$ kernprof -l -v test_defaultdict.py 
3
Wrote profile results to test_defaultdict.py.lprof
Timer unit: 1e-06 s

Total time: 2.5628 s
File: test_defaultdict.py
Function: main at line 5

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     5                                           @profile
     6                                           def main():
     7         1          5.0      5.0      0.0      d = defaultdict(str)
     8                                           
     9         1          1.0      1.0      0.0      d[0] = "hoge"
    10         1          1.0      1.0      0.0      d[10] = "fuga"
    11         1          1.0      1.0      0.0      d[100] = "piyo"
    12                                           
    13         1    2562684.0 2562684.0    100.0      lst = [d[i] if i in d else "" for i in range(10000000)]
    14         1        108.0    108.0      0.0      print(len(d.keys()))

　このように処理時間が半分以下になりました。

まとめ

• defaultdictは単にデフォルト値を期待してアクセスしただけの場合でも、hashにキーと値を追加してしまう。

• 通常のdictと同様、キーの存在を判定して処理を分岐させた方がリーズナブルである。