テープへのファイルの保存

磁気テープ¹に \(n\) 個のファイルを保存したいとします。テープに保存したファイルは後でユーザーが読み込みますが、テープからのファイルの読み込みはディスクからの読み込みのようにはいきません。磁気テープを読み込むときには、まず目的のファイルがあるところまでテープを送る必要があるからです。 \(L[1..n]\) でファイルの長さを表すことにして、\(i\) 番目のファイルの長さが \(L[i]\) だとします。ファイルが \(1\) から \(n\) という順番で保存されていたとすると、\(k\) 番目のファイルにアクセスするコストは次の式で表されます: \[ \mathit{cost}(k) = \sum_{i=1}^{k} L[i] \] \(k\) 番目のファイルを読むには \(k\) 番目までのファイルを送らなくてはいけないということが、この関数で表されています。それぞれのファイルに対する探索の頻度が同じだと仮定すれば、ランダムなファイルに対する探索コストの期待値を求められます: \[ E[\mathit{cost}] = \sum_{k=1}^{n} \frac{\mathit{cost}(k)}{n} = \sum_{k=1}^{n} \sum_{i=1}^{k} \frac{L[i]}{n} \]

テープ上のファイルの順番を変えると、各ファイルへのアクセスコストが変化し、読み込みが高速になるファイルもあれば遅くなるファイルもあります。この結果、探索コストの期待値も変化するはずです。つまり、\(\pi(i)\) でテープで \(i\) 番目に保存されているファイルの添え字を表すことにすると、置換 \(\pi\) のコストの期待値は次の式で表されます: \[ E[\mathit{cost}(\pi)] = \sum_{k=1}^{n}\sum_{i=1}^{k} \frac{L[\pi(i)]}{n} \] このコストの期待値を最小化したい場合、どのような順番を使うべきでしょうか？直感的には答えは明らかです: 短いものから長いものに向かって並べるべきです。しかし直感というのは厄介な代物であり、この順番が正しいことを示すには ~~飛行機に乗り込んで核爆弾で全てを吹き飛ばす~~ 実際に証明しなければなりません！

命題 4.1 \(E[\mathit{cost}(\pi)]\) は全ての \(i\) で \(L[\pi(i)] \leq L[\pi(i+1)]\) が成り立つとき最小となる。

証明ある添え字 \(i\) で \(L[\pi(i)] > L[\pi(i+1)]\) だったとする。簡単のため \(a = \pi(i)\), \(b = \pi(i+1)\) とする。 \(a\) と \(b\) を交換すると、\(a\) へのアクセスコストは \(L[b]\) 増え、\(b\) へのアクセスコストは \(L[a]\) 減る。よってこの交換で全体のコストの期待値は \((L[b] - L[a])/n\) だけ増える。 \(L[b] < L[a]\) だったから、この交換によって元より良い順番が手に入っている。よって \(L[\pi(i)] \leq L[\pi(i+1)]\) となっていない \(i\) がある場合には、要素を交換することでコストを減少させることができる。したがって全ての \(i\) で \(L[\pi(i)] \leq L[\pi(i+1)]\) のときコストの期待値は最小となる。 \(\Box\)

これは私たちが最初に出会う貪欲アルゴリズム (greedy algorithm) です。ファイルアクセスにかかる全体コストの期待値を最小化するには、一番早くアクセスできるファイルを最初に書き込み、残りについて同じ処理を再帰的に行います。バックトラッキングも動的計画法もありません。ただ局所的に最良な選択肢を選んで盲目的に進むだけです。効率の良いソートアルゴリズムを使えば、順番を決める処理の実行時間は \(O(n \log n)\) であり、この他にファイルへの書き込み時間がかかります。この貪欲アルゴリズムの証明では、他のアルゴリズムで作った順番が交換によって改善できてしまうことを示している点に注目してください。

このアイデアを推し進めてみましょう。新しい入力として各ファイルのアクセス頻度を表す \(F[1..n]\) が加わり、ファイル \(i\) はテープが使われなくなるまでにちょうど \(F[i]\) 回アクセスされるとします。このときテープ上の全てのファイルに対するアクセスにかかる合計コストは次のようになります: \[ \begin{aligned} \Sigma \mathit{cost}(\pi) & = \sum_{k=1}^{n} \left(F[\pi(k)] \cdot \sum_{i=1}^{k} L[\pi(i)]\right) \\ & = \sum_{k=1}^{n} \sum_{i=1}^{k} (F[\pi(k)] \cdot L[\pi(i)]) \\ \end{aligned} \]

さてここでもファイルの順番を変えると探索にかかる合計コストが変化します。コストを最小化するには、どんな順番でファイルを保存すればよいでしょうか？ (この問題は最適二分探索木の問題と似ていると言うこともできるでしょう。しかしデータ構造とコスト関数がどちらも異なっているので、答えのアルゴリズムも異なっているはずです)

先ほど証明したのは、全てのファイルに対するアクセス頻度が等しいならファイルをサイズで昇順にソートすべきであるということです。またファイルのサイズ \(L[i]\) が全て同じで頻度だけが異なっているならば、アクセス頻度で降順にソートすべきであるということは直感的に分かりますし、実際命題 4.1の証明を改変すれば証明も難しくありません。

ではサイズと頻度が両方とも変化したら？この場合、サイズと頻度の比 \(L/F\) でソートすべきであるということが示せます:

命題 4.2 \(\Sigma \mathit{cost}(\pi)\) は全ての \(i\) に対して \(\displaystyle \frac{L[\pi(i)]}{F[\pi(i)]} \leq \frac{L[\pi(i+1)]}{F[\pi(i+1)]}\) が成り立つとき最小となる。

証明ある添え字 \(i\) で \(L[\pi(i)]/F[\pi(i)] > L[\pi(i+1)]/F[\pi(i+1)]\) だったとする。簡単のため \(a = \pi(i)\), \(b = \pi(i+1)\) とする。 \(a\) と \(b\) を交換すると、\(a\) へのアクセスコストは \(L[b]\) 増え、\(b\) へのアクセスコストは \(L[a]\) 減る。よってこの交換で全体のコストの期待値は \((F[a] \cdot L[b] - F[b] \cdot L[a])/n\) だけ増える。ここで \[ \frac{L[a]}{F[a]} > \frac{L[b]}{F[b]} \Leftrightarrow L[b]F[a] - L[a]F[b] < 0 \] だから、この交換によって全体のコストは減少する。したがって、問題で示された順番に並んでいない任意の順番が与えられたとき、交換を行うことでその順番を改善できる。 \(\Box\)

磁気テープなんて何十年も前にお役御免になっているだろうと言いかけた人は、近くのスーパーコンピューター施設を見学に行ってテープロボットを見てくることをお勧めします。そのような施設が近くに無いなら、代わりに図書館の本棚に本を並べる処理を想像してもいいでしょう。ええ、あの木の死体とインクからできているレンガみたいな形をした奇妙な物体です。^[return]