Comment by girvo
2 years ago
You've explained that wonderfully, thank you! I'm not the original commenter, but was also confused by my intuition here. That makes a lot more sense now :)
2 years ago
You've explained that wonderfully, thank you! I'm not the original commenter, but was also confused by my intuition here. That makes a lot more sense now :)
It didnt make any sense to me.
I think an intuitive perspective is that if you pick one item randomly, you cant use the LRU signal. So, you pick two items. Now you get to also use LRU. Notice that it doesnt add any value to pick three random items and then apply LRU.
> Notice that it doesnt add any value to pick three random items and then apply LRU.
It actually does. The more items you pick, the better it works, because at the ultimate stage of k=N you will always be picking the best item. For a lot of real-world distributions, there are rapidly diminishing returns with higher k, but the returns are still there.
[edit]
The same example as above works for k=3, observing that discarding one of the 3 chosen uniformly randomly devolves to the k=2 form.
k=3: MAX(A,B,C)
k=2: MEAN(MAX(A,B),MAX(B,C),MAX(A,C))
k=1:
If you think you need a better K, because you have insight into your distribtution, then don't use uniform, instead, use something more appropriate.
When k=N you degrade to LRU.
Your MAX / MEAN logic is completely flawed. If k=N then you'd have MAX(0..N), wouldn't this be optimal? But, this is LRU and it's not optimal.
All this is hand-waving. The proper response is to use the language of mathematics to prove how this algorithm behaves. Perhaps there is an optimal k.
1 reply →