如何利用Go語言實(shí)現(xiàn)LRU?Cache
1 基本概念
LRU是一個(gè)老生常談的問題,即最近最少使用,LRU是Least Recently Used
的縮寫,是一種操作系統(tǒng)中常用的頁面置換算法,選擇最近最久未使用的頁面予以淘汰。該算法賦予每個(gè)頁面一個(gè)訪問字段,用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間 t,當(dāng)須淘汰一個(gè)頁面時(shí),選擇現(xiàn)有頁面中其 t 值最大的,即最近最少使用的頁面予以淘汰。
實(shí)現(xiàn)LRU基本的數(shù)據(jù)結(jié)構(gòu):Map+LinkedList
一般規(guī)則:
- 添加數(shù)據(jù)時(shí),將新增數(shù)據(jù)節(jié)點(diǎn)放在頭指針,尾結(jié)點(diǎn)部分大于最大長度時(shí)刪除。
- 刪除數(shù)據(jù)時(shí),先按照Map的規(guī)則進(jìn)行查找,再根據(jù)鏈表規(guī)則進(jìn)行刪除。
- 查找數(shù)據(jù)時(shí),按照
Map
進(jìn)行查找,沒有則返回空,有則返回該數(shù)據(jù)的值并移動(dòng)到頭節(jié)點(diǎn)。
2 代碼實(shí)現(xiàn)
package main import "fmt" var head *Node var end *Node type 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 ? ? ? ? ? ? ?//頁面初始化大小 ? ?Size ? ? int ? ? ? ? ? ? ?//頁面實(shí)際大小 ? ?Map ? ? ?map[string]*Node //具體的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 測(cè)試使用
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("001")) ? ?fmt.Println(lruCache.get("002")) ? ?fmt.Print(lruCache.Map) }
到此這篇關(guān)于如何利用Go語言實(shí)現(xiàn)LRU Cache的文章就介紹到這了,更多相關(guān)Go實(shí)現(xiàn)LRU Cache內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
在Go中實(shí)現(xiàn)高效可靠的鏈路追蹤系統(tǒng)
在當(dāng)今互聯(lián)網(wǎng)應(yīng)用的架構(gòu)中,分布式系統(tǒng)已經(jīng)成為主流,分布式系統(tǒng)的優(yōu)勢(shì)在于能夠提供高可用性、高并發(fā)性和可擴(kuò)展性,本文將介紹鏈路追蹤的概念和原理,并重點(diǎn)介紹如何在Golang中實(shí)現(xiàn)高效可靠的鏈路追蹤系統(tǒng),需要的朋友可以參考下2023-10-10go日志系統(tǒng)logrus顯示文件和行號(hào)的操作
這篇文章主要介紹了go日志系統(tǒng)logrus顯示文件和行號(hào)的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-11-11Go Web 編程中的模板庫應(yīng)用指南(超詳細(xì))
這篇文章主要介紹了Go Web 編程中的模板庫應(yīng)用指南,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03golang調(diào)用shell命令(實(shí)時(shí)輸出,終止)
本文主要介紹了golang調(diào)用shell命令(實(shí)時(shí)輸出,終止),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02K8s部署發(fā)布Golang應(yīng)用程序的實(shí)現(xiàn)方法
本文主要介紹了K8s部署發(fā)布Golang應(yīng)用程序的實(shí)現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07基于Golang實(shí)現(xiàn)Excel表格的導(dǎo)入導(dǎo)出功能
最近項(xiàng)目開發(fā)中有涉及到Excel的導(dǎo)入與導(dǎo)出功能,特別是導(dǎo)出表格時(shí)需要特定的格式,所以本文給大家介紹了基于Golang實(shí)現(xiàn)Excel表格的導(dǎo)入導(dǎo)出功能,文中通過代碼示例和圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12Go語言中init函數(shù)特點(diǎn)、用途和注意事項(xiàng)詳解
go語言中有一個(gè)非常神奇的函數(shù)init,它可以在所有程序執(zhí)行開始前被執(zhí)行,并且每個(gè)package下面可以存在多個(gè)init函數(shù),這篇文章主要給大家介紹了關(guān)于Go語言中init函數(shù)特點(diǎn)、用途和注意事項(xiàng)的相關(guān)資料,需要的朋友可以參考下2023-07-07