LRU Cache: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
=Overview= | =Overview= | ||
The Least Recently Used caches are justified by the [[The_Optimal_Caching_Problem#The_B.C3.A9l.C3.A1dy_Theorem|Bélády Theorem]] | |||
An implementation where get() is O(1) and put() is O(n): [https://github.com/NovaOrdis/playground/blob/master/leetcode/146-lru-cache/src/main/java/playground/leetcode/lruCache/LRUCacheOn.java Playground LRUCache O(n)] | An implementation where get() is O(1) and put() is O(n): [https://github.com/NovaOrdis/playground/blob/master/leetcode/146-lru-cache/src/main/java/playground/leetcode/lruCache/LRUCacheOn.java Playground LRUCache O(n)] | ||
Revision as of 19:41, 20 October 2021
Internal
Overview
The Least Recently Used caches are justified by the Bélády Theorem
An implementation where get() is O(1) and put() is O(n): Playground LRUCache O(n)
An implementation where both get() and put() are O(1): Playground LRUCache O(1)
The idea is to maintain the keys in a map (O(1)) for retrieval, but the time ordering is maintained implicitly in the structure of a double-linked list that can be manipulated in O(1): Playground LRUList
