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

1. Cache capacity is a positive integer, and the cached key and value are of type int
2. Read cache func get(key int) int:
   • key already exists, return the corresponding value
   • key does not exist, return -1
3. 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

1. cache:map[int]*listNode, key to node mapping; Where listNode data:key, value
2. List:*listNode, a bidirectional linked list, maintains the last use time of the cache
3. Capacity:int, linked list capacity

Pseudocode

• Read cache
  1. 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
  2. key does not exist:
     • Return -1
• Write cache (update cache)
  1. 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
  2. Key does not exist:
     1. 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
     2. 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

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

1. Cache capacity, cached key and value are natural numbers (can be 0, which will be handled separately in the code)
2. Read cache func get(key int) int: (same as lru)
   • key already exists, return the corresponding value
   • key does not exist, return -1
3. 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
  1. 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
  2. Does not exist: return -1
• 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

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