読者です 読者をやめる 読者になる 読者になる

わどぅー

記事については、中間出力の場合も多いので間違ってたらごめんなさい。twitter は waddlaw です。どうぞよろしく。

amortized complexity

関数プログラミングの楽しみ第一章の中に「均し解析」という言葉が出現してたんですが、聞いたこと無いキーワードだったので勉強することにします。

キーワードとしてはこんな感じかな

  • 均し計算量
  • ならし計算量
  • 償却計算量
  • ならし解析
  • amortized complexity

計算量のお話みたいなんですけど、苦手な領域なのでまずは知識を詰め込んでいこう・・・。

アルゴリズム アルゴリズム設計設計 (1) 導入、計算量概念

http://www.logos.t.u-tokyo.ac.jp/www/home/chik/algorithm-design/01%20Introduction.pdf
■ 計算量の指標

  • 時間計算量 (time complexity)
    • 基本操作の回数
  • 空間計算量 (space/memory complexity)
    • 使用するメモリの総量
  • 漸近的計算量 (asymptotic complexity)
    • 例) 「計算量は n が大きいときに n log n 程度」
  • O 記法 (big-O notation)
    • 漸近的計算量の上界を示す記法
      • 上界: 「これより大きくなることはない」
    • あるアルゴリズムがO(f(n))であるとは
      • \exist{c} \exist{n_{0}} \forall{n} \ge n_{0} T(n) \le c f(n)
      • T(n) は問題サイズ n に対する計算量
      • 論理式のわかりやすい解説は「数学ガール 乱択アルゴリズム P.194〜」を見ると良いかも。つまり、最低ライン n0 を決めて、それよりも大きな任意の n に対して f(n) 以下であれば良いのだ。n0 よりも小さい値に関しては f(n) よりも大きくなっても構わない。
  • Ω記法 (Ω-notation)
    • 漸近的計算量の下界を示す記法
      • 下界: 「これより小さくなることはない」
  • Θ(シータ) 記法 (Θ-notation)
    • 上界と下界が一致する場合の記法
      • あるアルゴリズムが Θ(f(n)) であるとは O (f(n)) かつ Ω (f(n))

■ 単純でない場合の計算量指標

  • 最悪の場合の計算量 (worst case complexity)
  • 平均計算量 (average case complexity)
  • 償却計算量 (amortized complexity)

■ 計算量クラス

動的配列への追加コストはなぜ O(1)?

http://chasen.org/~taku/blog/archives/2007/02/_o1.html
非常にわかりやすかった。

しかし、Haskell の場合では一般的なならし解析と少し違うらしい。
本物のプログラマはHaskellを使う - 第32回 効率的なキューを表現するSeq型:ITpro
上記のコラムによると、Amazon.co.jp: Purely Functional Data Structures: Chris Okasaki: 洋書の5章と6章を読めばわかるらしい。
論文だとこれの3章http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

20分でわかる Purely Functional Data Structures

http://www.kmonos.net/pub/Presen/PFDS.pdf

■ リストキュー

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)

すげえええええええ、たしかにこの構造でキューを定義すればリストへの追加は先頭になるから O (1) で済んじゃうね!

■ リストキューの特徴

  • Persistent である
    • Prsistent・・・永続的な、永続性の
  • 最悪実行時間は、reverse が発生する瞬間 O (n)
    • これは蓄積変数を利用した reverse のこと。(++) を利用した実装だと O(n^2) になるので注意。この辺の話は「プログラミング Haskell」のP.174ら辺に書いてあります。
  • 償却実行時間は O (1) (本当に???)

■ reverse が起きる寸前のキューを何回も使う
pdf では pushFront ってなってるけど、pushBack の間違いだと思うので修正。

let q = pushBack (pushBack (pushBack (Queue [] []) 1) 2) 3
in … (popFront q) … (popFront q) … (popFront q) … (popFront q) …
  • 現実の計算時間
    • 1*3 + 4*4 (pushBack3つ分とpopFront4つ分、pushBack を3回行ってるので t=3)
  • 分担をごまかした計算時間
    • 2*3 + 4

■ さらなる工夫
pdf は len だけど、length に改変。

  • length(front)+1 == length(rear) になったら遅延評価で reverse
    • 日本語で書くと、front の方が rear より短くなったら遅延評価で reverse する
data Queue a = Q [a] Int [a] Int
pushBack(Q f fl r rl) e  = chk (Q f fl (e:r) (rl+1))
popFront(Q (e:f) fl r rl) = (e, chk (Q f (fl-1) r rl))
chk (Q f fl r rl) =
    if fl+1 == rl 
    then (Q (f++reverse r) (fl+rl) [] 0)
    else (Q f fl r rl)

データ構造が若干変化して Int が2つ増えたけど、単に front と rear のリストの長さを保存してるだけ。
chk 関数は「front の方が rear より短くなったら遅延評価で reverse する」に相当。

■ 工夫したリストキューの特徴 (銀行家キュー)

  • Persistent である
  • 最悪実行時間は、reverseが発生するとき O (n)
  • 償却実行時間は (persistentな使い方でも) O (1) (これで大丈夫なはず!)

■ 計算量の見積もり方

  • 積み立て金メソッド
    • 「時間tかかるreverseの前に必ずt回pushBackしてる」→「pushBackのコストを 2 にして、先にreverseの負担の分を払っておけばOK」
  • 借金メソッド
    • 「早めの遅延評価reverseしておけば、値が本当に必要になるまでに時間がある」→「本当に必要になる支払期限までに、t 回のpopFrontで負担金を用意できれば問題ない」

この次のスライドは説明不足な気もするけど、気にしないでおこう

  • r[1] とか書いてあるのは reverse する予定ってことかな (遅延評価なので予定)
  • popFront (重) x+1 は popFront (重) t+1 の間違いかな
    • おさらいすると、popFront(軽)とpopFront(重)の違いは reverse するかしないかという点。
  • 積立金は一度使うとなくなる
  • 借金は、一度返せば大丈夫!
    • 遅延評価でメモ化されてるから

■ 実時間キュー

  • 償却計算量とはなんだったのか
    • 仮想的に「積立金」や「借金」を考え仮想的に返済する
  • popFront で、仮想的にではなく実際に「借金」を返す
  • 言いかえれば、popFront のたびに、reverse 処理を実際に「ちょっとずつ実行」する

■ やり方
1: 借金ポインターを追加 (遅延評価サンクを指しておく)

data Queue a = Q [a] Int [a] Int [a]
pushBack(Q f fl r rl s) e
    = seq chk (Q f fl (e:r) (rl+1) s)
popFront(Q (e:f) fl r rl s)
    = (e, seq chk (Q f (fl-1) r rl s))

ここで言ってる借金ポインタは Queue データ型の最後の [a] のこと。
ちなみに、サンク (thunk) とは途中で計算が止まっている値のこと。完全に評価されていない値って言えばいいのかな。
詳しくはこちら。http://www.haskell.org/haskellwiki/Thunk

2: chk 関数は reverse チェックのついでに無駄に遅延サンクをちょっとづつ実行 (chk自体は遅延しないようにeager実行)
seq は第一引数を正格評価し、第二引数を返す関数。型は seq :: a -> b -> b。Prelude参照。


pdf では 2.1 → 2.2 の順番で説明されてるけど、逆の方がわかりやすい気がするので逆で説明。
ちなみに、2.2 のコードは若干間違ってる。ff じゃなくて zs が正しい気がする。

2.2: rotate xs ys zs は xs ++ (reverse ys) ++ zs する関数

rotate [] (y:_) zs = y : zs
rotate (x:xs) (y:ys) zs = x : rotate xs ys (y:zs)

ようするに、リスト xs は全部分解し、ys は reverse したいので、zs の先頭にくっつけ、最終的にはリスト zs の先頭に xs の要素1つ1つを実際に cons してるんだね。

具体例だしとこ。

rotate [1,2] [5,4,3] [6,7,8]
= rotate (1:[2]) (5:[4,3]) [6,7,8]
= 1 : rotate [2] [4,3] (5:[6,7,8])
= 1 : (rotate (2:[]) (4:[3]) (5:[6,7,8]))
= 1 : (2 : rotate [] [3] (4:(5:[6,7,8])))
= 1 : (2 : (3 : (4:(5:[6,7,8]))))
=...
= [1,2,3,4,5,6,7,8]

具体例書いて気づいたけど、rotate [1,2,3] [6,5,4] [7,8,9] だとパターンマッチに失敗するね。

rotate [1,2,3] [6,5,4] [7,8,9]
= rotate (1:[2,3]) (6:[5,4]) [7,8,9]
= 1 : rotate [2,3] [5,4] (6:[7,8,9])
= 1 : (rotate (2:[3]) (5:[4]) (6:[7,8,9]))
= 1 : (2 : rotate [3] [4] (5:(6:[7,8,9])))
= 1 : (2 : (rotate (3:[]) (4:[]) (5:(6:[7,8,9]))))
= 1 : (2 : (3 : rotate [] [] (4:(5:(6:[7,8,9])))))
= 1 : (2 : (3 : ( -- ここでパターンマッチに失敗する

コメントにあった「実は fl+1 == rl のときだけこっちに来る」って言うのをもっと考察するべきだった。たしかに、これが本当なら大丈夫だ。

2.1: 借金ポインタに対してパターンマッチ = consセル1個分だけ実行される。

chk (Q f fl r rl (_:s)) = (Q f fl r rl s)
chk (Q f fl r rl []) =
    -- 実は fl+1 == rl のときだけこっちに来る
    let ff = rotate f r []
    in (Q ff (fl+rl) [] 0 ff)

rotate f r [] ということは、ff は実質 f ++ reverse r ということか。


うーん、こんがらがってきた・・・。まとめてみよ。
登場人物は3人
 ダメ人間Aさん
 しっかり者のBさん
 金融屋のCさん

  • お金を借りる人
    • ダメ人間Aさん。これが早めの遅延評価 reverse に相当?
  • 金返せ!っていう人
    • 金融屋のCさん。実際の reverse 処理に相当?
  • お金を返す人
    • しっかり者のBさん。t 回の popFront に相当?

つまり、この3人の関係が上手く行けば問題無いんだろうなぁ。もし、お金が払えなくなったら成り立たないってことで良いのかなぁ。
これ以上わからんんんんんんんんんん。

星の贈り物

¯‚Ì‘¡‚蕨(2006”N10ŒŽ‚Ì“ú‹L)

ちなみに 前に紹介した the fun of programming の第一章がこの本の(一部の)サマリーになっている のですが、読んでいるときは凄いと思うものの、紙面の都合上あれだけで内容を把握するのは困難です。(他の章は全然違う話題をしているので、すぐに内容を忘却してしまいますし……。)また、Catenable Double Ended Queue までは辿りつけません。なので、この辺りの話に興味のある人は素直に Purely Functional Data Structures を読みましょう。

深く理解しようと思ったらこの本を買って読めということか、欲しい本リストに追加しておこう。


関数プログラミングの楽しみで利用されていたならし解析は「20分でわかる Purely Functional Data Structures」を読んでみると、わかった気になれそう。
ちゃんと理解したいから本読むことにしよ