pfds8.md

8 Lazy Rebuilding

• 1章: 導入
• 2〜3章: 関数型データ構造の基本的な部分についての紹介
• 4〜7章: 遅延評価と償却の関係 ← ここまでやった
• 8〜11章: 関数型データ構造を設計するための汎用的なテクニック ← 残りはこの部分

この章でやること

• batch rebuilding
  • 定期的に最高のバランスに作り直す
• global rebuilding
  • batch rebuilding をインクリメンタルに
• lazy rebuilding
  • 遅延評価を駆使してシンプルに永続的な再構築ができる何か

8.1 Batched Rebuilding

平衡二分探索木と perfect balance

• 多くのデータ構造は効率的なアクセスを実現するためにバランス不変式を保つようになっている
  • 例えば平衡二分探索木
    • バランスすることで最悪計算量 O(n) の操作を O(log n) に改善している
• バランス不変式を維持する方法としては、例えば更新ごとに rebalance を行う、というものが考えられる
• このようなデータ構造には、 perfect balance とでもいうべきものが存在する
  • その後の操作にかかるコストを最小化するような状態
• しかし、常に perfect balance を維持しようとすると、rebalance にかかるコストが大きくなりがちである
  • そのため、多くの場合 近似的に perfect balance を維持するような実装がなされる
    • perfect balance より高々定数倍、後ろに続く操作コストが高まってしまうような実装
    • 例: AVL木や赤黒木

平衡二分探索木と batched rebuiding

• しかし、もし更新操作がバランスを大きく崩すことがなければ、以下のような代替案、 batched rebuilding が採用されうる
  1. rebalance をある程度まとまった数の更新が行われるまで延期させる
  2. その後、データ構造全体に対して rebalance を行い、perfect balance を実現する
• batched rebuilding は以下の2つの条件を満たすケースでよい償却計算量を提供する
  • (条件1) データ構造があまりに多く再構築されることはない
    • 言い換えると、ある程度溜め込んでからでないと再構築してはいけない
    • 個々の操作が O(f(n)) 償却時間に収まってほしいとする
    • 再構築に O(g(n)) かかるとする
    • この場合、再構築は最低でも c・g(n)/f(n) 回の更新ごとにしか行うことができない(cは定数)
    • 二分探索木の例
      • 個々の操作は O(log n) 償却時間で行われたい
      • perfect balance な状態に再構築するのに O(n) かかる
      • 少なくとも c・n/log n 回の更新を行ってからでないと再構築を行えない(cは定数)
        • 例えば毎回 rebalance してたら計算量が O(n) に悪化する
  • (条件2) 個々の更新が後に続く操作のパフォーマンスを極端に悪化させることはない
    • 適切な頻度で更新が行われ、再構築直後の操作は O(f(n)) で実行できるとする
    • その後の各操作が O(f(n)) から悪化しないようなケースは 条件2 を満たしている
      • 定数倍の劣化は OK
    • この条件を満たす更新操作を weak updates と呼ぶ
• 二分探索木の削除操作の例
  • 対象ノードを物理削除する代わりに、論理削除する(削除された、というフラグを立てる)
  • 削除操作は O(log n) で行いたいとする
  • 半数のノードが論理削除されたら
    • 論理削除されているノードを物理削除し、木を perfect balance な状態に再構築する
  • 条件1 のチェック
    • 論理削除されているノードの物理削除と、 perfect balance への再構築に合計 O(n) かかる
    • この操作は論理削除 n/2 回ごとに行われるので、条件1 を満たす
      • O(n/2) > O(c・n/log n)
  • 条件2 のチェック
    • 削除操作は対象ノードを探索し削除フラグを立てるというもので、 O(log 木に存在するノード数)
      • 論理削除ノードは最大 n/2 個なので、物理削除されている場合と比べても1回程度探索パスが深くなるだけ
      • したがって常に O(log n) となり、条件2 も満たす
• ちなみに残念ながら、挿入操作は木の深さを更新しまくるので weak update ではない
• しかし、ハイブリッド戦法を用いることで batched rebuiding を行いつつ挿入と削除をサポートすることが可能
  • 挿入時は普通の平衡二分探索木のように毎回 rebalance、削除時は batched rebuilding

Exercise 8.1

Section 3.3 で実装した赤黒木にこのアイデアを適用せよ。
木の再構築部分は、 Exercise 3.9 を参考にするとよい。

import scala.Ordering.Implicits._
import scala.annotation.tailrec
import scala.collection.mutable.ArrayBuffer

sealed abstract class Color
case object Red extends Color
case object Black extends Color

case class RedBlackTree[A: Ordering](validSize: Int, invalidSize: Int, node: Node[A])

sealed abstract class Node[A: Ordering]
case class Leaf[A: Ordering]() extends Node[A]
case class Branch[A: Ordering](color: Color,
                               isDeleted: Boolean,
                               left: Node[A],
                               value: A,
                               right: Node[A]) extends Node[A]

object RedBlackTree {
  def empty[A: Ordering]: RedBlackTree[A] = RedBlackTree(0, 0, Leaf())

  val Deleted = true
  val NonDeleted = false

  // 指定した要素がどのような状態か調べる便利関数
  // O(log (valid size + invalid size))
  val Found = 0
  val NotFound = 1
  val LogicalDeleted = 2
  @tailrec
  private def check[A: Ordering](x: A, node: Node[A]): Int = node match {
    case Leaf() => NotFound
    case Branch(c, Deleted, l, v, r) if x == v => LogicalDeleted
    case Branch(c, NonDeleted, l, v, r) if x == v => Found
    case Branch(c, d, l, v, r) if x < v => check(x, l)
    case Branch(c, d, l, v, r) if x > v => check(x, r)
  }

  // 論理削除時に false を返すようにする修正
  // O(log (valid size + invalid size))
  def member[A: Ordering](x: A, tree: RedBlackTree[A]): Boolean = {
    check(x, tree.node) match {
      case Found => true
      case NotFound | LogicalDeleted => false
    }
  }

  // 対象要素を持つ要素が木の中に存在するが、論理削除されてしまっている、
  // というケースで論理削除を取り消すことで挿入を表現するよう修正
  // O(log (valid size + invalid size))
  def insert[A: Ordering](x: A, tree: RedBlackTree[A]): RedBlackTree[A] = {
    // ハイブリッド戦法なので、挿入時は木を回転させてゆく
    def insert0(node: Node[A]): Branch[A] = node match {
      case Leaf() => Branch(Red, NonDeleted, Leaf(), x, Leaf())
      // 対象要素が論理削除されていたらフラグを折らねばならない
      case Branch(c, d, l, v, r) if x == v => Branch(c, NonDeleted, l, v, r)
      case Branch(c, d, l, v, r) if x < v => balance(c, d, insert0(l), v, r)
      case Branch(c, d, l, v, r) if x > v => balance(c, d, l, v, insert0(r))
    }

    check(x, tree.node) match {
      case Found => tree
      case NotFound =>
        val node = insert0(tree.node).copy(color = Black)
        // 対象要素が木にない場合は純粋に有効ノードが増える
        RedBlackTree(tree.validSize + 1, tree.invalidSize, node)
      case LogicalDeleted =>
        val node = insert0(tree.node).copy(color = Black)
        // 論理削除の場合は無効ノードを有効ノードに置き換える
        RedBlackTree(tree.validSize + 1, tree.invalidSize - 1, node)
    }
  }

  // ここは間違ってるかもしれませんが詳細は気にしないでください
  // とにかくバランスを取ります
  private def balance[A: Ordering](color: Color,
                                   isDeleted: Boolean,
                                   left: Node[A],
                                   value: A,
                                   right: Node[A]): Branch[A] = {
    (color, isDeleted, left, value, right) match {
      case (Black, zd, Branch(Red, yd, Branch(Red, xd, a, x, b), y, c), z, d) =>
        Branch(Red, yd, Branch(Black, xd, a, x, b), y, Branch(Black, zd, c, z, d))
      case (Black, zd, Branch(Red, xd, a, x, Branch(Red, yd, b, y, c)), z, d) =>
        Branch(Red, yd, Branch(Black, xd, a, x, b), y, Branch(Black, zd, c, z, d))
      case (Black, xd, a, x, Branch(Red, zd, Branch(Red, yd, b, y, c), z, d)) =>
        Branch(Red, yd, Branch(Black, xd, a, x, b), y, Branch(Black, zd, c, z, d))
      case (Black, xd, a, x, Branch(Red, yd, b, y, Branch(Red, zd, c, z, d))) =>
        Branch(Red, yd, Branch(Black, xd, a, x, b), y, Branch(Black, zd, c, z, d))
      case (c, d, l, v, r) => Branch(c, d, l, v, r)
    }
  }


  // 対象ノードを削除する
  // 基本論理削除だが、invalid size が valid size を超えたタイミングで再構築する
  // 再構築が発生しない場合の最悪計算量は O(log (valid size + invalid size))
  // 再構築が発生する場合の最悪計算量は O(valid size + invalid size)
  // 再構築は無効ノードが木全体の半分を占めたタイミングで発生するので、O(log n) amortized time
  def delete[A: Ordering](x: A, tree: RedBlackTree[A]): RedBlackTree[A] = {
    // 削除対象が存在しなければ例外
    def delete0(x: A, node: Node[A]): Node[A] = node match {
      case Leaf() => sys.error("error")
      // 対象ノードを論理削除する
      case Branch(c, NonDeleted, l, v, r) if x == v => Branch(c, Deleted, l, v, r)
      case Branch(c, Deleted, l, v, r) if x == v => sys.error("error")
      case Branch(c, d, l, v, r) if x < v => Branch(c, d, delete0(x, l), v, r)
      case Branch(c, d, l, v, r) if x > v => Branch(c, d, l, v, delete0(x, r))
    }

    check(x, tree.node) match {
      case NotFound | LogicalDeleted => tree
      case Found =>
        val node = delete0(x, tree.node)
        val (validSize, invalidSize) = (tree.validSize - 1, tree.invalidSize + 1)
        if (invalidSize >= validSize) {
          rebuild(node)
        } else {
          RedBlackTree[A](validSize, invalidSize, node)
        }
    }
  }

  // 最高のバランスを持った木を作り直す
  // O(n)
  private def rebuild[A: Ordering](node: Node[A]): RedBlackTree[A] = {
    // 各ノード1回ずつ探索するので O(n)
    // 右から畳み込んでいくので結果はソート済みリストとなる
    def toList(n: Node[A], acc: List[A]): List[A] = n match {
      case Leaf() => acc
      case Branch(c, NonDeleted, l, v, r) => toList(l, v :: toList(r, acc))
      // 論理削除されている要素は捨てる
      case Branch(c, Deleted, l, v, r) => toList(l, toList(r, acc))
    }

    val xs = toList(node, Nil)
    fromOrdList(xs)
  }

  // xs はソート済みのものでないとダメ
  // O(n) で赤黒木を構築する
  // 多分バグってますが、O(n) でソート済みリストから
  // バランスした赤黒木が生成されるものと思ってください
  def fromOrdList[A: Ordering](sortedList: List[A]): RedBlackTree[A] = {
    val size = sortedList.size // O(n)
    val maxDepth = (math.log(size) / math.log(2)).toInt
    // ランダムアクセス用
    // 反則っぽいけど参照だけだしいいよね
    val array = sortedList.to[ArrayBuffer]

    // 基本全部黒で埋めるが、それだけだと完全にバランスしない場合に
    // すべてのパス上にある黒ノードの数が同じ、という制約を満たせないので
    // 一番深いBranchだけ赤にする
    def color(depth: Int): Color = if (depth == maxDepth) Red else Black

    // ノード作成
    // 細かい部分間違ってるかもしれません
    // ネットに載ってるのはもっと難しかったのでそもそも根本的に間違ってるかもしれません
    // 簡単のために要素数 n = 2^k - 1 とする
    // その場合木全体の深さは k となるので、k回再帰する
    // ルートの階層を0とする
    // 階層iには 2^i 個の部分木がある
    // したがって計算回数は
    // ∑[i=0..k]2^i
    // k = log(n + 1) なので
    // O(n)
    def fromOrdList0(depth: Int, start: Int, size: Int): Node[A] = {
      size match {
        case 0 => Leaf()
        case s =>
          val half = s / 2
          val value = array(start + half)
          val left = fromOrdList0(depth + 1, start, half)
          val right = fromOrdList0(depth + 1, start + half + 1, (s - 1) / 2)
          Branch(color(depth), NonDeleted, left, value, right)
      }
    }

    val node = fromOrdList0(0, 0, size) // O(n)
    RedBlackTree(size, 0, node)
  }
}

batched rebuilding キュー

• Section 5.2 で作成したキュー(paired-listによるもの)も batched rebuilding とみなすことができる
  • front list が空になったタイミングで一気に rear list を reverse して front list にする
  • すべての要素が front list に格納されるので、この操作を行ったキューは perfect balance
• このキューはよい償却性能を持つが、永続的に使用すると batched rebuilding のコストに引っ張られて性能が劣化する
• batched rebuilding を使用したすべてのデータ構造に対して同じことがいえる
  • 以降のセクションでは batched rebuilding の概念を永続版に適用する方法を示す

fun checkf ([], r) = (rev r, [])
  | checkf q = q

8.2 Global Rebuilding

• global rebuilding
  • batched rebuilding から償却を除去するテクニック
  • 再構築をインクリメンタルに行う
    • 再構築処理をコルーチンとして実行しているようなもの
  • 再構築結果が必要となったときにすぐ使えるよう、コルーチンは十分早く開始されなければならない
• global rebuilding はオブジェクトに対する２つのコピーを維持することで実現する
  • プライマリコピー(working コピー)
    • 普通な構造を持ったオブジェクト
    • すべての更新がそのまま適用されてゆく
  • セカンダリコピー
    • 徐々に再構築が行われる
    • セカンダリコピーの再構築が完了すると、それは working コピーに取って代わる
      • その場合新たなセカンダリコピー上の再構築はすぐ開始されるかもしれないし、しばらくは working コピーだけで運用されるかもしれない
• セカンダリコピーが再構築されている間に更新が行われると、やっかいなことになる
  • working コピーは通常通り更新すればよい
  • セカンダリコピーもよしなに更新してやらないと、セカンダリが昇格した場合にその更新内容が失われてしまう
  • しかし、セカンダリコピーは通常効率よく更新を行えるようにはなっていないので、以下のように処理する
    1. セカンダリコピーへの更新を一度バッファに蓄える
    2. 再構築完了後、working コピーへ昇格する前に更新を適用する
• global rebuilding は純粋関数的に実装することができ、また何度も実現されてきた
  • 例: Hood と Melville の real-time queue
• batched rebuilding と違い、 global rebuilding により構築されたデータ構造は永続的に利用可能である
  • expensive な操作がないから
• ただし、global rebuilding は実装が複雑になることが多い
  • コルーチンの実行途中の状態を表現できるようにしたりするのが特に厄介

8.2.1 Example: Hood-Melville Real-Time Queues

• Hood と Melville の real-time queue は Section 7.2 のものと多くの点で似ている
  • front list と rear list を持つ
  • rear list が front list より長くなった時点で、インクリメンタルにローテートを行う
• ローテーションの詳細に差異がある
  • rear list をリバースして front list に追加する処理
  • 以下ローテーションを Hood-Melville 風にインクリメンタルにするテクニックの紹介

インクリメンタル・リバース

• インクリメンタルなリストの reverse は、空のリストを用意し、元のリストの要素を徐々に移していくことで実現できる
  • 畳み込み演算を1回ずつ進めていく感じ
• exec は n + 1 回呼び出される

datatype α ReverseState = WORKING of α list * α list | DONE of α list

fun startReverse xs = WORKING (xs, [])

fun exec (WORKING (x :: xs, xs')) = WORKING (xs, x :: xs')
  | exec (WORKING ([], xs') = DONE xs' 

インクリメンタル・アペンド

• xs と ys を連結する操作を考える
  1. xs をインクリメンタルに reverse し xs' を作成
  2. xs' をインクリメンタルに ys に連結
• exec は 2m + 2 回呼び出される(m は xs の長さ)
  • インクリメンタルリバースに m + 1 回
  • インクリメンタル連結に m + 1 回

datatype α AppendState =
      REVERSING of α list * α list * α list (* xs * ys * xs' *)
    | APPENDING of α list * α list (* xs' * ys *)
    | DONE of α list

fun startAppend (xs, ys) = REVERSING (xs, [], ys)

fun exec (REVERSING (x :: xs, xs', ys)) = REVERSING (xs, x :: xs', ys)
  | exec (REVERSING ([], xs', ys)) = APPENDING (xs', ys)
  | exec (APPENDING (x :: xs', ys)) = APPENDING (xs', x :: ys)
  | exec (APPENDING ([], ys)) = DONE ys

インクリメンタル・ローテーション

• キューのローテーション(|front| + 1 = |rear|)
  • front + reverse(rear) な状態にする
• f(front list) と reverse された r(rear list) を連結する操作を考える
  1. f と r をそれぞれ並列に reverse し、f' と r' を生成する
  2. f' を r' に連結してゆく
• exec は 2m + 2 回呼び出される(m は front list の長さ)
  • インクリメンタルリバースに m + 1 回
  • インクリメンタル連結に m + 1 回

datatype α RotationState =
      REVERSING of α list * α list * α list * α list (* f * f' * r * r' *)
    | APPENDING of α list * α list (* f' * r' *)
    | DONE of α list

fun startRotation (f, r) = REVERSING (f, [], r, [])

fun exec (REVERSING (x :: f, f', y :: r, r')) = REVERSING (f, x :: f', r, y :: r')
  | exec (REVERSING ([], f', [y], r')) = APPENDING (f', y :: r') (* |f| + 1 = |r| なので REVERSING はこのパターンで終わる *)
  | exec (APPENDING (x :: f', r')) = APPENDING (f', x :: r')
  | exec (APPENDING ([], r')) = DONE r'

インクリメンタル・ローテーション完全体

• snoc や tail の度に上記のローテーションを呼び出してゆくとすると、おかしなことになる
  • 特に tail が k 回呼び出されていたとすると、「DONE r'」のうち初めの k 個はすでに不用なものとなっている
• ２つの解決方法
  • 案1: 不用な要素の個数を持ち、 RotationState に DELETING フェイズを挟む
    • DELETING フェイズでは不用な要素がなくなるまで削除し続ける
    • global rebuilding の定義に限りなく近い方法(以下手順再掲)
      1. セカンダリコピーへの更新を一度バッファに蓄える
      2. 再構築完了後、working コピーへ昇格する前に更新を適用する
  • 案2: f' の有効な要素数を保持し続け、その数値が 0 となったら r' への追加を終了する
    • tail を呼び出す度に「有効な要素数」をデクリメントしていく
    • わざわざ不用な要素を r' に連結する必要がないので、このケースではよりよい方法
• 後者の方法を用いると、 exec と invalidate の呼び出し回数が合計 2m + 2 回ですむ(m は f の長さ)
  • インクリメンタルリバースに m + 1 回
  • インクリメンタル連結と tail による要素削除合わせて m + 1 回

datatype α RotationState =
      REVERSING of int * α list * α list * α list * α list (*有効な要素数 * f * f' * r * r'*)
    | APPENDING of int * α list * α list (* 有効な要素数 * f' * r' *)
    | DONE of α list

fun startRotation (f, r) = REVERSING (0, f, [], r, [])

(* インクリメンタル・ローテーションを行う操作 *)
fun exec (REVERSING (ok, x :: f, f', y :: r, r')) = REVERSING (ok + 1, f, x :: f', r, y :: r')
  | exec (REVERSING (ok, [], f', [y], r')) = APPENDING (ok, f', y :: r') (* |f| + 1 = |r| なので REVERSING はこのパターンで終わる *)
  | exec (APPENDING (0, f', r')) = DONE r' (* 有効な要素数が 0 となったら終了 *)
  | exec (APPENDING (ok, x :: f', r')) = APPENDING (ok - 1, f', x :: r')

(* 有効な要素数を減少させる操作 *)
fun invalidate (REVERSING (ok, f, f', r, r')) = REVERSING (ok - 1, f, f', r, r')
  | invalidate (APPENDING (0, f', r')) = DONE r' (* 有効な要素数が 0 となったら終了 *)
  | invalidate (APPENDING (ok, f', r')) = APPENDING (ok - 1, f', r')

その他

• あと3点トリッキーな細かい部分がある

1. ローテーション中、キュー内にある最初の数個の要素がすぐアクセスできる場所にない

• 基本 f' の末尾にいる
• head クエリに対応するために、古い front list の working copy を保持する必要がある
  • そして新たな front list のコピーはその working copy がなくなる前に用意しなければならない
• lenf フィールドは、working copy の長さではなく構築中のリストの長さを示すようにする
  • ローテーションとローテーションの間は working copy の front list の長さとなる
    • 後に示す IDLE 状態のとき

type α Queue = int * α list * α RotationState * int * α list (* lenf * f * state * lenr * r *)

2. snoc と tail 時に何回 exec を呼び出すべきか

• 次のローテーションが始まるか、working コピーが使い尽くされる前にローテーションを完了させなければならない
• ローテーション開始時に |f| = m, |r| = m + 1 を満たすとすると
  • 次のローテーションが始まるのは 2m + 2 回 挿入か削除が行われた場合
    • |f| < |r| となるので
  • working コピーがなくなるのは m 回削除が行われた場合
• ローテーションの完了には最大 2m + 2 回のステップが必要
• したがって、ローテーション開始時及びその後のすべての操作ごとに、2回 exec を呼び出せばよい
  • m 回の操作が行われたらそのローテーションが完了するのでそれで十分

3. 次のローテーションが始まる前にローテーションが終了したらどうするか

• IDLE 状態を RotationState に追加する
  • exec を呼び出しても何もしない状態
  • IDLE 状態であるかどうかを気にせず各操作を実装できるので実装がシンプルになる

datatype α RotationState =
      IDLE
    | REVERSING of int * α list * α list * α list * α list
    | APPENDING of int * α list * α list
    | DONE of α list

Exercise 8.2

ローテーション開始時に2回、挿入または削除ごとに1回 exec を呼び出すことでもローテーションが時間内に完了することを証明せよ。またコードを適切に修正せよ。

• おさらい
  • ローテーション開始時に |f| = m, |r| = m + 1 を満たすとすると、次にローテーションすべきは
    • 条件1: 次のローテーションが始まる、 2m + 2 回 挿入か削除が行われたタイミング
    • 条件2: working コピーがなくなる m 回削除が行われたタイミング
  • ローテーションの完了には最大 2m + 2 回のステップが必要
    • 正確には、exec と invalidate の呼び出しが合計 2m + 2 回必要
• 例題で指定されたように exec を呼び出すと
  • 2m + 2 回 挿入か削除が行われたならば、合計 2m + 4 回 exec が呼び出される
    • したがって、条件1 タイミングで 2m + 2 回以上 exec が呼び出されていることが保証できる
  • m 回削除が行われたならば、合計 m + 2 回 exec が呼び出されてる
    • それに加え、invalidate が m 回呼び出される
    • したがって、条件2 タイミングで合計 2m + 2 回以上 exec と invalidate が呼び出されていることが保証できる
• コードは省略

Exercise 8.3

lenf と lenr を f と r の長さの差分を保持する一つのフィールドに置き換えよ。この差分は再構築中誤った値となるかもしれないが、再構築が終わったタイミングでは必ず正しい値となる。

• 省略