Eliminating Amortizations PurelyFunctionalDataStrctures 輪講 第６回 2006/06/23 いなば

ここまでの流れ (1) Imperative Queue (Ch2) 1 2 3 ・ 4 ・ リスト末尾を指すポインタをもっておきsnoc時に書換 Persistent でない head, tail, snoc の最悪実行時間が O(1) 1 2 3 ・ 4 ・

ここまでの流れ (2) 1 2 3 ・ 5 4 ・ Functional Queue (Ch5) Front側とRear側の２つのリストで表現 |Front| == 0 になったら Rear を reverse Persistent である 最悪実行時間は、reverseが発生するとき O(n) 償却実行時間は (persistencyを必要としない使い方なら) O(1) 1 2 3 ・ 5 4 ・

ここまでの流れ (3) 1 2 3 ・ 5 4 ・ Functional Queue via Lazy Evaluation (Ch6) Front側とRear側の２つのリストで表現 |Front|+1 == |Rear| になったら遅延 reverse Persistent である 最悪実行時間は、reverseが発生するとき O(n) 償却実行時間は (persistencyを必要とする使い方でも) O(1) 1 2 3 ・ 5 4 ・

？ 今日の話 Functional Real-Time Queue (Ch7) Persistent である 最悪実行時間は、O(1)

Real-Time Queues: 基本的考え 「借金」 ＝ 「suspensionをほどく計算のコスト」 “reverse” の suspension に仮想的な「借金」を割当 借金額 ＝非共有コスト ＝ そのsuspensionをforceした時実行される計算時間 ＝ reverse時点のRearの長さ 実際にsuspensionがforceされるに至るまでの各演算に、仮想的に借金を定数額ずつ「返済」させる reveseは|Front| = |Rear| のとき行われるので、 |Front| 回 tail した後にforceされる。よって、１回のtailで １ずつ借金を返済

Real-Time Queues: 基本的考え 「借金」 ＝ 「suspensionをほどく計算のコスト」 各 tail 演算で、実際に「借金」を「返済」する つまり、tailのたびに、reverseのsuspensionを 少しずつ（定数時間ずつ）実行しておく

Real-Time Queues OCaml で実装してみました ポイント MyRTQ.ml 「|Front|+1 == |Rear| になったらreverse」になってるか 全てのsuspensionは定数時間でforce可能か

Amortization除去 6章のQueueとの差 Rearの逆転処理 f @ rev r rev は incremental でない（forceすると全体を計算してしまう）ので、「実際に少しずつ借金を返す」ができない rotate f r [] incremental。少しずつ計算できる。 Schedule, exec 「実際に少しずつ計算」するための「次やる計算」のリストと、それを実際に少し実行する処理

Amortization除去 一般的なステップ (1) Monolithic な suspension を、工夫してincremental なものに置き換える 各 suspension の「内部コスト」を、許される計算量制限の範囲におさえる 例 : @rev → rotate, 内部コスト=O(1) 内部コスト（internal cost） suspension の内部コストとは、「依存している他の全ての suspension が既に評価済みで値をO(1)で取り出せる」と仮定した時にかかる計算コストのこと (「suspendされている計算の非共有コスト」と同義？)

Amortization除去 一般的なステップ (2) 各suspensionが評価されるよりも前に、そのsuspensionが依存する他のsuspensionが評価済みとなることを保証する 例 : schedule変数

Exercise 7.1 6章の @rev を rotate に置き換えると（Schedulingを行わなくても）、snoc, head, tail の最悪実行時間はO(n) から O(log n) に減る。これを示せ Ans Scheduleが関与したのはrotateの第一引数のforce。 このsuspensionの依存の深さは、連続でsnocし続けた時最大になるが、たかだかO(log n)

Exercise 7.2 Real-time Queue の要素数を求めたい。 ただし、|f| + |r| で求めるよりも、|r| と |s| を使う方が効率がよい。求め方と効率について考察せよ Ans. |s| = 前回のrotate時の要素数 – tail回数 – snoc回数 |r| = snoc回数 ∴要素数 =前回のrotate時の要素数 - tail回数 + snoc回数 = |s| + 2 |r| |f|+|r| > |r|+|s| なのでその分だけ速い？ それだけだろうか？　

今日の話その２ Binomial Heaps (Ch3) Binomial Heaps (Ch5) insert, deleteMin, findMin, merge : 最悪 O(log n) Binomial Heaps (Ch5) Physicist’s Method で、 persistencyを必要としない使い方なら insert : 償却 O(1) が示せる Lazy Binomial Heaps (Ch6) リストを遅延リストに変えれば、persistency を使う場合でも insert : 償却 O(1) にできる Amortizationの除去 (Ch7) insert を 最悪 O(1) にできる

Binomial Heaps: おさらい 自然数の「２進数表現」に類似したデータ構造 サイズ 2a1+2a2+...+2an のHeapは、 [サイズ2a1の木、サイズ2a2の木、…、サイズ2anの木] のリストで表現

Binomial Heaps: おさらい type tree = T of int * Elt.t * tree list type heap = tree list insert e h = insTree (T(0,e,[])) h insTree t h = match h with | [] -> [t] | hd::tl -> if rank t < rank hd then t::h else insTree (link t hd) tl

やるべきこと 「少しずつ実行したいsuspension」 がmonolithicなら incremental に書き換える 内部コストが欲しい計算量におさまるように monolithic な insTree を incremental, O(1) に Scheduling insert e h = insTree (T(0,e,[])) h insTree t h = match h with | [] -> [t] | hd::tl -> if rank t < rank hd then t::h else insTree (link t hd) tl

[ ] [ , ] , , , １： Incremental 化 もっと２進数に近い表現を type tree = T of Elt.t * tree list type bit = Zero | One of tree type heap = bit list [ , ] [ ] , , ,

１: Incremental 化 もっと２進数に近い表現を insTree t h = match h with | [] -> [One t] | Zero::tl -> (One t) :: tl | (One hd)::tl -> Zero :: insTree (link t hd) tl

１: Incremental 化 もっと２進数に近い表現を Lazy版 insTree t h = match force h with | SNil -> lazy (SCons(One t, lazy(SNil))) | SCons(Zero, tl) -> lazy (SCons(One t, tl)) | SCons(One hd, tl) -> lazy (SCons(Zero, insTree (link t hd) tl))

２： Scheduling 「insTreeの作るsuspensionは全て、 評価される前にその依存するsuspensionが評価済みになっているようにする」 insTree t h = match force h with | SNil -> lazy (SCons(One t, lazy(SNil))) | SCons(Zero, tl) -> lazy (SCons(One t, tl)) | SCons(One hd, tl) -> lazy (SCons(Zero, insTree (link t hd) tl))

２: Scheduling insert のみで考える（他の演算はあとで） 作られるsuspension 満たすべき条件 左図の黄色の部分 1 作られるsuspension 左図の黄色の部分 満たすべき条件 「ある bit が0に評価される時点までには、その右上のマスの bit は評価済み」 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

２: Scheduling insert のみで考える（他の演算はあとで） type schd = bit stream list 1 type schd = bit stream list type heap = bit stream * schd let exec (bs::bsl) = match force bs with | SCons(Zero, t) -> t::bsl | SCons(One _,_) -> bsl let insert x (bs,sc) = let bs = insTree ... bs in (bs, exec (exec (bs::sc))) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

２: Scheduling Q: なぜ２回execするのか A: ６章での解析によれば、 Amortized Costは２だったので。

２: Scheduling (Thm7.1) … … １回のinsertにつき２回execすれば 常に次が満たされる Schedule １回のinsertにつき２回execすれば 常に次が満たされる Schedule内で未評価rangeに重なりはない 隣り合う未評価rangeの間には必ず評価済のZeroが１個はある 最左の未評価rangeの左には必ず評価済のZeroが２個はある 1 1 1 … 1 1 … 1 1 1 1 1 1 現在のHeap

２: Scheduling (Thm7.1) 証明 帰納法による 初期状態 (empty) は条件を満たす → 自明 条件を満たす状態で insert を１回実行しても条件を満たす insert すると最左のZeroがOneに変わる 場合分け（４通り）

証明：場合分け４通り [1] が入る ケースB [1] が入る ケースA 1 1 insert 1 1 1 1 insert 1 1 1 1 1 insert 1 1 1 1 insert 1 1 1 exec × 2 1 1 1 1 exec × 2 [0,1] が入る ケース 1 1 1 insert 1 1 insert 1 1 1 exec × 2 1 1 exec × 2 1 1 1 [0,...,0,1] が入る ケース

その他の演算 deleteMin, findMin, merge O(log n) で十分なので、全ての未消化 schedule を実行して、普通のリストとして操作すればよい insert での解析から、未消化 schedule はたかだか O(log n) 個である MyBinHeap2.ml

まとめ “Lazy” “Amortized” “Persistent” データ構造を、 “Lazy” “WorstCase” “Persistent” に変える手法 遅延評価する部分を incremental にする 小分けにした suspension を “Schedule” として管理 各演算ごとに、解析された償却計算量に従った回数分 Schedule を実行