2 ms·
>>When Are Randomized Algorithms Better Than LRU? >When the access pattern is random: recently used items are not more likely to be accessed than other items.
by carlmr 8y ago
>>When Are Randomized Algorithms Better Than LRU?
>When the access pattern is random: recently used items are not more likely to be accessed than other items.
Wouldn't they perform equally well in this case? There's no advantage in LRU, but also no disadvantage if they're really unpredictably random.
- adrianN 8y agoA random strategy has less overhead than LRU because there is no bookkeeping.
- dan-robertson 8y agoThis argument does not apply to the OP as it does not account for any bookkeeping. I think an actual answer is more complicated and will entirely depend on the definition of “random access pattern.”
- carlmr 8y agoYes, and bookkeeping and randomness both cost something.