Shulou(Shulou.com)06/01 Report--

Editor to share with you how to use the Goto language to achieve LRU Cache, I hope you will learn something after reading this article, let's discuss it together!

1 basic concepts

LRU is an old problem, that is, the least used recently, LRU is the abbreviation of Least Recently Used, is a commonly used page replacement algorithm in the operating system, choose the most recently unused pages to be eliminated. The algorithm gives each page a visit field, which is used to record the time t of a page since it was last visited. When a page needs to be eliminated, select the page with the largest t value in the existing page, that is, the page that is the least used recently.

Implement the basic data structure of LRU: Map+LinkedList

General rules:

When adding data, the new data node is placed in the head pointer and deleted when the tail node part is greater than the maximum length.

When deleting data, first look it up according to the rules of Map, and then delete according to the rules of the linked list.

When looking for data, look for it according to Map. If not, empty is returned. If there is any, the value of the data is returned and moved to the header node.

2 Code implementation of package mainimport "fmt" var head * Nodevar end * Nodetype Node struct {Key string Value string pre * Node next * Node} func (n * Node) Init (key string) Value string) {n.Key = key n.Value = value} type LRUCache struct {Capacity int / / Page initialization size Size int / / actual page size Map map [string] * Node / / specific cache} func GetLRUCache (capacity int) * LRUCache {lruCache: = LRUCache {Capacity: capacity} lruCache.Map = make (map [string] * Node Capacity) return & lruCache} func (l * LRUCache) get (key string) string {if v, ok: = l.Map [key] Ok {l.refreshNode (v) return v.Value} else {return "null"}} func (l * LRUCache) put (key, value string) {if v, ok: = l.Map [key] ! ok {if len (l.Map) > = l.Capacity {oldKey: = l.removeNode (head) delete (l.Map, oldKey)} node: = Node {Key: key Value: value} l.addNode (& node) l.Map [key] = & node} else {v.Value = value l.refreshNode (v)} func (l * LRUCache) refreshNode (node * Node) {if node = = end {return} l.removeNode (node) l.addNode (node)} func (l * LRUCache) removeNode (node * Node) string {if node = = end {end = end.pre } else if node = = head {head = head.next} else {node.pre.next = node.next node.next.pre = node.pre} return node.Key} func (l * LRUCache) addNode (node * Node) {if end! = nil {end.next = node node.pre = end node.next = nil} end = node if head = nil {head = node}} 3 Test using func Main () {lruCache: = GetLRUCache (3) lruCache.put ("001" "1") lruCache.put ("002", "2") lruCache.put ("003", "3") lruCache.put ("004", "4") lruCache.put ("005", "5") lruCache.get ("002") fmt.Println (lruCache.get ("002") fmt.Println (lruCache.get ("002")) fmt.Print (lruCache.Map)} finished reading this article I believe you have a certain understanding of "how to achieve LRU Cache in GE language". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.