append が気になる

Scheme 関連の記事が書かれているブログを巡回していてこんな記事を見掛けた。

Scheme に慣れた人ならこのコードで append を使っている部分が気になるのではないだろうか。 私はとても気になる。 そんなわけでどう気になるのか解説してみることにした。 比較的初心者向けの内容だと思う。

Schemeappend は複数のリストをくっつけてひとつのリストにしたものを返す。 最後の引数として渡されたリストのみが返されたリストと共有された状態になる。 つまり、最後の引数以外はコピーされるのだ。

例としてこんなものを考えてみよう。

(define X '(A B C))
(define Y '(D))
(define Z (append X Y))

このとき変数 X, Y, Z はどのような構造になっているのかを図で表すとこうなる。

f:id:SaitoAtsushi:20140328184232p:plain

変数 X の内容はコピーされた上で最後のペアの cdr フィールドが変数 Y と同じものを指していることがわかる。

ではひとつのオブジェクトをリストの先頭にくっつける場合、つまりこんな例を考えてみる。

(define X '(A B C))
(define Y 'D)
(define Z (cons Y X))

図で表わすと

f:id:SaitoAtsushi:20140328184336p:plain

となり、コピーは発生していない。 この操作が Scheme で頻繁に用いられるのは、メモリアロケーションもなく、リストを辿ることさえ不要であるため効率的だからだと思う。

もちろん append が悪者というわけではない。 コピーが必要な場合もあるし、対象リストが充分に小さいことがわかっている場合に少々のメモリ効率のためにプログラムを複雑にするのも馬鹿馬鹿しい。 しかし、繰返しの中に append が現れるのは悪いサインの場合がある。

試しに、リストを逆順に並べ換える手続きを append を用いて書いてみよう。

(define (bad-reverse ls)
  (if (null? ls)
      '()
      (append (bad-reverse (cdr ls)) (list (car ls)))))

(define X '(A B C D E))
(define Y (bad-reverse X))

このときのデータ構造はこんな感じだ。

f:id:SaitoAtsushi:20140328184345p:plain

手続きから返ってきた時点において、赤枠で囲んだ範囲にあるオブジェクト (ペア) はどこからも参照されない。 つまりはゴミだ。 GC に回収される運命にある。

同じものをより効率的に書くとこうなる。

(define (good-reverse ls)
  (let loop ((m '())
             (ls ls))
    (if (null? ls)
        m
        (loop (cons (car ls) m) (cdr ls)))))

(define X '(A B C D E))
(define Y (good-reverse X))

f:id:SaitoAtsushi:20140328184358p:plain


出力結果分以外はアロケートされていない。

これを先程の bad-reverse と比較してみよう。 要素数が n とすると bad-reverse がアロケートするペアの個数は n2/2 である。 good-reverse が必要な分である n 個しかアロケートしないことを考えると、 bad-reverse はメモリ使用量のオーダーがひとつ次元が大きいわけで、とても非効率的だ。

データ構造がどうなっているのかを意識して書くと劇的に効率的になったりしますよという話。

Document ID: f6962cf26977df9a9083f7b82f018186