Scheme 関連の記事が書かれているブログを巡回していてこんな記事を見掛けた。
Scheme に慣れた人ならこのコードで append
を使っている部分が気になるのではないだろうか。 私はとても気になる。 そんなわけでどう気になるのか解説してみることにした。 比較的初心者向けの内容だと思う。
Scheme の append
は複数のリストをくっつけてひとつのリストにしたものを返す。 最後の引数として渡されたリストのみが返されたリストと共有された状態になる。 つまり、最後の引数以外はコピーされるのだ。
例としてこんなものを考えてみよう。
(define X '(A B C)) (define Y '(D)) (define Z (append X Y))
このとき変数 X
, Y
, Z
はどのような構造になっているのかを図で表すとこうなる。
変数 X
の内容はコピーされた上で最後のペアの cdr
フィールドが変数 Y
と同じものを指していることがわかる。
ではひとつのオブジェクトをリストの先頭にくっつける場合、つまりこんな例を考えてみる。
(define X '(A B C)) (define Y 'D) (define Z (cons Y X))
図で表わすと
となり、コピーは発生していない。 この操作が 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))
このときのデータ構造はこんな感じだ。
手続きから返ってきた時点において、赤枠で囲んだ範囲にあるオブジェクト (ペア) はどこからも参照されない。 つまりはゴミだ。 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))
出力結果分以外はアロケートされていない。
これを先程の bad-reverse
と比較してみよう。 要素数が n とすると bad-reverse
がアロケートするペアの個数は n2/2 である。 good-reverse
が必要な分である n 個しかアロケートしないことを考えると、 bad-reverse
はメモリ使用量のオーダーがひとつ次元が大きいわけで、とても非効率的だ。
データ構造がどうなっているのかを意識して書くと劇的に効率的になったりしますよという話。
Document ID: f6962cf26977df9a9083f7b82f018186