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...' |
m Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{WikiProject Computer science}}. Tag: |
||
| (9 intermediate revisions by 6 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=Start|
{{WikiProject Computer science|importance=low}}
}}
"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."
Line 4 ⟶ 7:
[[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) cache 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)
== cache-oblivious unrolled linked lists ==
"it is possible to design a variant of unrolled linked lists which is cache-oblivious" is false. The closest thing is the packed-memory array, but its append is slow. Normal and unrolled linked lists have constant time append. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/190.135.57.152|190.135.57.152]] ([[User talk:190.135.57.152|talk]]) 00:10, 27 May 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
| |||