今朝の解析で, 二次元配列の更新操作がボトルネックということが分かりました. そこで, 二次元配列としてnumpyの二次元配列を利用して, 行や列ごとのコピーなどをnumpyに任せてしまい, 要素ごとに逐次的に行うより性能を良くするという方針で改善を行いました.
図について説明です.
- Pure Python: numpyを使っていない.
- 1: 二次元配列としてnumpyを使っただけ. 配列操作は要素ごとに行う.
- 2: ボトルネックとなっていたcopyI,copyJ(行/列ごとのコピー)をnumpyにオフロード.
- 3: 二次元配列上の範囲に対する代入操作もnumpyにオフロード.
特記することは以下です.
- (1)は, numpyを使ってないバージョンより性能が悪くなっています. numpyをただ利用するだけでは性能はむしろ落ちるということでしょう.
- (2)の時点で, 顕著な改善がなされています.
- (3)も, そもそもボトルネックでないところを更に改善しているため, (1)に比べて大きな改善はありません.
改めてcProfileをかけてみましょう.
以前のプロファイル (Pure Python相当):
1
2
3
4
5
| ncalls tottime percall cumtime percall filename:lineno(function)
36140445 4.013 0.000 4.013 0.000 heiankyoview.py:113(set)
36265385 3.795 0.000 3.795 0.000 heiankyoview.py:115(get)
47086 5.540 0.000 9.087 0.000 heiankyoview.py:133(copyI)
64503 6.287 0.000 10.350 0.000 heiankyoview.py:136(copyJ)
|
今回のプロファイル (3):
1
2
3
4
5
6
7
8
9
| ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 heiankyoview.py:115(set)
270529 0.094 0.000 0.094 0.000 heiankyoview.py:117(get)
38180 0.054 0.000 0.054 0.000 heiankyoview.py:131(copyI)
59139 0.109 0.000 0.109 0.000 heiankyoview.py:135(copyJ)
270529 0.168 0.000 0.306 0.000 heiankyoview.py:234(get)
520489 0.590 0.000 0.908 0.000 heiankyoview.py:671(addNode)
1 0.689 0.689 3.550 3.550 heiankyoview.py:676(pack)
1040976 0.242 0.000 0.242 0.000 heiankyoview.py:100(translate)
|
以前のボトルネックは解消されています. 処理時間は様々なところに散らばってしまい, ボトルネックと呼べる場所はありません. たぶん, グラフの実装を変更したりする必要がありますが, そこまではする気がないので, 最適化については一旦終わりとします. 改善努力の甲斐あって, N=1000で2秒台を出せたということで大変満足しています. Javaでやった時は500ms程度だったので, それに比べると遅いですが, 妥当な範囲だと思います.