Cache
介紹
LRU (Least Recently Used)
LFU (Least Frequently Used)
LRFU (LRU + LFU)
ARC (Adaptive Replacement Cache)
LIRS (Low Inter-reference Recency Set)
W-TinyLFU (Window TinyLFU)
- Bélády’s optimal
演算法假設能知道未來再也不會用到某值，故無法實作，可以當成 Cache 演算法的 Upper Bound
Example
O* nuances
Traversal |
Cache Misses in Traversal |
|
Array |
O(N) |
O(0) |
Linked List |
O(N) |
O(N) |