純粋関数型データ構造より, BatchedQueue

純粋関数型データ構造という書籍を購入しました.

元々, 原著(PFDS)のほうに興味があったものの読んだことがなかったのですが, 訳書が出るということで購入してみたものになります.

下記は書籍内に登場する非破壊的なキュー実装の一つ BatchedQueueをSchemeで素朴に実装したもの:

;; 空のキュー
(define empty-queue (cons '() '()))
;; 先頭部分リストfと末尾逆順リストrからキューを構築
(define (queue-cons f r)
  (if (null? f) (cons (reverse r) '())
                (cons f r)))
;; キューは空?
(define (queue-empty? q)
  (null? (car q)))
;; キューの先頭要素
(define (queue-head q)
  (if (queue-empty? q) (error "invalid operator"))
  (caar q))
;; 先頭要素を取り除いた新しいキュー
(define (queue-tail q)
  (if (queue-empty? q) (error "invalid operator"))
  (queue-cons (cdar q) (cdr q)))
;; 末尾に要素を追加した新しいキュー
(define (queue-push q i)
  (queue-cons (car q) (cons i (cdr q))))
  • キューの先頭要素の取得 queue-head
  • キューの先頭要素を取り除いた新しいキューの生成 queue-tail
  • キューの末尾に要素を追加した新しいキューの生成 queue-push

この3点が基本的な操作関数です.

いずれも非破壊的な手続きのため, 古いキューにも永続的にアクセスできます.

この実装はキューの内部実装を 先頭の部分リスト f := (car q) と末尾の逆順部分リスト r := (cdr q) の対で構成します.

この2つのリストに分割することで, 先頭と末尾に素早くアクセスできるため, 通常ケースでは効率よく動作する queue-pushqueue-tail を定義することができます.

ただしキューの再構築時に f が空リストになるタイミングで, r の逆リストを生成して新しい f にするため (reverse r) を実行するコストを支払います.

ただし (reverse r) にかかるコストは queue-push された回数が上限のため, queue-pushqueue-tail が同数しか呼ばれないなら, 均すことで実質 O(1) と見なすことができます.

とは言え現状の実装では queue-tail を複数回呼び出すなどすることで, 余分な reverse の再計算をしてしまう弱点があります.

書籍のほうにはより高度な方法で reverse のコストを f が空になるタイミングでまとめて支払うのではなく漸進的に処理したり, reverse の余分な再計算をしないようにする, うまい実装方法なども紹介されていました.

SICPに乗っているような破壊的なキューは挿入/削除が O(1) ですが 過去のキューは破壊されてしまうため, アクセスできなくなってしまいます. (破壊的変更は並列アクセスによる不具合原因になりやすい問題も抱えています)

今回のようなデータ構造であれば, 破壊的変更を用いた際の弱点を克服しつつ, 余分なコピーによる高いコストを支払わないで済む効率を得ることができそうです.

破壊的変更を用いたデータ構造を考えることが多かったですが, 破壊的変更を使わないでも効率のよいデータ構造を実装するテクニックが 身に付きそうな書籍で楽しいですね.

Written on April 28, 2017