ファイル読み込み #2

R5RS を読んでいたら、append は

結果のリストは、最後のリスト引数と構造を共有する場合を除いて、必ず新しく割り当てられる。

Revised(5) Report on the Algorithmic Language Scheme

ということだった。実は昨日改善したつもりだった readfile2 は改悪なんじゃないかと思って、ベンチマークをとってみることにした。

;; 文字列ベース
(define (readfile filepath)
  (let ((port (open-input-file filepath)))
    (let loop ((contents "") (c (read-char port)))
      (if (eof-object? c)
        (begin
          (close-input-port port)
          contents)
        (loop (string-append contents (make-string 1 c)) (read-char port))))))

;; リストベース（append）
(define (readfile2 filepath)
  (let ((port (open-input-file filepath)))
    (let loop ((contents '()) (c (read-char port)))
      (if (eof-object? c)
        (begin
          (close-input-port port)
          (list->string contents))
        (loop (append contents (cons c '())) (read-char port))))))

;; ベンチマーク
(define (benchmark4 fn st)
  (use srfi-19)
  (let loop ((c '0))
    (if (= c 5)
      (time-difference (current-time) st)
      (begin
        (fn "C:\\test.txt")
        (loop (+ c 1))))))

;; ベンチマーク実施
(benchmark4 readfile (current-time))
(benchmark4 readfile2 (current-time))

読み込むテキストのサイズは大体 80KB。

僕の環境だと、以下のような結果になった。

方法	時間
string-append	39.6 秒
append	189.6 秒

やっぱり改悪だった λ...

でも string-append も実用にならない遅さ。

もしやと思って作ってみたのが cons ベースの読み込み。

;; リストベース（cons）
(define (readfile3 filepath)
  (let ((port (open-input-file filepath)))
    (let loop ((contents '()) (c (read-char port)))
      (if (eof-object? c)
        (begin
          (close-input-port port)
          (list->string (reverse contents)))
        (loop (cons c contents) (read-char port))))))

;; ベンチマーク
(benchmark4 readfile3 (current-time))

方法	時間
cons	0.04 秒

おおっ！超劇的に速いじゃないですか（処理系は Gauche です）。

リストの並びが逆になってしまう点、なので最後にひっくり返さなきゃならない点などが「なんだかな〜」という感じだったんだけど、これは Scheme の定石なんですかね。

この手続きはペアを新しく割り当てて返し、そのcarはobj1、cdrはobj2である。

Revised(5) Report on the Algorithmic Language Scheme

なるほど。ペアは新しく割り当てられるけど、car も cdr も元々のものを流用するから速いわけだ。