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