読者です 読者をやめる 読者になる 読者になる

Suffix-Arrayの逆襲

ocaml

http://d.hatena.ne.jp/komamitsu/20090503/1241369214

  • List使って書いたら遅かった
  • Array.append使ってSuffix-Arrayを構築したら全然処理が終わらなかった

としょうもない感じだったので、改善してみました(http://github.com/komamitsu/ocaml-suffixarray)。



具体的には以下。

  • ListでなくてArrayに変えて
  • Suffix-Arrayを構築する際は「Array.append連発」など危険なこと(内部的にはreallocしまくり?)はやらない


すると…
前回のベンチマークで、Str.search_forwordにボロ負けしていたアイツ(Suffix-Array)がやってくれました。

komamitsu@potato:~/git/ocaml-suffixarray$ ./sample3
text length is 50659.
regexp:       3.000000 sec
suffix array: 1.000000 sec