Content deleted Content added
←Created page with '"This can be implemented in practice with the Least Recently Used policy, which is shown to be within a factor of 2 of the offline optimal replacement strategy." I...' |
No edit summary |
||
Line 4:
[[User:Vecter|Vecter]] 23:35, 7 June 2007 (UTC)
:No, it's basically correct. The following lemma is proved in the Frigo paper from the references:
::Lemma 12 Consider an algorithm that causes Q'(n;Z,L) cache misses on a problem of size n using a (Z, L) ideal cache. Then, the same algorithm incurs Q(n;Z,L) ≤ 2Q'(z;Z/2,L) cache misses on a (Z,L) cahce that uses LRU replacement.
:Note that, technically, you need an LRU cache of twice the size of the optimal-replacement cache to simulate it within a factor of two.
:[[User:Stevenj|—Steven G. Johnson]] 16:10, 8 June 2007 (UTC)
| |||