SICP 3.3.2 Representing Queues
ノート
待ち行列の表現
ここでは後ろから詰めて前から出す方式。と言うのも後で分かるが最後の要素を削除するのは意外と厄介なので、自然と削除は先頭からとなる。一番後ろを見つけるのに手前から一つずつ追っていたのでは要素数が大きくなった時に非効率なので最初と最後のポインタを持つ。
Exercise 3.21
まず例を実際に動かす。set**とerrorが共存する最も面倒な構成だが、DrRacketでは以下の構成で実行する。
#lang scheme (require r5rs)
実行結果
> (insert-queue! q1 'a) {{a} a} > (insert-queue! q1 'b) {{a b} b} > (delete-queue! q1) {{b} b} > (delete-queue! q1) {() b} >
Explain what Eva Lu is talking about. In particular, show why Ben's examples produce the printed results that they do.
q1が指しているセルをリストと見立てて表示されるので、carがqueueの先頭からのリスト、cdrがそのリストの末尾をさす事になり、必ず末尾は２回表示される事になる。またdelete-queue!ではfront-ptrしか変更していないのでrear-ptrは元の要素を指したままであり、q1を表示するとそれが現れてしまう。
キューの中身だけを表示するにはcar側のリストを表示すれば良い。値として返せばREPLが表示しますが、それではprintと言う手続きではないので積極的に表示させます。
(define (print-queue q) (display (car q))(newline))
実行結果
> (define q1 (make-queue)) > (print-queue q1) () > (insert-queue! q1 'a) {{a} a} > (print-queue q1) (a) > (insert-queue! q1 'b) {{a b} b} > (print-queue q1) (a b) > (delete-queue! q1) {{b} b} > (print-queue q1) (b) > (delete-queue! q1) {() b} > (print-queue q1) () >
Exercise 3.22
メッセージ、メソッドにいちいちqueueを付ける必要は無し。引数としてqueueを渡す必要も無し。引数が必要なinsert!のみ手続きを返すが、それ以外はそのまま実行。printもメソッドとして含める。
#lang scheme (require r5rs) (define (make-queue) (let ((front-ptr null) (rear-ptr null)) (define (set-front-ptr! item) (set! front-ptr item)) (define (set-rear-ptr! item) (set! rear-ptr item)) (define (empty?) (null? front-ptr)) (define (insert! item) (let ((new-pair (cons item '()))) (cond ((empty?) (set-front-ptr! new-pair) (set-rear-ptr! new-pair) front-ptr) (else (set-cdr! rear-ptr new-pair) (set-rear-ptr! new-pair)))) front-ptr) (define (delete!) (cond ((empty?) (error "DELETE! called with an empty queue")) (else (set-front-ptr! (cdr front-ptr)))) front-ptr) (define (dispatch m) (cond ((eq? m 'empty?) (empty?)) ((eq? m 'front) front-ptr) ((eq? m 'insert!) insert!) ((eq? m 'delete!) (delete!)) ((eq? m 'print) (display front-ptr)(newline)) (else (error "Unknown method" m)))) dispatch))
実行結果
> (define q1 (make-queue)) > (q1 'empty?) #t > (q1 'front) () > (q1 'print) () > ((q1 'insert!) 'a) {a} > (q1 'empty?) #f > (q1 'front) {a} > (q1 'print) (a) > ((q1 'insert!) 'b) {a b} > (q1 'empty?) #f > (q1 'front) {a b} > (q1 'print) (a b) > (q1 'delete!) {b} > (q1 'empty?) #f > (q1 'front) {b} > (q1 'print) (b) > (q1 'delete!) () > (q1 'empty?) #t > (q1 'front) () > (q1 'print) () >
Exercise 3.23
両方から出し入れ出来るdequeの実装。メソッドが全て関数とする事を前提としている様なのでlocal stateではなくpairを使った実装とする。問題は最後の要素をどうやって削除するのか。その一つ前の要素を指すものが必要。と言う事は双方向リストである必要がある。ポイントする先は保存する要素、前のセルへのポインタ、後ろのセルへのポインタなので、必然的に前後のセルへのポインタを持つセルと、要素とそのセルを指すセルの二つひと組となる。
#lang scheme (require r5rs) (define (make-cell item) (cons item (cons '() '()))) (define (connect-cells! a b) (set-next-ptr! a b) (set-prev-ptr! b a)) (define (set-prev-ptr! cell prev) (if (null? cell) '() (set-car! (cdr cell) prev))) (define (set-next-ptr! cell next) (if (null? cell) '() (set-cdr! (cdr cell) next))) (define (prev-cell cell) (cadr cell)) (define (next-cell cell) (cddr cell)) (define (make-deque) (cons '() '())) (define (front-ptr deque) (car deque)) (define (rear-ptr deque) (cdr deque)) (define (set-front-ptr! deque item) (set-car! deque item)) (define (set-rear-ptr! deque item) (set-cdr! deque item)) (define (empty-deque? deque) (null? (front-ptr deque))) (define (front-insert-deque! deque item) (let ((new-cell (make-cell item))) (cond ((empty-deque? deque) (set-front-ptr! deque new-cell) (set-rear-ptr! deque new-cell)) (else (connect-cells! new-cell (front-ptr deque)) (set-front-ptr! deque new-cell)))) deque) (define (rear-insert-deque! deque item) (let ((new-cell (make-cell item))) (cond ((empty-deque? deque) (set-front-ptr! deque new-cell) (set-rear-ptr! deque new-cell)) (else (connect-cells! (rear-ptr deque) new-cell) (set-rear-ptr! deque new-cell)))) deque) (define (front-deque deque) (if (empty-deque? deque) (error "FRONT called with an empty deque" deque) (car (front-ptr deque)))) (define (rear-deque deque) (if (empty-deque? deque) (error "REAR called with an empty deque" deque) (car (rear-ptr deque)))) (define (front-delete-deque! deque) (cond ((empty-deque? deque) (error "DELETE! called with an empty deque" deque)) (else (begin (set-front-ptr! deque (next-cell (front-ptr deque))) (set-prev-ptr! (front-ptr deque) '()) (if (null? (front-ptr deque)) (set-rear-ptr! deque '()) '())))) deque) (define (rear-delete-deque! deque) (cond ((empty-deque? deque) (error "DELETE! called with and empty deque" deque)) (else (begin (set-rear-ptr! deque (prev-cell (rear-ptr deque))) (set-next-ptr! (rear-ptr deque) '()) (if (null? (rear-ptr deque)) (set-front-ptr! deque '()) '())))) deque)
動作確認。まずは双方向リストのセルについて。
> (define a (make-cell 'a)) > (define b (make-cell 'b)) > (define c (make-cell 'c)) > (connect-cells! a b) > (prev-cell a) () > (next-cell a) #0={b {a () . #0#}} > (eq? b (next-cell a)) #t > (prev-cell b) #0={a () b #0#} > (eq? a (prev-cell b)) #t > (connect-cells! b c) > (eq? c (next-cell (next-cell a))) #t > (eq? a (prev-cell (prev-cell c))) #t >
dequeの部分。
> (define d (make-deque)) > (empty-deque? d) #t > (front-insert-deque! d 'a) {{a ()} a ()} > (empty-deque? d) #f > (front-deque d) a > (rear-deque d) a > (front-insert-deque! d 'b) {#0={b () . #1={a #0#}} . #1#} > (front-deque d) b > (rear-deque d) a > (rear-insert-deque! d 'c) {#0={b () . #1={a #0# . #2={c #1#}}} . #2#} > (front-deque d) b > (rear-deque d) c > (front-delete-deque! d) {#0={a () . #1={c #0#}} . #1#} > (front-deque d) a > (rear-delete-deque! d) {{a ()} a ()} > (front-deque d) a > (rear-deque d) a > (front-delete-deque! d) {()} > (empty-deque? d) #t > (front-insert-deque! d 'e) {{e ()} e ()} > (rear-deque d) e > (rear-delete-deque! d) {()} > (empty-deque? d) #t >
一応期待通り。全ての操作はfront-ptrかrear-ptrからアクセスして、一つ以上セルを手繰る事はないのでΘ(1)と言える。
