2009/10/14 に紹介していた http://github.com/tabe/lcs の速度の計測を行いました。対象はランダムに生成された文字のリストで、Gauche の util.lcs を移植したコードと比較しました。移植したコード: lcs.scm
手元のノートPC(CPU 1.6GHz)上の Ypsilon で試しました。実行時間が短くて済むように、データとして10から200までの長さのリストを引数に使いました:
ただし sample.(リストの長さ)-(LCS の長さ).scm を意味しています。
結果としては、移植したコードの方はいずれのデータでも1秒未満で LCS を返すのに対し、O(NP) 版のコードの方はより遅いです。特にリストの長さが100になった辺りからパフォーマンスの差が明らかになります。
どうやら O(NP) 版のコードの snake! でやっている処理に修正すべき点があるようです。やはり計測は重要です。