Generatorの勧め

Schemeでリスト処理を書いていると中間リスト(処理の最中に作成されて捨てられるリスト)の存在が気にならないだろうか？ClojureにはTransducersがあるのにSchemeにはないのだろうか？そこでGeneratorである。

Generatorは元もとGaucheに実装されていたもので割と最近SRFIになったもの。これ自体は引数を取らない手続きかつ処理が終了するとEOFを返すというものである。（GaucheのGeneratorも元をたどるとPython辺りからインスパイアされたらしい（要出典）） このGeneratorのSRFIは紆余曲折あって2種類ある。SRFI-121とSRF-158だ。SRFI-158はSRFI-121の上位互換なので、サポートされているのであればそちらを使った方がよい。（ちなみに、Sagittariusは両方サポートしている）

では、これを使って中間リストの削減をしてみる。 まずは以下のような処理を書く。処理自体に特に意味はない。

(filter (lambda (x) (zero? (mod x 3)))                     ;; 最終リスト
        (map cdr                                           ;; 中間リスト
             (filter (lambda (x) (odd? (car x)))           ;; 中間リスト
                     (map (lambda (x) (cons x (square x))) ;; 中間リスト
                          (iota 1000))))))                 ;; 初期リスト

この処理では計3つの中間リストが存在する。iotaで作成されるものも含めると4つになる。Generatorを使うと以下のように減らすことができる。

(generator->list ;; リストの生成はここだけ
 (gfilter (lambda (x) (zero? (mod x 3)))
          (gmap cdr
                (gfilter (lambda (x) (odd? (car x)))
                         (gmap (lambda (x) (cons x (square x)))
                               (make-iota-generator 1000))))))

ここではmake-iota-generatorを使っているが、(list->generator (iota 1000))と書くと、既存の初期リストをGeneratorに変換するような処理になる。

見た目はほぼ同じ（よく目を細めるように）、ならば気になるのは性能だろう。ということでベンチマークを取ってみる。使うスクリプトは以下。

(import (scheme base)
        (scheme write)
        (srfi 1)
        (srfi 158)
        (time))

(define size 1000)
(define (target1)
  (filter (lambda (x) (zero? (mod x 3)))
          (map cdr
               (filter (lambda (x) (odd? (car x)))
                       (map (lambda (x) (cons x (square x)))
                            (iota size))))))


(define (target2)
  (generator->list
   (gfilter (lambda (x) (zero? (mod x 3)))
            (gmap cdr
                  (gfilter (lambda (x) (odd? (car x)))
                           (gmap (lambda (x) (cons x (square x)))
                                 (make-iota-generator size)))))))


(define count 1000)
(define-syntax dotimes
  (syntax-rules ()
    ((_ n expr ...) (do ((c n) (i 0 (+ i 1))) ((= c i)) expr ...))))

;; GCの結果も見るため、交互に計測する
(time (dotimes count (target1))) 
(time (dotimes count (target2)))

結果は以下の通り。

# 中間リスト作成版
$ sash -s test.scm

;;  (dotimes count (target1))
;;  0.385681 real    0.688000 user    0.000000 sys

;; Statistics (*: main thread only):
;;  GC: 21389312bytes heap, 293849719bytes allocated, 49 gc occurred

# Generator版
$ sash -s test.scm

;;  (dotimes count (target2))
;;  0.386407 real    0.480000 user    0.000000 sys

;; Statistics (*: main thread only):
;;  GC: 28368896bytes heap, 198322311bytes allocated, 28 gc occurred

性能に大きな差はないが、GC回数と割り付けられたメモリに大きな差がある。

メモリの圧迫が気になるときに思い出したように使うといいかもしれない。