Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

> 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. Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items. This is undergraduate stuff I once had to know for exams in machine architectures and operating systems. The choice of LRU replacement is favorable when there exists "locality of reference"; that's what it's…

Related: the author, Dan Luu has, IMHO, one of the best IT-related Twitter feeds out there: https://twitter.com/danluu Highly recommended.

> But what if we take two random choices (2-random) and just use LRU between those two choices? > Also, we can see that pseudo 3-random is substantially better than pseudo 2-random, which indicates that k-random is probably an improvement over 2-random for the k. Some k-random policy might be an improvement over DIP. This sounds very similar to tournament selection schemes in evolutionary algorithms. You can control the amount of selective pressure by adjusting the tournament size. I think…

I've been playing a lot of Baldur's Gate 3 lately and this kind of reminds me of when you have to roll a d20 in a skill check. Early in the game there are skill checks with a difficultly class of 2 (need to roll a 2 or higher to succeed) but you might have proficiency in that skill so you get a +3 modifier to your roll. But if your base d20 roll result is a 1 then this…