Baidu Baike:

LRU stands for Least Recently Used. It is a common page replacement algorithm that selects the pages that have not been Used for the most recent time to eliminate the page. The algorithm assigns each page an access field, which is used to record the time T experienced by a page since it was visited last time. When a page needs to be eliminated, the page with the largest T value in the existing page, that is, the least recently used page, is selected to be eliminated.

LeetCode:

146. LRU caching mechanism

✨ I learned LRU page replacement algorithm when I was learning operating system in my sophomore year. At that time, I could only manually simulate with paper and pen. Today, I saw LRU evictionAlgo when I was looking at the example of strategy mode of design mode, so I went to Leetcode to find this problem. A map can reduce the value time complexity to O(1), and a bidirectional list can simulate the order of use

Design LRUCash data structures

Design method

The put method:

  • If there is a key, update the value of the node and move the node to the head of the list

  • If a key exists, check whether the capacity is reached.

    If the capacity is reached, the end of the list element is deleted.

    Finally, construct the node, add the node to the linked list header, and add the cashMap

The get method:

  • If the key does not exist, return -1
  • If it exists, move the node to the head of the list

Code implementation

type LRUCache struct {
	capacity   int
	head, tail *DNode
	cashMap    map[int]*DNode
}

type DNode struct {
	prev       *DNode
	next       *DNode
	key, value int
}

func Constructor(capacity int) LRUCache {
	l := LRUCache{
		capacity: capacity,
		head:     initNode(0.0),
		tail:     initNode(0.0),
		cashMap:  map[int]*DNode{},
	}
	l.head.next = l.tail
	l.tail.prev = l.head
	return l
}

func (l *LRUCache) Get(key int) int {
	node, ok := l.cashMap[key]
	if! ok {return - 1
	}
	l.removeToHead(node)
	return node.value
}

func (l *LRUCache) Put(key int, value int) {
	/ / there
	if node, ok := l.cashMap[key]; ok {
		node.value = value
		l.removeToHead(node)
		return
	}
	/ / does not exist
	if len(l.cashMap) >= l.capacity {
		removed := l.removeTail()
		delete(l.cashMap, removed.key)
	}
	node := initNode(key, value)
	l.cashMap[key] = node
	l.addNodeToHead(node)
}

func initNode(key, value int) *DNode {
	return &DNode{
		key:   key,
		value: value,
	}
}

func (l LRUCache) addNodeToHead(node *DNode) {
	node.prev = l.head
	node.next = l.head.next
	l.head.next.prev = node
	l.head.next = node
}

func (l LRUCache) removeTail(a) *DNode {
	node := l.tail.prev
	l.removeNode(node)
	return node
}

func (l LRUCache) removeToHead(node *DNode)  {
	l.removeNode(node)
	l.addNodeToHead(node)
}

func (l LRUCache) removeNode(node *DNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}
Copy the code

🎈 : Do you want to write a container/ List

import "container/list"

type LRUCache struct {
	capacity    int
	dLinkedList *list.List
	cash        map[int]*list.Element
}

type DLinkNode struct {
	key, value int
}

func (d DLinkNode) Value(a) interface{} {
	return d.value
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity:    capacity,
		dLinkedList: list.New(),
		cash:        map[int]*list.Element{},
	}
}

func (l *LRUCache) Get(key int) int {
	element, ok := l.cash[key]
	if! ok {return - 1
	}
	l.dLinkedList.MoveToFront(element)
	return element.Value.(*DLinkNode).value
}

func (l *LRUCache) Put(key int, value int) {
	element, ok := l.cash[key]
	// If key already exists
	if ok {
		node := element.Value.(*DLinkNode)
		node.value = value
		l.dLinkedList.MoveToFront(element)
	}
	// If the key does not exist
	if len(l.cash) >= l.capacity {
		back := l.dLinkedList.Back()
		l.dLinkedList.Remove(back)
		delete(l.cash, back.Value.(*DLinkNode).key)
	}
	node := &DLinkNode{
		key:   key,
		value: value,
	}
	front := l.dLinkedList.PushFront(node)
	l.cash[key] = front
}

Copy the code

conclusion

  • When operating a bidirectional linked list, pay attention to the sequence of points, such as: writeaddNodeToHeadThe time,l.head.next.prev = node å’Œ l.head.next = nodeIt took a long time to find the bug
  • Go language built-in data structure, not familiar, the second code implementation map value type is *list.ElementElement handle, which is easy to calllistBuilt-in methods