Document

Eliminating Amortizations
PurelyFunctionalDataStrctures 輪講第６回
2006/06/23
いなば
ここまでの流れ (1)

Imperative Queue (Ch2)

リスト末尾を指すポインタをもっておきsnoc時に書換
1


2
3 ・
4 ・
Persistent でない
head, tail, snoc の最悪実行時間が O(1)
ここまでの流れ (2)

Functional Queue (Ch5)




Front側とRear側の２つのリストで表現
 |Front| == 0 になったら Rear を reverse
1
2
5
4 ・
3 ・
Persistent である
最悪実行時間は、reverseが発生するとき O(n)
償却実行時間は (persistencyを必要としない使い方なら) O(1)
ここまでの流れ (3)

Functional Queue via Lazy Evaluation (Ch6)




Front側とRear側の２つのリストで表現
 |Front|+1 == |Rear| になったら遅延 reverse
1
2
5
4 ・
3 ・
Persistent である
最悪実行時間は、reverseが発生するとき O(n)
償却実行時間は (persistencyを必要とする使い方でも) O(1)
今日の話

Functional Real-Time Queue (Ch7)
？



Persistent である
最悪実行時間は、O(1)
償却実行時間も当然、 O(1)
Real-Time Queues: 基本的考え

6章の遅延評価を使ったQueueでは


「借金」＝「suspensionをほどく計算のコスト」
“reverse” の suspension に仮想的な「借金」を割当


借金額＝非共有コスト
＝そのsuspensionをforceした時実行される計算時間
＝ reverse時点のRearの長さ
実際にsuspensionがforceされるに至るまでの各演
算に、仮想的に借金を定数額ずつ「返済」させる

reveseは|Front| = |Rear| のとき行われるので、
|Front| 回 tail した後にforceされる。よって、１回のtailで
１ずつ借金を返済
Real-Time Queues: 基本的考え

Real-Time Queue では


「借金」＝「suspensionをほどく計算のコスト」
各 tail 演算で、実際に「借金」を「返済」する

つまり、tailのたびに、reverseのsuspensionを
少しずつ（定数時間ずつ）実行しておく
Real-Time Queues

OCaml で実装してみました


MyRTQ.ml
ポイント


「|Front|+1 == |Rear| になったらreverse」になってるか
全てのsuspensionは定数時間でforce可能か
Amortization除去
6章のQueueとの差

Rearの逆転処理

f @ rev r


rotate f r []


rev は incremental でない（forceすると全体を計算してし
まう）ので、「実際に少しずつ借金を返す」ができない
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)


Physicist’s Method で、 persistencyを必要としない使い方な
ら insert : 償却 O(1) が示せる
Lazy Binomial Heaps (Ch6)


insert, deleteMin, findMin, merge : 最悪 O(log n)
リストを遅延リストに変えれば、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
insTree t
| []
| hd::tl
h = insTree (T(0,e,[])) h
h = match h with
-> [t]
-> 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
insTree t
| []
| hd::tl
h = insTree (T(0,e,[])) h
h = match h with
-> [t]
-> 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
[, ]
[ ,, , ]
0
0
１: 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 のみで考える（他の演算はあとで）
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1

作られるsuspension


左図の黄色の部分
満たすべき条件

「ある bit が0に評価さ
れる時点までには、そ
の右上のマスの bit は
評価済み」
２: Scheduling

insert のみで考える（他の演算はあとで）
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
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)))
２: Scheduling

Q: なぜ２回execするのか

A: ６章での解析によれば、
Amortized Costは２だったので。
２: Scheduling (Thm7.1)
Schedule

１回のinsertにつき２回execすれば
常に次が満たされる
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
…
0
0


…

0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
Schedule内で未評価
rangeに重なりはない
隣り合う未評価range
の間には必ず評価済
のZeroが１個はある
最左の未評価rangeの
左には必ず評価済の
Zeroが２個はある
現在のHeap
２: Scheduling (Thm7.1) 証明

帰納法による


初期状態 (empty) は条件を満たす → 自明
条件を満たす状態で insert を１回実行しても条件を
満たす


insert すると最左のZeroがOneに変わる
場合分け（４通り）
[1] が入る
ケースB
証明：場合分け４通り
[1] が入る
ケースA
0
0
1
0
0
insert
1
1
insert
1
0
1
0
0
0
1
0
0
1
1
0
1
1
0
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
1
exec × 2
0
1
0
insert
1
exec × 2
0
1
[0,1] が入
る
ケース
0
insert
1
exec × 2
1
exec × 2
1
1
0
0
1
0
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 を実行

Download Report