2011/10/21

思い立ったが吉日 (正規表現・続き)

昨日の話題の続きみたいなもの。

ときどきの雑記帖 濫觴編

ちょっと方向が違いますが、GNU の regex がマッチする文字列の先頭に来うる文字集合を チェックしてて、その集合に入ってない限り読み飛ばすということをしています。

この手はAllegro Common Lispのregexpに使ったんだけど、 Gaucheでは面倒でやっていなかったのだ。 話題に上ったのも何かの縁なので、ちょいと実装してみた。

こんな意地悪なベンチマークだと：

(use gauche.time)
(use text.tree)

(define s
  (tree->string `(,(make-list 1000 `(,(make-string 1000 #\a) "01:23")) ":45")))

(print (time-this 50 (^[] (#/\d\d:\d\d:\d\d/ s))))

こんな感じ。効果ありますなー。

0.9.2
#<time-result 50 times/  8.709 real/  8.680 user/  0.020 sys>

改良版
#<time-result 50 times/  0.354 real/  0.360 user/  0.000 sys>

さらに、昨日のエントリで書いた

もし入力の先頭から調べて/A+B/がマッチしなかったら、その入力から/A/にマッチするプリフィクスを好きなだけ取り除いた入力文字列にもマッチしないはずである。(ただしAとBの先頭文字集合は排他)

(追記2011/10/22 20:22:53 UTC: AとBの先頭文字集合が排他である必要はないか。重なる分についても既に試してだめなことがわかってるんだから。)

(追記2011/10/23 01:38:47 UTC: いや、先頭文字集合が排他でない場合、A+が最後にマッチした終端を覚えといてそこを行きすぎないようにしないとだめだ。ところで文字列先頭からA+がマッチした場所までというのは、既にAで一回マッチを試みているのだから、再びスキップのために先頭から調べる必要はない。「A+がマッチした終端を覚えといて、全体が失敗したらその場所の次から始めよ」っていう情報をつけとけばいい。さらに先頭のA+だけに限らず、途中の部分正規表現についても、「これが失敗したなら、次はここから始めていいよ」という情報をあらかじめ計算しておける可能性がある。KMP searchのrestart vectorみたいな発想。これをやってる実装はあるかなあ。)

というのも実装してみた。Aにマッチする文字列が複数文字だとスキップの条件がややこしいので、Aは文字か文字セットに限っているが。 昨日のベンチマークを使うとこのとおり。

0.9.2:
80:     #<time-result 20 times/  0.001 real/  0.000 user/  0.000 sys>
400:    #<time-result 20 times/  0.010 real/  0.010 user/  0.000 sys>
800:    #<time-result 20 times/  0.037 real/  0.030 user/  0.000 sys>
4000:   #<time-result 20 times/  0.885 real/  0.890 user/  0.000 sys>
8000:   #<time-result 20 times/  3.510 real/  3.500 user/  0.000 sys>

改良版:
80:     #<time-result 20 times/  0.000 real/  0.000 user/  0.000 sys>
400:    #<time-result 20 times/  0.000 real/  0.000 user/  0.000 sys>
800:    #<time-result 20 times/  0.000 real/  0.000 user/  0.000 sys>
4000:   #<time-result 20 times/  0.001 real/  0.000 user/  0.000 sys>
8000:   #<time-result 20 times/  0.002 real/  0.000 user/  0.000 sys>

しまった速すぎてオーダーがわからん。繰り返し回数を1000倍してみる。

改良版:
80:     #<time-result 20000 times/  0.051 real/  0.050 user/  0.000 sys>
400:    #<time-result 20000 times/  0.120 real/  0.120 user/  0.000 sys>
800:    #<time-result 20000 times/  0.207 real/  0.200 user/  0.000 sys>
4000:   #<time-result 20000 times/  0.908 real/  0.910 user/  0.000 sys>
8000:   #<time-result 20000 times/  1.785 real/  1.790 user/  0.000 sys>

O(n)になってるっぽいですな。というか数値的にはリニアよりも下に振れてる 感じだけど、これはマッチごとのコンスタントなオーバヘッドがあるからじゃないかな。

前者の、マッチ可能な先頭文字集合でスキップするのはAllegroのregexpを書いた時に 効果を確かめてる。後者のは、最適化が効く条件が結構複雑だけれど、 現実のシチュエーションでは案外多いんじゃないかという気がする。

妙なバグを入れてないかどうか、もう一晩くらい寝かせてからpushするつもりだけど、 現在のHEADに対するパッチはこちら→ https://gist.github.com/1305809

Tags: Programming, Gauche