正規表現

#/(?:aa?){n}a{n}/という正規表現(nは任意の数)がどれくらい遅くなるかをチェックしようとしたら正規表現のコンパイラがエラーを飛ばした。ソースを見ると特にコメントも無く、

/* ugh, ugly */

とだけある。(よくこういうのを書く。)問題はこう書いてあるということは何らかの問題があってそうせざるを得なかったはずなのだが、思い出せない。とりあえず、必要そうに見えないのでコメントアウトしてコンパイル。テストも全部通る。なんだったんだろう？問題が見つかったら考えることにしよう。こういうことが多々あるのだから、コメントは都度書くようにしないとなぁ。やっつけで直してコメント書かないことが多いから・・・(仕事ではそれを反面教師にしているのかまじめに書いてる)

っで、件の速度チェック。 ここを見て、Sagittariusではどうなるんだろう？と実験してみたかった。
これどうやってたんだっけな (正規表現・続々) - Island Life
見た感じO(n)の正規表現エンジンの方が使われるはずだからSagittariusではO(n^2)にはならないはずだけど、と思いつつ以下のコードで実験。

#< (sagittarius regex) >
(import (rnrs) (sagittarius regex) (srfi :42) (time)
 (sagittarius control))
;;(use srfi-42)
(define s (apply string (list-ec (: x 100) #\a)))
(print ((#/(?:aa?){40}a{40}/ s) 0))
(time
 (dotimes (i 100)
   (#/(?:aa?){40}a{40}/ s)))

いい加減、毎回正規表現のリーダーマクロを有効にするのが面倒だが、ライブラリをインポートしないと正規表現自体使えないからなぁ・・・
っで以下が結果。

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

;;  0.125000 real    0.125000 user    0.000000 sys

普通。単発で走らせた結果が、0.014くらいだったのでリニアだろう。単純な正規表現ならO(n)が保障されているのはそれなりに強みだろう。(エンジン自体が遅いので、微妙だけど・・・)