オンラインアルゴリズム(online algorithm)とは、要求の列を 1 つずつ受け取り、それより後の要求を知らないまま各要求に取り消せない応答をするアルゴリズムである。良さは、どの要求の列でも費用が、列全体を知るオフラインの最適値の何倍以内に収まるか(競合比)で測る。スキーを借りるか買うかを決めるスキーレンタル問題では、借りた費用が買う値段に追いつく直前に買う規則が最良で、決定的な規則の最良の比は $2-1/B$ である。$k$ 個の頁を置くキャッシュの管理では、最も長く使われていない頁を追い出す LRU が $k$-競合的で、決定的な規則は $k$ より良くならない。
オンラインアルゴリズム(online algorithm)とは、入力が要求の列として 1 つずつ届き、各要求に、それより後の要求を知らないまま応答しなければならないアルゴリズムである。応答は取り消せず、費用が積み重なる。これに対し、要求の列全体を初めから知って最適な応答を選ぶものを オフライン の最適解という。オンラインアルゴリズムの良さは、どの要求の列に対しても、費用がオフラインの最適値の何倍以内に収まるか(競合比)で測る。この見方を 競合解析(competitive analysis)という。
典型例は 2 つある。1 つは スキーレンタル問題 で、スキーを何日続けるか分からないまま、毎日借りるか、高い値段で買うかを決める。もう 1 つは ページング(キャッシュの管理)で、小さく速い記憶に $k$ 個の頁しか置けないとき、要求された頁がなければ何を追い出すかを決める。どちらも、未来を知らない代償がちょうど何倍かを、上界と下界の一致で決められる。
この記事では、オンラインアルゴリズムと競合比を定義し、スキーレンタル問題の最良の決定的な競合比が $2-1/B$ であること、ページングで LRU(最も長く使われていない頁を追い出す)が $k$-競合的であり、どの決定的なアルゴリズムも $k$ より良くならないことを証明する。
要求の集合 $R$ と、要求の列 $\sigma=(\sigma_1,\dots,\sigma_T)\in R^T$ に対する応答の規則と費用が与えられているとする。
$c\ge1$ とする。
定義は FKLMSY91 §1(p. 1)に従った(そこでは $\mathrm{OPT}(\sigma)$ の代わりに任意のアルゴリズム $B$ の費用と比べるが、同じことである)。競合比の下界を示すには、アルゴリズムの動きを見ながら要求の列を作る 敵 を考え、その列で費用の比が大きくなることを示す。決定的なアルゴリズムの動きは要求の列から決まるので、敵は応答を前もって計算できる。乱数を使うアルゴリズムでは、2 の定義のとおり敵は乱数の値を見られない。
$B\ge1$ を整数とする。スキーは 1 日ごとに、借りれば費用 $1$、買えば費用 $B$(以後は費用 $0$)である。滑る日数 $d\ge1$ は前もって分からず、毎朝「今日も滑る」ことだけが分かる。$d$ 日の滑りに対するオフラインの最適値は $\mathrm{OPT}(d)=\min(d,B)$ である。
毎朝届く要求はどれも「今日も滑る」で同じなので、決定的なアルゴリズムは「$t$ 日目の朝に買う」($t\in\{1,2,\dots\}$)か「買わない」($t=\infty$)のどれか 1 つに決まる。$t$ 日目に買う規則 $A_t$ の費用は
$$
C_{A_t}(d)=\begin{cases}d & (d< t),\\ t-1+B & (d\ge t)\end{cases}
$$
である。$t=B$(借りた費用の合計が買う値段に追いつく直前の日に買う)の規則を 損益分岐の規則 という。
1:$d< B$ なら $C_{A_B}(d)=d=\mathrm{OPT}(d)$ である。$d\ge B$ なら $C_{A_B}(d)=2B-1$、$\mathrm{OPT}(d)=B$ で、比は $2-1/B$ である。
2:$A=A_t$ とする。$t=\infty$ なら、$d\ge B$ で $C_A(d)=d$、$\mathrm{OPT}(d)=B$ なので、$d=2B$ をとれば比は $2\ge2-1/B$ である。$t<\infty$ なら $d:=t$(買った日で滑るのをやめる)とすると、$C_A(t)=t-1+B$ である。$t\le B$ なら $\mathrm{OPT}(t)=t$ で
$$
\frac{t-1+B}{t}=1+\frac{B-1}{t}\ge1+\frac{B-1}{B}=2-\frac1B
$$
である。$t>B$ なら $\mathrm{OPT}(t)=B$ で、$\frac{t-1+B}{B}\ge\frac{2B}{B}=2$ である。$\square$
2 は、どの $t$ についても比 $(t-1+B)/\min(t,B)$ が $t=B$ で最小になることを言っている(ex-oa-ski の図)。加法的な定数を許す競合比では、スキーレンタル問題は意味を失う。初日に買う規則は $C=B\le1\cdot\mathrm{OPT}+B$ なので 1-競合的になる(反例の表の 1 行目)。オフラインの最適値が $B$ で抑えられる問題では、厳密な競合比で比べる。
$k\ge1$ と、頁の集合 $P$ をとる。キャッシュ は $P$ の高々 $k$ 個の頁の集合で、初めの内容 $K_0$ はどのアルゴリズムにも共通とする。要求 $\sigma_t\in P$ が届くと、$\sigma_t$ がキャッシュにあれば費用 $0$ で何もしない。なければ 頁の欠損 で費用 $1$ がかかり、$\sigma_t$ をキャッシュに入れる。そのときキャッシュに $k$ 個の頁があれば、1 つを選んで追い出す。費用は欠損の回数である。
キャッシュを変えるのは欠損のときだけとし、オフラインの最適値もこの規則の中で最小をとる。オンラインの規則の例を挙げる。
キャッシュの大きさが $k$ のとき、すべての要求の列 $\sigma$ について
$$
C_{\mathrm{LRU}}(\sigma)\le k\cdot\mathrm{OPT}(\sigma)+k
$$
である。すなわち LRU は $k$-競合的である。
証明のために、要求の列を 相 に分ける。$\sigma_1$ から始め、現れる相異なる頁が $k$ 個以下にとどまる限り同じ相を延ばし、$k+1$ 個目の相異なる頁の要求で次の相を始める。最後の相以外の相には、ちょうど $k$ 個の相異なる頁が現れる。
相の個数を $N$ とする。
段 1(LRU は各相で $k$ 回以下)。1 つの相の中で頁 $p$ が時刻 $s$ に要求されたあと、同じ相の時刻 $s'>s$ の欠損で LRU が $p$ を追い出したとする。追い出すのはキャッシュに $k$ 個の頁があるときで、$p$ はその中で最後の要求が最も古いので、残りの $k-1$ 個の頁はどれも時刻 $s$ より後、$s'$ より前に要求されている。それらは同じ相の要求である。さらに時刻 $s'$ に要求された頁 $q$ はキャッシュになかったので、$p$ とも $k-1$ 個の頁とも異なる。すると、この相に $p$、$k-1$ 個の頁、$q$ の $k+1$ 個の相異なる頁が現れ、相の定め方に反する。よって相の中で一度要求された頁は、その相の終わりまで追い出されない。LRU の欠損は、相の中でまだ要求されていない頁の要求でだけ起こり、各相で $k$ 回以下である。したがって $C_{\mathrm{LRU}}(\sigma)\le kN$ である。
段 2(最適値は相をまたぐごとに 1 回以上)。$i=1,\dots,N-1$ について、第 $i$ 相の最初の要求を時刻 $u_i$、その頁を $p_i$ とし、区間 $I_i$ を時刻 $u_i+1$ から第 $i+1$ 相の最初の要求の時刻 $u_{i+1}$ まで(両端を含む)とする。第 $i$ 相には $p_i$ 以外に $k-1$ 個の相異なる頁が現れ、それらは時刻 $u_i$ より後に要求される。第 $i+1$ 相の最初の頁は第 $i$ 相の $k$ 個の頁のどれとも異なる。よって $I_i$ には $p_i$ と異なる相異なる $k$ 個の頁が要求される。一方、どのアルゴリズムも時刻 $u_i$ の要求に応えたあとは $p_i$ をキャッシュに持つので、それ以外の頁は $k-1$ 個以下しか持たない。$I_i$ の中で欠損しなければキャッシュは変わらず、これら $k$ 個の頁をすべて持つことになるので、$I_i$ の中で少なくとも 1 回欠損する。区間 $I_1,\dots,I_{N-1}$ は互いに交わらないので、$\mathrm{OPT}(\sigma)\ge N-1$ である。
段 1・2 から $C_{\mathrm{LRU}}(\sigma)\le kN\le k(\mathrm{OPT}(\sigma)+1)$ である。$\square$
頁が $k+1$ 個以上あるとする。どの決定的なオンラインアルゴリズム $A$ も、$c< k$ について $c$-競合的でない。
初めのキャッシュ $K_0$ を含む $k+1$ 個の頁を選び、それだけを使う。$T\ge1$ を固定する。敵は各時刻に、$A$ のキャッシュにない頁のうち番号の最も小さいものを要求する(キャッシュは $k$ 個以下なので必ずある)。$A$ は決定的なので、この列 $\sigma$ は $A$ から決まり、$A$ は毎回欠損して $C_A(\sigma)=T$ である。
$\sigma$ を知るオフラインの規則 $F$ を、欠損でキャッシュが満ちていれば「次に要求される時刻が最も遅い頁(もう要求されない頁があればそれ)」を追い出すものとする。キャッシュが満ちるまでの欠損は $k$ 回以下である。満ちたあと時刻 $t$ に欠損したとすると、そのときのキャッシュは要求された頁 $r$ 以外の $k$ 個の頁全部で、$F$ はその中で次の要求が最も遅い頁 $e$ を追い出す。$e$ がもう要求されなければ以後は欠損しない。そうでなければ、次の欠損は $e$ が次に要求される時刻 $t'$ で、残りの $k-1$ 個の頁はどれも時刻 $t$ と $t'$ の間に要求されるので、$t'-t\ge k$ である。よって満ちたあとの欠損は $T/k+1$ 回以下で、$\mathrm{OPT}(\sigma)\le C_F(\sigma)\le T/k+k+1$ である。
$A$ が定数 $a$ について $c$-競合的で $c< k$ なら、どの $T$ でも $T\le c(T/k+k+1)+a$、すなわち $T(1-c/k)\le c(k+1)+a$ となるが、$T$ を大きくとるとこれは成り立たない。$\square$
2 つの定理から、決定的なページングの最良の競合比は $k$ で、LRU はそれを達成する。LRU と FIFO が $k$ 倍より悪くならず、どのオンラインの規則も $k$ 倍を下回れないことは Sleator と Tarjan による(FKLMSY91 §1、p. 1)。FIFO の評価はこの記事では証明しない。
thm-oa-lower の敵は、アルゴリズムのキャッシュの中身を知っていることを使った。乱数を使えば、乱数を見られない敵に対しては $k$ より良い競合比が得られる。標識アルゴリズム(marking algorithm)は、初めはキャッシュの頁に印を付けておき、要求された頁に印を付け、印の付いた頁が $k+1$ 個になった時点で直前に要求された頁以外の印を消す。欠損したときは、キャッシュの中の印のない頁から一様に無作為に 1 つを選んで追い出す(FKLMSY91 §3、p. 3)。
1 は FKLMSY91 Theorem 1(p. 3)、2 は同 Theorem 4 と Corollary 5(pp. 6–8)で、この記事では証明しない。$H_k\le1+\ln k$ なので、乱数によって競合比は $k$ から $\ln k$ の程度に下がる。$2H_k< k$ となるのは $k\ge5$ のときである($2H_5\approx4.57$)。
| 問題と規則 | 競合比 | 条件 | 根拠 |
|---|---|---|---|
| スキーレンタル、損益分岐の規則 $A_B$ | $2-1/B$(厳密) | 決定的 | thm-oa-ski |
| スキーレンタル、決定的な規則すべて | $\ge2-1/B$ | 厳密な比で比べる | thm-oa-ski |
| ページング、LRU | $k$($C\le k\,\mathrm{OPT}+k$) | キャッシュ $k$ | thm-oa-lru |
| ページング、決定的な規則すべて | $\ge k$ | 頁が $k+1$ 個以上 | thm-oa-lower |
| ページング、標識アルゴリズム | $\le2H_k$ | 敵は乱数を見ない | thm-oa-marking |
| ページング、乱数を使う規則すべて | $\ge H_k$ | 同上、頁が $k+1$ 個以上 | thm-oa-marking |
競合比を求める手順は次のとおりである。
$B=10$ とする。損益分岐の規則は 10 日目の朝に買う。$d=5$ なら費用 $5$(最適値 $5$)、$d=9$ なら $9$(最適値 $9$)、$d=10$ なら $9+10=19$(最適値 $10$)で比は $1.9=2-1/10$、$d=30$ でも費用は $19$ のままである。買う日を $t$ にしたときの最悪の比 $\max_d C_{A_t}(d)/\mathrm{OPT}(d)$ は、$t=1,5,10,11,20$ で $10,\ 2.8,\ 1.9,\ 2,\ 2.9$ であり、$t=10$ で最小になる。
図: 左は B=10 のスキーレンタル問題で、買う日 t を横軸に、最悪の比を縦軸にとったグラフ。t が小さいと比は大きく、t=10 で最小値 1.9 をとり、それより後は 1 日ごとに 0.1 ずつ増える。右は日数 d に対する費用で、損益分岐の規則は 9 日目まで最適値と一致し、10 日目以降は 19 で一定、最適値は 10 で一定、借り続ける規則は d とともに増え続ける。
$k=3$、要求の列を $1,2,3,4,1,2,5,1,2,3,4,5$、初めのキャッシュを空とする。LRU は $10$ 回、FIFO は $9$ 回欠損する。オフラインで「次に要求される時刻が最も遅い頁」を追い出すと $7$ 回で、これが最適値である。実際、どの規則も 5 種類の頁の最初の要求(時刻 $1,2,3,4,7$)で欠損し、時刻 $7$ の後のキャッシュは頁 $5$ のほかに高々 $2$ 個の頁しか持たないので、時刻 $8$〜$11$ に $1$ 回ずつ要求される頁 $1,2,3,4$ のうち $2$ 個以上で欠損する(キャッシュは欠損のときにだけ変わり、入るのは要求された頁である)。LRU の比は $10/7\approx1.43$ で、thm-oa-lru の上界 $3\cdot7+3=24$ よりずっと小さい。
$k=2$、頁を $1,2,3$、初めのキャッシュを空とし、敵が LRU のキャッシュにない最小の頁を要求し続けると、列は $1,2,3,1,2,3,\dots$ となり、LRU は毎回欠損する。長さ $T=12$ では LRU が $12$ 回、最適値は $7$ 回、$T=100$ では LRU が $100$ 回、最適値は $51$ 回で(どちらも thm-oa-lower の証明の規則 $F$ で達成され、最小値である。最初の $3$ 回はどの規則も欠損し、$t=3,5,7,\dots$ について、時刻 $t$ の要求に応えたあとのキャッシュはその頁ともう $1$ 個しか持たないので、時刻 $t+1,t+2$ に要求される残りの $2$ 個の頁のどちらかで欠損する。これらの区間は交わらない)、比は $k=2$ に近づく。
| 外す条件 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 厳密な比($a=0$)で比べる | 初日に買う規則は $C=B\le\mathrm{OPT}+B$ | thm-oa-ski の 2 から読める「$2-1/B$ より小さい比では競合的でない」。2 の不等式そのものは成り立つ(初日に買う規則でも $d=1$ で $B\ge2-1/B$)が、加法的な定数を許すと 1-競合的な規則がある |
| いつかは買う($t<\infty$) | 借り続ける規則は $d$ 日で費用 $d$、最適値 $B$ | どの $c$ についても $c$-競合的でない |
| 追い出す頁を最近の使用で選ぶ | LFU(ex-oa-lfu) | LRU のような $k$-競合性。LFU はどの $c$ についても $c$-競合的でない |
| アルゴリズムが決定的 | 標識アルゴリズム(thm-oa-marking) | thm-oa-lower の下界 $k$。$k\ge5$ で $2H_k< k$ |
| 頁が $k+1$ 個以上 | 頁が $n\le k$ 個なら、どの規則も欠損は $n$ 回以下 | thm-oa-lower。どの規則も $C\le1\cdot\mathrm{OPT}+n$ |
$k\ge2$、$m\ge2$ とし、初めのキャッシュを空とする。頁 $1,\dots,k-1$ をそれぞれ $m$ 回ずつ続けて要求し、そのあと新しい頁 $x,y$ を $x,y,x,y,\dots$ と $m-1$ 回ずつ交互に要求する。$x$ の最初の要求ではキャッシュに空きがある。以後、$x$ か $y$ の要求のたびにキャッシュは頁 $1,\dots,k-1$ と $x,y$ の一方で満ちており、要求の回数はそれぞれ $m$ 回と $m-1$ 回以下なので、LFU は $x,y$ のキャッシュにある方を追い出し、毎回欠損する。LFU の欠損は $(k-1)+2(m-1)$ 回である。一方、$y$ の最初の要求で頁 $1$ を追い出せば、以後は欠損しないので、$\mathrm{OPT}\le k+1$ である。$m\to\infty$ で比は限りなく大きくなる。$k=3$、$m=100$ では LFU が $200$ 回、最適値が $4$ 回である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 競合比は平均的な入力での比である | どの要求の列でも成り立つ最悪の場合の比 | def-oa-competitive |
| 乱数を使う規則の下界にも、キャッシュの中身を見る敵を使う | 敵は乱数を見られない。見られる敵なら乱数は役に立たない | thm-oa-lower の証明は決定性を使う |
| 比べる相手はオンラインの最良の規則である | 未来を知るオフラインの最適値と比べる | def-oa-main |
| 競合比が小さい規則は実際の欠損も少ない | 競合比は最悪の比で、ex-oa-belady のように実際の比はずっと小さいことが多い | 上界は最悪の列に合わせた評価 |
オンラインの規則に $k$ 個、オフラインの規則に $h\le k$ 個のキャッシュを与えて比べると、LRU の比は $k/(k-h+1)$ で、これがオンラインの規則で最良であることも Sleator と Tarjan による(FKLMSY91 §7、p. 11。この記事では証明しない)。$h=k$ では $k$、$k$ が偶数で $h=k/2$ なら $k/(k/2+1)<2$ で、オフラインの規則より大きなキャッシュを持てば最悪の比は定数で抑えられる。
ページングは、グラフの頂点に置いた $k$ 台のサーバのどれかを要求された頂点へ動かす $k$ サーバ問題の、どの 2 頂点の間の移動も費用 1 の場合と同じ問題である(FKLMSY91 §2、p. 3)。要求が 1 つずつ届いて応答を取り消せない状況は、データ構造の操作の列、資源の割り当て、データを 1 回だけ読む ストリーミングアルゴリズム にも現れる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する