ついに0時を回ってしまった. 会社での仕事に満足行かないから*1家でコードを書く. プログラマにとっては自然なことだ.

リーフノードのパッキングを計算で行うことで性能改善が可能であるという話をした. その実装を行って再度, ベンチマークを実行した. 実行は, Python 2.7を用いた. 比較のため, この最適化あり/なしを並べる.

顕著に改善した. N=1000の時, およそ6倍の改善が見られている. しかし私の記憶では, Javaで実装した時はN=1000の時に500msだったわけだから, まだ20倍ほど遅い. なぜだ. 常識的に考えると, JavaとPythonの差となるだろうが, ピュアな計算ならともかく, 実際のアプリケーションで20倍は大きすぎやしないかと思う. 最適化オプションがあったりするのかも知れない. とりあえず, N=1000の時に5secを目標にする. ここから2倍である. 解析と改善を適切に行えば十分に到達出来るように思う. Pythonアプリケーションの性能改善問題と思って努力してみる.

追記

このグラフを見ると, improvedの方は少しカーブしていることが分かる. N=100の時には0.2秒程度だが, N=1000では10秒になっている. これは, RectanglePackingのオーダがやはりO(N²)であることを意味する.

近似のため, これらのカーブ(最適化あり/なしの順)をa N² + b_1 N, a N² + b_0 N (Nは100で割って正規化する)と置くと, 大体, a = 0.08, b_0 = 0.2, b_1 = 5となることが分かる. したがって, リーフノード配置の最適化は局所的に25倍の性能向上があったが, 長方形配置が本質的にN²オーダなのが響いてしまって遅いのだと分かる. もし, 第一項が線形オーダならば, N=1000の時に2秒程度のはずである.

この性能の悪さが実装に依るものなのか, アルゴリズムの特性そのものなのか切り分けは出来ないが, 解析することは出来そうである. しかし少なくともJavaでやった時は, こんなことはなかった. 実装がPython向けでないかPythonがやはり遅いのか, いずれかであるように思う.