20分でわかる PURELY FUNCTIONAL DATA STRUCTURES.pptx

20分でわかるPurely FunctionalData Structuresk.inaba (//)Apr. 4, 2010あらすじ遅いイミュータブルデータ構造はImmutable Object だけで作るデータ構造この本の内　容を全速力で布教するお題：キュー (Queue)FIFO (First-In First-Out)pushBack(e) でデータeを入れるpopFront() で取り出せる入れた順に出てくる以上代入Immutable Object でない打倒すべき目標破壊的キュー手続き型でよくあるinterface QueueE{ void pushBack(E e); EpopFront();}よくある実装class HakaiQueueE implements QueueE { class Cell { E e; Cell next; } Cell fst, last; void pushBack(E e) {last=last.next=new Cell(e,null);} E popFront() {E e=fst.e; fst=fst.next; return e;}}123?4?破壊的キューの特徴Mutable Object を使用リスト末尾を指すポインタをもっておき末尾のセルを pushBack 時に書換Persistent でない操作前の状態をとっておくには全コピーしかないpushBack, popFront の最悪実行時間は O(1)123?4?HakaiQueueE q = 略;HakaiQueueE p = q;q.pushBack(e); //pも変化!計算量Ephemeral (儚い)使い方での計算量(比較対象)破壊的2リスト銀行家実時間儚AO(1)WO(1)永An/aWn/a詳しくはあとでAmortized(償却)計算量Worst-Case(最悪)計算量Persistent (永続的な)使い方での計算量償却計算量！Immutable な実装2リストキュー非破壊的キューinterface ImuQueueE{ ImuQueueE pushBack(E e); PairE, ImuQueueE popFront();}フィールドの書き換えを使わないキューpushBack, popFront は「操作後のキュー」を別のオブジェクトを作って返す非破壊キュー123?4?コピーコピーコピー1234?単純にやると全コピー：計算量 O(n)２リストキューちょっと工夫キューの後ろの方は逆順で持つpushBack がリスト先頭への追加なのでO(1)に！123?54?data Queue a = Q [a] [a] --ここからコードはHaskellですpushBack (Q front rear) e = Q front (e:rear)popFront (Q [] r) = popFront (Q (reverse r) [])popFront (Q (e:f) r) = (e, Q f r)２リストキューの特徴front側とrear側の２つのリストで表現len(front) == 0 になったら rear を reversePersistent である最悪実行時間は、reverseが発生する瞬間 O(n)でも、償却実行時間は O(1)なので、トータルの実行時間的に考えると計算時間は O(1) と思って問題ない！123?54?償却計算量とは？操作列全体でコストを平均化して見たときの計算量pushBack 1? [] [1]pushBack 2? [] [2,1]pushBack 3? [] [3,2,1]popFront ? [1,2,3] [] ? [2,3] []popFront ? [3] []pushBack 4? [3] [4]popFront ? [] [4]popFront ? [4] [] ? [] []reverseは「たまにしか」起きない時間 t かかるreverseが発生する前に、必ずt 回 pushBack している償却計算量とは？現実の計算量pushBack 1popFront(軽) 1popFront (重) t+1分担をごまかした計算量pushBack 2popFront(軽) 1popFront (重) 1時間 t かかるreverseが発生する前に、必ずt 回 pushBack しているpushBack 1? [] [1] 1 2pushBack 2? [] [2,1] 1 2pushBack 3? [] [3,2,1] 1 2popFront ? [1,2,3] [] ? [2,3] [] 3+1 1popFront ? [3] []