Random boosting could have saved Mars pathfinder https://en.wikipedia.org/wiki/Priority_inversion
Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
41–44 of 44 posts
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#42Earlier quoted context omitted.
This comment is dangerously trivializing the problem. Even in cases where the access pattern is contiguous, not "anti-recent", etc. LRU can still fail to perform. For example, if you simply iterate over a contiguous list of 5 items with a cache size of 4, you will have a 0% hit rate with LRU. With 2 random, it would be > 0% because there is a chance you wouldnt evict the item in exactly the wrong time. The main takea…
Repeatedly iterating over a sequence items is in fact "anti-recent". Round-robin cycling is probably the simplest possible algorithm for accessing a set of items such that, at any time, the item that is accessed next is the one that was least recently visited. Proof: since that item was last visited, every other item in the set was visited.
You're missing exactly the point. "anti-recent" is a relative term. Imagine that the data set is actually 1000 items long, but we iterate through it five at a time, but we iterate over that five 10 times each before moving on to the next 5. Those five items are much more likely to be necessary than all the 995 other items, but the currently added member is less likely than the other 4 for the next loop. You see, its a relative term. If the cache size had been 5, we would say that this is a nearly perfect example of caching the most likely members to appear.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#43Earlier quoted context omitted.
A random strategy has less overhead than LRU because there is no bookkeeping.
This 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.”
Yes, and bookkeeping and randomness both cost something.
Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
#44Earlier quoted context omitted.
Repeatedly iterating over a sequence items is in fact "anti-recent". Round-robin cycling is probably the simplest possible algorithm for accessing a set of items such that, at any time, the item that is accessed next is the one that was least recently visited. Proof: since that item was last visited, every other item in the set was visited.
You're missing exactly the point. "anti-recent" is a relative term. Imagine that the data set is actually 1000 items long, but we iterate through it five at a time, but we iterate over that five 10 times each before moving on to the next 5. Those five items are much more likely to be necessary than all the 995 other items, but the currently added member is less likely than the other 4 for the next loop. You see, its…
[deleted]