切符パズルのプログラムを gprof を使って改良
5桁の問題を解こうとすると、だいたい1時間くらいかかっていたのを改良して、2秒くらいまでチューニングした。つまり、約1800倍速くなった。
最初は遅い原因が、データを線形リストで扱っているところにあるとあたりをつけて、ランダムアクセスできるように配列を使えばそこそこ速くなるだろうと思っていたけど、あまり効果はなかった。
そこで、プロファイリングツールの存在を思いだし、C言語で何かつかえるものがあるだろうと思って探したら、GNU gprofを発見。こいつでプロファイリングしてみると、式木の複製が死ぬほどたくさん行なわれていることが判明。理論のわかりやすさのために、式木を無駄に複製していた部分を見つけたので、そこで複製しないようにしたら圧倒的に速くなった。再帰的に膨大な数のデータを生成するときは、微々たる負荷の削減が大きく効いてくることを改めて実感。
