Gaucheで文字列のシーケンシャルアクセス

Gaucheでそこそこサイズの大きい文字列へのシーケンシャルアクセスをしたい場合の注意点です。

例として、以下のURLにある『吾輩は猫である』の文書中に、何回「猫」という文字が出てくるかを調べてみましょう。

http://www.aozora.gr.jp/cards/000148/card789.html#download

$ wget http://www.aozora.gr.jp/cards/000148/files/789_ruby_5639.zip
$ unzip 789_ruby_5639.zip 
$ nkf -w wagahaiwa_nekodearu.txt > neko_utf8.txt
$ ls -lh neko_utf8.txt 
-rw-rw-r-- 1 cloudear8 cloudear8 1.1M 11月 13 22:26 neko_utf8.txt

このneko_utf8.txtをGaucheから読み込んでみます。

(define book (call-with-input-file "/path/to/neko_utf8.txt"
               port->string))

(string-length book) ; => 377272

この37万7272文字の文書から、「猫」という文字の数をカウントしてみましょう。

(define (count-neko1 book)
  (let loop ((count 0)
             (i 0))
    (if (<= (string-length book) i)
        count
        (let ((c (string-ref book i)))
          (if (char=? c #\猫)
              (loop (+ count 1) (+ i 1))
              (loop count (+ i 1)))))))

(count-neko1 book) ; => 終わらない

たかだか377272回のループのはずが、この関数は非常に実行に時間がかかってしまいます。
では、この関数の実行時間のオーダーはどれくらいになっているのでしょうか。bookの部分文字列に対してcount-neko1を呼んでみましょう。

(time (count-neko1 (substring book 0 1000)))
;;(time (count-neko1 (substring book 0 1000)))
;; real   0.003
;; user   0.010
;; sys    0.000

(time (count-neko1 (substring book 0 2000)))
;;(time (count-neko1 (substring book 0 2000)))
;; real   0.011
;; user   0.020
;; sys    0.000

(time (count-neko1 (substring book 0 4000)))
;;(time (count-neko1 (substring book 0 4000)))
;; real   0.044
;; user   0.050
;; sys    0.000

(time (count-neko1 (substring book 0 16000)))
;;(time (count-neko1 (substring book 0 16000)))
;; real   0.670
;; user   0.660
;; sys    0.000

ざっと概算して、だいたいn^2くらいのオーダーになっていることがわかるでしょうか。
実はこれはGaucheの文字列の仕様によるものが原因です。

Gaucheの文字列は文字の配列ではなく、ただのバイト列を動的に解析して文字として扱っています。UTF-8等の文字コードでは1文字のバイト数が一定ではないため、(string-ref book i)が呼ばれるたびにbookを頭から読み込み、どこからどこまでが1文字なのかを順番に調べ、i番目の文字にたどり着いたところでその値を返しているのです。

実際に、string-refの実行時間を計測することで、おおよそのオーダーを測ってみましょう。

(use gauche.time)
(time-this 10000 (^() (string-ref book 10)))
;; => #<time-result 10000 times/  0.003 real/  0.010 user/  0.000 sys>
(time-this 10000 (^() (string-ref book 100)))
;; => #<time-result 10000 times/  0.006 real/  0.010 user/  0.000 sys>
(time-this 10000 (^() (string-ref book 1000)))
;; => #<time-result 10000 times/  0.051 real/  0.050 user/  0.000 sys>
(time-this 10000 (^() (string-ref book 10000)))
;; => #<time-result 10000 times/  0.530 real/  0.520 user/  0.000 sys>

大体nくらいのオーダーであることがわかります。

では、文字列の先頭から順に定数時間でアクセスするためにはどうすればよいでしょうか？

答えは、文字列ポートを使用する方法です。
文字列ポートは現在の読み込み位置を内部に持っているので、定数時間で次の文字にアクセスすることができます。

文字列ポートを使ってcount-neko1を書き換えてみましょう。

(define (count-neko2 book)
  (with-input-from-string book
    (^()
      (let loop ((count 0))
        (define c (read-char))
        (cond
         ((eof-object? c) count)
         ((char=? c #\猫) (loop (+ count 1)))
         (else (loop count)))))))

(count-neko2 book) ; => 263

(time (count-neko2 book))
;;(time (count-neko2 book))
;; real   0.082
;; user   0.110
;; sys    0.010

今度は現実的な時間で実行を終えることができました。

Gaucheで文字列のシーケンシャルアクセス

関連記事