Cache

介紹

  • LRU cache (Least Recently Used)

  • Adaptive Replacement Cache

  • Low Inter-reference Recency Set

  • 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)

相關實做

Redis

Site

http://redis.io/

Repo

https://github.com/antirez/redis/

Language

C

可以想像為功能更複雜的 Memcached