Differences between LRU and LFU
Both LRU and LFU are page replacement algorithms for memory management.
LRU: Least Recently Used (longest time) elimination algorithm. LRU is the page that has not been used for the longest time.
LFU: Least Frequently Used. LFU is the least used page in a period of time.
-
example
Assume that the period T of LFU method is 10 minutes, the time spent accessing the following pages is exactly 10 minutes, and the memory block size is 3. If the required page order is as follows:
2 1 2 1 2 3 4
---------------------------------------->
- When you need to use page 4, 1, 2, and 3 are stored in the memory block. If there is no page 4 in the memory block, page missing interruption will occur. At this time, the memory block is full and page replacement is required.
- If the LRU algorithm is used, page 1 should be replaced. Because page 1 has not been used for the longest time, pages 2 and 3 have been used behind it.
- If LFU algorithm is used, page 3 should be changed. During this period, page 1 was visited twice, page 2 was visited three times, and page 3 was visited only once, with the least number of visits in a period of time.
The key of LRU is to see the length of time from the last time the page is used to the replacement. The longer the time, the page will be replaced;
The key of LFU is to look at the frequency (Times) of pages used in a certain period of time. The lower the frequency, the pages will be replaced.
-
LRU algorithm is suitable for: large files such as game clients (recently loaded map files);
-
LFU algorithm is suitable for: small files and fragmented files, such as system files and application files;
-
LRU consumes less CPU resources, while LFU consumes more CPU resources.
LRU (maximum time)
The algorithm has not been used for the longest time recently. LRU is the page that has not been used for the longest time
function
- Cache capacity is a positive integer, and the cached key and value are of type int
- Read cache func get(key int) int:
- key already exists, return the corresponding value
- key does not exist, return -1
- Write cache func put(key int, value int):
- key already exists, modify the corresponding value
- If the key does not exist, write to this group of caches. If the cache capacity has reached the upper limit before writing, the cache that has not been used for the longest time should be eliminated (emphasis: both read and write caches are considered to be used)
data structure
-
Last time to use the bidirectional linked list to maintain the cache:
- Convention: the nodes in the positive direction of the list (from head to tail) are sorted according to the use time - the earlier the node is used (that is, it has not been used for a long time), the closer it is to the tail of the list
- Maintenance: move the linked list node corresponding to the cache to the head of the linked list every time the cache is used; When the cache is obsolete, you only need to delete the tail node
-
Add a map to record the mapping relationship between the key and the linked list node; Solution: if you only use a two-way linked list, you must traverse the linked list every time you judge whether a key exists
- cache:map[int]*listNode, key to node mapping; Where listNode data:key, value
- List:*listNode, a bidirectional linked list, maintains the last use time of the cache
- Capacity:int, linked list capacity
Pseudocode
- Read cache
- key exists:
- Delete the cache node in the original linked list and reinsert it into the head of the linked list,
- Return the corresponding value
- key does not exist:
- Return -1
- key exists:
- Write cache (update cache)
- Key exists:
- Update the value value of the cache node
- Delete the cache node in the original linked list and reinsert it into the head of the linked list
- Key does not exist:
- Capacity has reached the maximum:
- Delete the tail node in the linked list (record the key of the node)
- Delete the corresponding mapping relationship according to the key recorded in the previous step
- Construct a new node according to the input parameters:
- Insert the new node into the head of the linked list
- Mapping relationship between new key and new node
- The capacity does not reach the upper limit:
- Construct a new node according to the input parameters:
- Insert the new node into the head of the linked list
- Mapping relationship between new key and new node
- Capacity has reached the maximum:
- Key exists:
Golang code implementation
// Bidirectional linked list node type doublyListNode struct { key int value int prev *doublyListNode next *doublyListNode } // Construct a two-way empty linked list (the first and last points are empty nodes) func newDoublyList() *doublyListNode { headNode := &doublyListNode{} tailNode := &doublyListNode{} headNode.next = tailNode tailNode.prev = headNode return headNode } // Add nodes to the head of the linked list func (dl *doublyListNode) addToHead(node *doublyListNode) { dl.next.prev = node node.next = dl.next dl.next = node node.prev = dl } // Delete nodes in the linked list func removeNode(node *doublyListNode) { node.next.prev = node.prev node.prev.next = node.next } // LRUCache specific cache type LRUCache struct { cache map[int]*doublyListNode head *doublyListNode tail *doublyListNode capacity int } // Constructor build cache container func Constructor(capacity int) LRUCache { dl := newDoublyList() return LRUCache{ cache: make(map[int]*doublyListNode), head: dl, tail: dl.next, capacity: capacity, } } func (lruCache *LRUCache) Get(key int) int { // Get cache according to key v, ok := lruCache.cache[key] // If there is no cache, return -1 if !ok { return -1 } // If there is cache removeNode(v) // Remove the cache lruCache.head.addToHead(v) // Add cache to bidirectional linked list header return v.value } // Put new cache func (lruCache *LRUCache) Put(key int, value int) { // There is already a cache if v, ok := lruCache.cache[key]; ok { // v is the node in the double linked list v.value = value // Update values in linked list nodes lruCache.cache[key] = v // Update mapping relationship in cache removeNode(v) // Remove the cache lruCache.head.addToHead(v) // Add cache to bidirectional linked list header return } // Cache is too long to eliminate cache if len(lruCache.cache) >= lruCache.capacity { node := lruCache.tail.prev removeNode(node) // Delete this node delete(lruCache.cache, node.key) // Clear the least recently used cache } newNode := &doublyListNode{ key: key, value: value, } lruCache.cache[key] = newNode lruCache.head.addToHead(newNode) }
LFU (minimum times)
function
- Cache capacity, cached key and value are natural numbers (can be 0, which will be handled separately in the code)
- Read cache func get(key int) int: (same as lru)
- key already exists, return the corresponding value
- key does not exist, return -1
- Write cache func put(key int, value int):
- key already exists, modify the corresponding value
- If the key does not exist, write to this group of caches. If the cache capacity has reached the upper limit before writing, the cache with the least number of uses should be eliminated (remember that its number of uses is n);
- If the number of caches used n is greater than one, the cache that has not been used for the longest time will be eliminated (that is, the lru rule will be followed at this time)
data structure
// The specific cache frequency of LFUCache is the number of times it is used type LFUCache struct { recent map[int]*doublyListNode // The mapping from frequency to the most recently used node with frequency count map[int]int // Frequency mapping to the number of nodes corresponding to the frequency cache map[int]*doublyListNode // key to node mapping list *doublyList // Two way linked list, maintaining the usage times (priority) and last usage time of the cache capacity int // capacity }
Pseudocode
- Read cache
- Existence: (note that the node frequency is n)
- If there are other nodes with frequency = n+1, move the node to the front of all nodes with frequency = n+1;
- Otherwise, if there are other nodes with frequency = n, and the current node is not the nearest node, move the node to the front of all nodes with frequency = n;
- Otherwise, do not move the node (in this case, the node should stay in its current position)
- Update recent
- Update count
- Set node frequency +1
- Return the value of the node
- Does not exist: return -1
- Existence: (note that the node frequency is n)
- Write cache
- key exists
- Reference read cache - if the key exists, you can modify the corresponding value additionally
- non-existent:
- If the current cache capacity has reached the upper limit:
- Eliminate the tail cache node (remember that node freq is n)
- If there are no other nodes with freq = n, set recent to null
- Update cache
- Update count
- Construct a new node: key, value, frequency = 1
- Whether there are other nodes with frequency = 1:
- Exist: insert in front of them
- Does not exist: insert the tail of the linked list
- Update recent
- Update cache
- Update count
- If the current cache capacity has reached the upper limit:
- key exists
Golang code implementation
// Bidirectional linked list type doublyList struct { head *doublyListNode tail *doublyListNode } // Delete tail node func (dl *doublyList) removeTail() { pre := dl.tail.prev.prev pre.next = dl.tail dl.tail.prev = pre } // Whether the linked list is empty func (dl *doublyList) isEmpty() bool { return dl.head.next == dl.tail } // Bidirectional linked list node type doublyListNode struct { key int value int frequency int // Usage times prev *doublyListNode next *doublyListNode } // Insert a node before a node func addBefore(currNode *doublyListNode, newNode *doublyListNode) { pre := currNode.prev pre.next = newNode newNode.next = currNode currNode.prev = newNode newNode.prev = pre } // LFUCache specific cache type LFUCache struct { recent map[int]*doublyListNode // The mapping from frequency to the most recently used node with frequency count map[int]int // Frequency mapping to the number of nodes corresponding to the frequency cache map[int]*doublyListNode // key to node mapping list *doublyList // Two way linked list, maintaining the usage times (priority) and last usage time of the cache capacity int // capacity } func removeNode(node *doublyListNode) { node.prev.next = node.next node.next.prev = node.prev } // Constructor build cache container func Constructor(capacity int) LFUCache { return LFUCache{ recent: make(map[int]*doublyListNode), count: make(map[int]int), cache: make(map[int]*doublyListNode), list: newDoublyList(), capacity: capacity, } } func newDoublyList() *doublyList { headNode := &doublyListNode{} tailNode := &doublyListNode{} headNode.next = tailNode tailNode.prev = headNode return &doublyList{ head: headNode, tail: tailNode, } } func (lfu *LFUCache) Get(key int) int { if lfu.capacity == 0 { return -1 } node, ok := lfu.cache[key] if !ok { // key does not exist return -1 } // key already exists next := node.next if lfu.count[node.frequency+1] > 0 { // There are other caches with n+1 usage times. Move the specified cache to the front of all nodes with n+1 usage times removeNode(node) addBefore(lfu.recent[node.frequency+1], node) } else if lfu.count[node.frequency] > 1 && lfu.recent[node.frequency] != node { // There is no other cache with n+1 usage times, but there are other caches with n usage times, and the current node is not the nearest node // Move the specified cache to the front of all nodes used n times removeNode(node) addBefore(lfu.recent[node.frequency], node) } // Update recent lfu.recent[node.frequency+1] = node if lfu.count[node.frequency] <= 1 { // There are no other nodes with freq = n, and recent is null lfu.recent[node.frequency] = nil } else if lfu.recent[node.frequency] == node { // There are other nodes with freq = n, and recent = node. Move recent backward by one bit lfu.recent[node.frequency] = next } // Update the number of nodes corresponding to the usage times lfu.count[node.frequency+1]++ lfu.count[node.frequency]-- // Update cache usage node.frequency++ return node.value } // Put new cache func (lfu *LFUCache) Put(key int, value int) { if lfu.capacity == 0 { return } node, ok := lfu.cache[key] if ok { // key already exists lfu.Get(key) node.value = value return } // key does not exist if len(lfu.cache) >= lfu.capacity { // The cache is full, delete the last node, and update cache, count, recent (condition) accordingly tailNode := lfu.list.tail.prev lfu.list.removeTail() if lfu.count[tailNode.frequency] <= 1 { lfu.recent[tailNode.frequency] = nil } lfu.count[tailNode.frequency]-- delete(lfu.cache, tailNode.key) } newNode := &doublyListNode{ key: key, value: value, frequency: 1, } // Insert a new cache node if lfu.count[1] > 0 { addBefore(lfu.recent[1], newNode) } else { addBefore(lfu.list.tail, newNode) } // Update recent, count, cache lfu.recent[1] = newNode lfu.count[1]++ lfu.cache[key] = newNode }
-
Author wechat: folish_ is_ me
-
Author email: big_ox@163.com
First of all, I would like to introduce myself. I graduated from Jiaotong University in 13 years. I once worked in a small company, went to large factories such as Huawei OPPO, and joined Alibaba in 18 years, until now. I know that most junior and intermediate Java engineers who want to improve their skills often need to explore and grow by themselves or sign up for classes, but there is a lot of pressure on training institutions to pay nearly 10000 yuan in tuition fees. The self-study efficiency of their own fragmentation is very low and long, and it is easy to encounter the ceiling technology to stop. Therefore, I collected a "full set of learning materials for java development" and gave it to you. The original intention is also very simple. I hope to help friends who want to learn by themselves and don't know where to start, and reduce everyone's burden at the same time. Add the business card below to get a full set of learning materials