O(n^2)正規表現(from Island Life)

Gaucheの河合史郎さんのBlogのエントリーO(n^2)の正規表現をみて、そういえばSagittariusでは正規表現のベンチマークとったことないなぁと思いやってみた。 そのままでは当然動かないので、コンバート。
こんな感じ。

(import (sagittarius regex)
 (srfi :1)
 (srfi :13)
 (rnrs))

(define format.6f
  (lambda (x)
    (let* ((str (number->string (/ (round (* x 1000000.0)) 1000000.0)))
           (pad (- 8 (string-length str))))
      (if (<= pad 0)
          str
          (string-append str (make-string pad #\0))))))

(define-syntax time
  (syntax-rules ()
    ((_ expr)
     (let-values (((real-start user-start sys-start) (time-usage)))
       (let ((result (apply (lambda () expr) '())))
         (let-values (((real-end user-end sys-end) (time-usage)))
           (let ((real (format.6f (- real-end real-start)))
                 (user (format.6f (- user-end user-start)))
                 (sys  (format.6f (- sys-end sys-start))))
             (format #t "~%;;  ~a real    ~a user    ~a sys~%" real user sys)
        (flush-output-port (current-output-port))))
         result)))))

(define (time-this runs thunk)
  (time
   (do ((i 0 (+ i 1)) (r (thunk) (thunk)))
       ((= i runs)))))
       
(define rx1 (regex "[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+"))

(define (regex-test rx text runs)
  (display (string-length text))
  (time-this runs (lambda () (regex-replace-all rx text " "))))

(define (repeat s c) (string-concatenate (make-list c s)))

(print rx1)
(regex-test rx1 (repeat "abcdefgh" 10) 20)
(regex-test rx1 (repeat "abcdefgh" 50) 20)
(regex-test rx1 (repeat "abcdefgh" 100) 20)
(regex-test rx1 (repeat "abcdefgh" 500) 20)
(regex-test rx1 (repeat "abcdefgh" 1000) 20)

結果は散々であった。以下結果。(Core2Duo 3GHz)

#
80
;;  0.005000 real    0.000000 user    0.000000 sys
400
;;  0.100000 real    0.110000 user    0.000000 sys
800
;;  0.400000 real    0.375000 user    0.000000 sys
4000
;;  9.965000 real    9.937000 user    0.000000 sys
8000
;;  39.94300 real    39.70300 user    0.000000 sys

いやぁ、速くはないだろうなぁとは思っていたが、ここまで遅いとは。
Sagittariusの正規表現はJavaのコードを流用(もちろんCに書き直したが)しているので、マッチしなかったら一文字進めて再試行するようになっているので、入力文字列がマッチしないと結構不利にはなる。特にregex-replace-allみたいなのは痛い。
今回のケースだと、クラスのマッチはあんまり遅くないんだよなぁ、組み込みのcharsetを入れても改善の余地は少なさそう。さて、どうしようかね。