3 ms·
There is obviously a LRU-like element in the algorithm because 1. Evacuation generally shifts items to the right. 2. The Hand moves to the left. 3. Items ski
by kazinator 3y ago
There is obviously a LRU-like element in the algorithm because
1. Evacuation generally shifts items to the right.
2. The Hand moves to the left.
3. Items skipped by the Hand (appearing to its right) are spared from eviction until the Hand wraps around.
You can see it in the animation. D is flipped to visited just in the nick of time, and the Hand moves over it. Then it is spared from then on until the Hand wraps around (the animation doesn't go that far). Items that are used frequently will tend to be in the Visited state when the Hand passes over them, and stay cached.
- cryptonym 3y agoI don't understand why D is NOT switched to false when the hand moves left and removes E. At the beginning A is switched to false when the hand moves left over it.
- joaomacp 3y agoI watched it again and read the algorithm description part, and I think you're right - D should have been switched to false, as the hand was pointing to it when a cache miss happened.
- j16sdiz 3y agoI watched it again and checked it against the python reference code. The code and documentation are correct, the animation is wrong.
- kazinator 3y agoThe behavior is inconsistent with what happens to A and B at the very beginning. Whenever the hand skips a visited node in search of an unvisited one, it must flip it to unvisited. If D were given this special treatment every time the hand cycles around, it will forever stay in the cache even if not accessed (D-plomatic immunity?)
- deleted 3y ago[deleted]
- kazinator 3y agoYes; D is spared by the fact that the hand passed over it, but it should be turned gray so that if it is not accessed again by the time the hand comes around again, it will be toasted.