fixedpoint.jp - An R6RS library for Longest Common Subsequence (LCS) の計測




An R6RS library for Longest Common Subsequence (LCS) の計測

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! でやっている処理に修正すべき点があるようです。やはり計測は重要です。

上で判明した問題を 963a267a09239cf0c2e1a548149bc24593e968bd で修正したところ、O(NP) 版のコードが移植したコードに比べて半分程度の時間で処理するようになりました。これは元の論文のアルゴリズムの評価に沿っていると思われます。

© 2006-2010 Takeshi Abe