オンラインアルゴリズム  H.27 情報数学特論これまでのアルゴリズム(offline algorithm) 一括して入力があらかじめ提示され、計算に必要な情報はすべて入力に含まれている時間さえ掛ければ、最善の解を計算できる将棋の最善手など   第7回：オンラインアルゴリズム ―現在における最適な選択―   坂本比呂志九州工業大学大学院情報工学研究院オンラインアルゴリズム(online algorithm) 時刻が進むにつれて入力が徐々に与えられる各時刻におけるそれまでの入力のみから、その時点における行動を決定するアルゴリズム   2 例題  競合比(最適なコストとの比率) スキーレンタル問題      スキーに行くときに、用具をレンタルするか、購入するかを決める問題レンタルは一回1万円で、購入すると10万円一度購入すればシーズン中は何度でも使えるシーズン中に合計何回スキーに行くかはあらかじめわからないスキーレンタル問題に対する戦略の例 (1) (2) (3)  計 n 回スキーに行くときの競合比は以下のようになる (1) (2) (3)  3 九州工業大学情報工学部坂本比呂志常にレンタルする最初の1回で用具を購入する 9回目までレンタルで、10回目で購入 n/10 10以下 1.9以下これらの戦略で(最悪時の評価で)最も優れているのは(3)である 4 1 実用的なオンラインアルゴリズムの設計と解析競合比の定義    CA(x):入力xに対するオンラインアルゴリズム A のコスト Copt(x):最適オフラインアルゴリズムのコスト以下を満足する定数 r が存在するとき、Aの競合比はr であるという  問題      長さ n の線形リストある順番でリスト中のアイテムにアクセス(5,7,2,3,...など) 先頭から i 番目のアイテムにアクセスするコストは i 検索されたアイテムはリストの前方の任意の場所にコストゼロで移動できる (MTF: move to front) アイテム1 証明のつづき証明：以下の図は、tステップ目において、最適オフラインアルゴリズム(OPT)とオンラインアルゴリズム(MTF)が、アイテムiにアクセスする直前の状況  yt i 番目にアクセスしたアイテムを常に先頭に移動する最適アルゴリズム(OPT)  i 番目にアクセスしたアイテムを常に最適な前方位置に移動するアイテム3 アイテム4 6 ポテンシャル関数INV(t)を導入する  INV(t) = tステップ目のアクセスの直前において、OPTとMFT で出現順が逆になっているアイテムの組み(L,R)の数：すなわち、図でアイテム i の前後で色が異なるアイテムの組の総数 i OPT xt MTF  アイテム2 定理: MTFの競合比は2以下 pt－xt  長さiのリストを辿るコストはi 5 OPT オンラインアルゴリズム(MTF) pt－xt yt i i xt MTF pt i pt pt: MTFにおいて、アイテムiの前にあるアイテムの総数 xt : MTFではiの前にあるが、OPTではiの後ろにあるアイテムの総数 yt: MTFではiの後ろにあるが、OPTではiの前にあるアイテムの総数  7 九州工業大学情報工学部坂本比呂志以下のようなコスト関数を考える (アイテムiを先頭に移動するコスト＋移動によって増えた逆順の組みの個数) 8 2 証明のつづき証明のつづき  INV(t) = xt + yt とみなしてよい。なぜなら以下の計算で、 (i,k)と(k,i)のようにiの前後で順序が入れ替わる場合以外は、引き算で相殺されるから。  INV(t+1) ≤ OPTでiより前方のアイテム数= pt－ xt + yt 以上により、   以上により、  したがって、  よって、平均して pt ≤ 2qt (競合比が2)が示された補足：この競合比はそれ以上改善できない qt pt－xt OPT yt i xt MTF i 9  10 pt もう一つの問題  様々なページングアルゴリズムページング（あるいはキャッシング）        計算機は高速記憶装置(メモリやキャッシュ)と低速記憶装置 (ハードディスクやUSBメモリなど)がある低速記憶装置の容量は大きい(N個のデータを記憶できる) 高速記憶装置はk個(k<N)のデータしか記憶できないプログラム実行時に読み込むデータの列をページ要求といい、あるデータが高速記憶装置に存在せず、低速記憶装置からデータをロードしなければならない状況をページフォルトという例えば、メモリに0,2,3とデータがあり、ディスクに1,4,5があったとき、ページ要求0,1,3の2番目でページフォルトが起こるこのようなページフォルトの回数を最小にしたい 11 九州工業大学情報工学部坂本比呂志    FIFO (First-In-First-Out)：最も古くロードされたデータを削除する LRU(Least-Recently-Used)：直近のページ要求が最も古いデータを削除 FFU(Furthest-Future-Used)：将来のページ要求が最も遅くくるデータを削除（このアルゴリズムはあきらかに最適な振る舞いをするが、設計が不可能）そのほかにたくさん 12 3 ページング問題の競合比 FIFOとLRUの違い  FIFOはリストにデータを追加して行くことで実装できる    1,2,3,4,5,4,3,2,1のようなページ要求を処理すると、メモリには 1,2,3,4,5がロードされていて、これ以上新しいデータを記録できないとする。このとき、あらたにデータ6のページ要求に対して削除されるデータは、最初にロードされたデータ1である  LRUはメモリに存在する各データに対して、それらが直近でいつ参照されたかの履歴を持てば実装できる  上の同様のページ要求に対して、データ6のページ要求に対して削除されるのは、一番最後にページ要求があったデータ5 どのような(FFU以外の)アルゴリズムも競合比はk以上となる証明：データ全体がk+1個とする。どのようなアルゴリズムも最大でk個しかデータを記憶できないので、ある時点で記憶していないデータをページ要求することで、常にページフォルトが発生するように入力を作ることが可能である。一方、FFUは、将来のページ要求を知っているので、今記憶しているk個のデータのうち、最後にページ要求されるものを削除することで、k回につき高々1回しかページフォルトをおこさないようにできる。よって、これらの競合比はk以上である。 13 FIFOとLRUではどちらが有利か？  FIFOのページフォルトアノマリの問題：FIFOでは記憶領域が大きいほどページフォルトが多くなる例が存在する   14  2回目の繰り返しでは以下のようにページフォルトは9回  ところが、k=4にして同じページ要求を行うと以下のようにページフォルトが10回に増えてしまう。  このような現象はLRUでは起こらないことが証明されている k=3とし、ページ要求0,1,2,3,0,1,4,0,1,2,3,4を繰り返す場合 2回目の繰り返しの直前のメモリは古いほうから(4,2,3) ページ要求 0 1 2 3 0 1 4 0 1 2 3 4 最新のページ 0 1 2 3 0 1 4 4 4 2 3 3 0 1 2 3 0 1 1 1 4 2 2 0 1 2 3 0 0 0 1 4 4 F F F F F F F : 最古のページページフォルト F F 15 九州工業大学情報工学部坂本比呂志 16 4 演習問題7-1  演習問題7-1（ヒント付き） [問題] スキーレンタル問題の競合比1.9はそれ以上改善できないこと、すなわち競合比が1.9未満のオンラインアルゴリズムは存在しないことを示せ  [問題] スキーレンタル問題の競合比1.9はそれ以上改善できないこと、すなわち競合比が1.9未満のオンラインアルゴリズムは存在しないことを示せ     この競合比は、レンタル料などに関係なく一定ヒント：購入代金を x とし、1回のレンタル料を y とする。 k 回目のスキーの直前に購入すると払う金額は、(k-1)y+x この戦略で失敗するのは、    17 九州工業大学情報工学部坂本比呂志 (1) 最初に購入するのが最適だった場合 (2) k回目以降スキーに行かない場合(k回全部レンタルで済ませる場合)のいずれか (1)と(2)の場合の競合比を式で表したとき、その二つの競合比が均衡する場合がもっとも損失が少なくなる場合である。 18 5