重複順列パフォーマンス比較
重複順列の話 その４
何点かチューニングをしました。
- xrange() をリストへ置換
- ローカルスコープでの名前束縛の制限
1.は全般に言えることですが、呼び出し回数の多い関数内での for ループは、毎回 xrange() でまわすより、あらかじめ range() でリストを作っておいて同じインスタンスを使いまわす方が早い。
2.も当然ですね。最初、その２で作ったイテレータクラスの increment() 内でインスタンス変数の self を省略する目的でローカル変数に代入していました。このincrement()関数も呼び出し回数が多いためバカにならないコストになっていました。
この二つのチューニングで、特にイテレータクラスなどは 5% ほど高速化されました。
計測結果
| CPU | Core2Quard Q6600 (2.4GHz) |
| RAM | 4 GB |
| OS | Win Vista Ultimate 32bit |
| Python Ver. | 2.5.2 |
| 処理時間 (秒) | 最速との比 | モジュール | 関数/クラス | 備考 |
|---|---|---|---|---|
| 0.22569 | 1.00 | EvalPerm | repeated_permutation_n (7,7) | 文字列 + eval |
| 0.29667 | 1.31 | EvalPerm | repeated_permutation (7,'ABCDEFG') | 文字列 + eval |
| 0.34611 | 1.53 | NonRecurseGenPerm | repeated_permutation_n (7,7) | 再帰なしジェネレータ |
| 0.59794 | 2.65 | RecurseGenPerm | repeated_permutation (7,range(7)) | 再帰ジェネレータ |
| 0.72746 | 3.22 | RecurseGenPerm | repeated_permutation (7,'ABCDEFG') | 再帰ジェネレータ |
| 0.94852 | 4.20 | NonRecurseGenPerm | repeated_permutation_b (7,'ABCDEFG') | 再帰なしジェネレータ |
| 1.64705 | 7.30 | IterClassPerm | RepeatedPermutationN (7,7) | イテレータクラス |
| 2.99146 | 13.25 | IterClassPerm | RepeatedPermutationB (7,'ABCDEFG') | イテレータクラス |
"for x in EvalPerm.repeated_permutation_n(7,7): pass" のようなステートメントを作って timeit で計測。
一番速かったのは、文字列で作ったジェネレータ式を eval する方式でした。邪道だと思ってたんですがこれだけ速度が出るなら無視できませんね。ただメンテナンス性と、セキュリティ上の問題があるのが困りものです。
遅かったのはイテレータクラスの２つ。リストを使ったD桁N進数カウンタ increment 処理がネックになっていたようです。ほぼ同じロジックの「再帰なしジェネレータ」が数倍早いところを見ると、イテレータよりジェネレータの方が効率いいのかな。
不思議なことにイテレータクラスの内部バッファを list から array にしたら遅くなっしまった。一般的に array のほうが速いものだと思っていたけど、そう単純ではないのかな。
再帰なしジェネレータは、数値列挙と文字列列挙で大きな差が出ました。これは構造的なものでしょう。
数値列挙が「再帰ジェネレータ」より速かったのは、バッファが固定バッファだったからだと思うけど、どうだろう。
文字列列挙が遅かったのは、数値列挙で出た解を置き換えるという仕組みのオーバヘッドが大きかったから。
コード的にはシンプルで綺麗な再帰ありのジェネレータは、可も無く不可もなくという感じでした。
