2017年10月27日
LRU の最適性？
- 2017-10-27 (Fri)
- 一般
キャッシュのアルゴリズムを考えた時，オンラインにやるなら LRU が直感的にはユニバーサルに最適なんじゃなかろうかとか思ったのだけど，よく分からんのでちょっと調べてみたら面白そうな論文を見つけた：On the optimality of Least Recently Used．
各アルゴリズムでのページフォルト数を確率変数とみなした上で，それら確率変数間の大小関係（stochastic ordering）をもってアルゴリズムの良し悪しを考えようという感じのアプローチ．この大小関係は，X1 と X2 を確率変数としたら「 X1 ≦ X2 ⇔ forall x, P(X1 ＞ x) ≦ P(X2 ＞ x) 」で定義される．どんな基準点 x を持ってきても X1 より X2 の方が x を超えている可能性が高いなら，X1 より X2 のほうが大きいと言いましょうと．自然な定義な気がする．
まだこの論文もちゃんと読んでないけど，その後に出た著者の博論（https://depositonce.tu-berlin.de/handle/11303/2683）も面白そう．
- Comments: 0
- TrackBack (Close): -