TIM Labs

SICP読書会(Exercise 3.22 - Exercise 3.23)

| コメント(0) | トラックバック(0)

これまでのあらすじ

弊社では新入社員の技術的な基礎体力向上を目的として SICP の読書会を一年半程前から毎週行っています。

毎回のまとめは参加者用のMLに流していたのですが、 よくよく考えると後から一覧したり検索したりし辛いので、 今後はこちらにポストしようと思います。

かなりスローペースで進めているため、 一年半経ってようやく3章に突入したところです。

前回は 3.3.2 Representing Queues を読んでExercise 3.21を解き、Exercise 3.22とExercise 3.23は宿題ということにしました。 という訳で宿題の答え合わせをしましょう。

Exercise 3.22

Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form

(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <definitions of internal procedures>
    (define (dispatch m) ...)
    dispatch))

Complete the definition of make-queue and provide implementations of the queue operations using this representation.

これはExercise 3.20の前座の「Mutation is just assignment」に出てきた手続き版 cons と同じ要領で作れば良いだけの話です。 テキスト中の実装と比較した場合、 front-ptrrear-ptr の読み書き方法が異なるくらいで、残りの実装はほぼ同じです。 という訳でテキスト中の実装を切り貼りしてちょちょいと直せば完成ですね。

Exercise 3.23

A deque ("double-ended queue") is a sequence in which items can be inserted and deleted at either the front or the rear. Operations on deques are the constructor make-deque, the predicate empty-deque?, selectors front-deque and rear-deque, and mutators front-insert-deque!, rear-insert-deque!, front-delete-deque!, and rear-delete-deque!. Show how to represent deques using pairs, and give implementations of the operations. [23] All operations should be accomplished in Θ(1) steps.

dequeはqueueと違って先頭からも末尾からも要素の追加/削除が可能です。 一つづつ検討しましょう:

  • front-insert-deque! ... queueには無い操作ですが、リストの先頭に新しく追加するのは散々やってきたパターンなので楽勝ですね。
  • front-delete-deque! ... queueと一緒ですから楽勝ですね。
  • rear-insert-deque! ... queueと一緒ですから楽勝ですね。
  • rear-delete-deque! ... queueには無い操作で、 rear-ptr はリストの最後から二番目の要素を指すよう変更する必要があります。

問題は rear-delete-deque! です。 「最後から二番目の要素」はつまり rear-ptr の指す要素の直前の要素なのですが、 今まで散々扱ってきたリストでは直後の要素はO(1)で辿れても直前の要素はO(1)で辿れません。 という事はqueueと同じ要領でやろうとしても rear-delete-deque! をO(1)で実装できないことになります。

という訳で今までのリストを使うのは止めて、 各要素が直前の要素へのポインターも持つ双方向リストをベースにしてdequeを実装しましょう。 双方向リストの各要素は値、直後の要素へのポインター、直前の要素へのポインターの3個のデータで構成されるので、 もはやconsセル1個では賄えません。つまり

  1. 双方向リストの要素のconstructor/selectors/mutatorsを作って、
  2. それらを利用してdequeを実装する

形になります。 queueに比べると若干複雑ですが、 このデータ構造の分離ができているなら実装するのはそう難しくはないですね。

次回予告

3.3.3 Representing Tables を読んで問題をバンバン解いていきます。 dequeよりさらに複雑なデータ構造を相手にすることになるので、しっかり復習しておきましょう。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/444

コメントする

このブログ記事について

このページは、kanaが2014年11月18日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「JavaScriptでシェフィを実装する(UI本格化編/操作性向上の巻)」です。

次のブログ記事は「SICP読書会(Section 3.3.3 - Exercise 3.25)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。