LRU和LFU 缓存淘汰算法（javascript与go语言实现）-六虎

介绍

LRU（Least Recently Used）和LFU（Least Frequently Used）是两种常见的缓存筛选算法，用于在缓存空间有限的情况下挑选合适的缓存目标进行筛选，以提高缓存的利用功率。

LRU算法依据”最近最少运用”的准则进行筛选。它保护一个缓存的拜访次序链表，当有新的数据被拜访时，假如数据已经在缓存中，则将其移到链表头部；假如数据不在缓存中，则将其增加到链表头部。当需求筛选数据时，挑选链表尾部的数据进行筛选，因为尾部的数据是最近最少被拜访的数据。

LFU算法依据”最不常常运用”的准则进行筛选。它保护一个缓存目标的拜访频次，对于每个拜访到的目标，增加其拜访频次。当需求筛选数据时，挑选拜访频次最低的数据进行筛选。

LRU和LFU算法都有各自的优势和适用场景：

LRU算法适用于拜访具有时间局部性的数据，即最近被拜访的数据或许在将来一段时间内仍然会被拜访。LRU算法相对较简单，简单完成，适用于大多数场景。但是，当存在”热门数据”（被频繁拜访的数据）时，LRU算法或许无法有效地保证缓存的命中率。
LFU算法适用于拜访具有拜访频次局部性的数据，即拜访频次高的数据很或许在将来一段时间内仍然会被频繁拜访。LFU算法需求保护每个目标的拜访频次计数，相对于LRU算法来说更加复杂。LFU算法在面临热门数据的场景下表现较好，但在某些场景下或许存在”频次突变”的问题，即频次高的数据忽然不再被拜访，但因为频次计数较高而长期无法被筛选。

在实践运用中，我们能够依据具体的场景和需求挑选合适的缓存筛选战略，或者结合两种算法进行混合运用，以达到更好的缓存性能。

146. LRU 缓存中等

下面用javascript代码演示一下LRU缓存：

// 最近最少运用
// 界说LRU缓存类
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }
    get (key) {
        if (this.cache.has(key)) {
            const value = this.cache.get(key);
            this.cache.delete(key); // 删去key在Map中的位置
            this.cache.set(key, value); // 重新设置key对在Map的最终（最近运用,也便是设置为最新的）
            return value;
        }
        return -1;
    }
    put (key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key); // 删去key在Map中的位置
        } else if (this.cache.size >= this.capacity) {
            // 缓存容量不够了
            const oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey); // 删去最旧的key
        }
        this.cache.set(key, value);
    }
}
// 示例用法
const cache = new LRUCache(2); // 创立容量为2的LRU缓存
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 输出 1
cache.put(3, 3);
console.log(cache.get(2)); // 输出 -1
console.log(cache.get(3)); // 输出 3
cache.put(4, 4);
console.log(cache.get(1)); // 输出 -1
console.log(cache.get(3)); // 输出 3
console.log(cache.get(4)); // 输出 4

这段代码的技巧就在于运用了ES6的Map和迭代器的功用。Map 的遍历次序便是刺进次序，运用Map.prototype.keys()：回来键名的遍历器。然后我们运用迭代器的 next() 方法获取数据结构的第一个成员,也便是最旧的。然后通过 value 特点来获取它的值。拿到最旧的key就能够删去它，最终重新设置key。（Map具有LRU特性）

460. LFU 缓存困难

javascript代码完成LFU：

// 最不常常运用
// 最不常常运用
class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        // 每个拜访次数都对应存储一个 Set，里边包括 cache 里边的 Map 的 key
        this.frequency = new Map();
        this.minFrequency = 0;
    }
    get(key) {
        if (this.cache.has(key)) {
            const { value, freq } = this.cache.get(key);
            this.updateFrequency(key, freq); // 更新拜访次数
            return value;
        }
        return -1;
    }
    put(key, value) {
        if (this.capacity === 0) return;
        if (this.cache.has(key)) {
            const { freq } = this.cache.get(key); // 获取当时元素旧的拜访次数
            this.cache.set(key, { value, freq }); // 更新当时 key 对应的元素
            this.updateFrequency(key, freq); // 更新当时的拜访次数
        } else {
            if (this.cache.size >= this.capacity) {
                // 获取拜访次数最少的 key 组成的 Set
                const leastFreq = this.frequency.get(this.minFrequency);
                // 依据 Set 的 LRU 特性，回来最久未被拜访的元素（假如拜访次数最少的元素有多个，最久未被拜访的元素会被删去）
                const deleteKey = leastFreq.keys().next().value;
                leastFreq.delete(deleteKey);
                this.cache.delete(deleteKey);
            }
            // 新增加元素时设置元素的拜访次数为 1
            this.cache.set(key,{value,freq: 1});
            if (!this.frequency.has(1)) {
                // 新增加元素时，假如不存在拜访次数为1对应的 Set,设置拜访次数为 1 的 Set 为空
                this.frequency.set(1,new Set())
            }
            // 设置拜访次数为1的 Set 中增加当时的key
            this.frequency.get(1).add(key);
            this.minFrequency = 1; // 新增加元素时最小拜访次数更新为 1
        }
    }
    updateFrequency(key, freq) {
        // 从当时拜访次数 freq 对应的 Set中，删去当时的 key
        const freqList = this.frequency.get(freq);
        freqList.delete(key);
        // 当时元素旧的拜访次数等于最小拜访次数而且当时拜访次数 freq 组成的 Set 为空
        //（元素旧的拜访次数等于最小拜访次数，而且最小拜访次数对应的 Set 为空的情况）
        // 假如某个元素它之前的拜访次数为最小拜访次数，而且没有其他元素与该元素的拜访次数相同
        if (freq === this.minFrequency && freqList.size === 0) {
            this.minFrequency++;  // 更新最小拜访次数
        }
        if (!this.frequency.has(freq + 1)) {
            this.frequency.set(freq + 1, new Set());
        }
        // 在更新后的拜访次数对应的 Set 里边增加当时元素对应的 key
        this.frequency.get(freq + 1).add(key);
        this.cache.get(key).freq = freq + 1; // 更新当时元素的拜访次数 + 1
    }
}
// 示例用法
const cache = new LFUCache(2); // 创立容量为2的LFU缓存
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 输出 1
cache.put(3, 3); // 删去 1
console.log(cache.get(2)); // 输出 2
console.log(cache.get(3)); // 输出 3
cache.put(4, 4); // 删去 2
console.log(cache.get(2)); // 输出 -1
console.log(cache.get(3)); // 输出 3
console.log(cache.get(4)); // 输出 4

相同这儿运用了 Set 数据结构的 LRU 特性，在 frequency 对应的 Map 里边放在着每种拜访次数对应的 key 组成的 Set。也便是说，拜访次数相同的元素所对应的 key 存放在同一个 Set 中。这儿要注意的便是新增元素时，设置拜访次数为1的 Set为空,而且增加拜访该元素的 key，一起设置最小拜访次数为1。假如某个元素它之前的拜访次数为最小拜访次数，而且没有其他元素与该元素的拜访次数相同，一起更新最小拜访次数和该元素的拜访次数，也便是该元素的拜访次数 + 1，而且设置对应的 Set 数据结构为空，把当时拜访的 key 增加进去。

go代码演示LRU缓存：

package main
import "fmt"
// LRUCache 最近最少运用
type LRUCache struct {
	size       int
	capacity   int
	cache      map[int]*DoubleLinkNode
	head, tail *DoubleLinkNode
}
// DoubleLinkNode 双向链表
type DoubleLinkNode struct {
	key, value int
	prev, next *DoubleLinkNode
}
// 初始化双向链表
func initDoubleLinkNode(key, value int) *DoubleLinkNode {
	return &DoubleLinkNode{
		key:   key,
		value: value,
	}
}
// Constructor 初始化LRU缓存
func Constructor(capacity int) LRUCache {
	l := LRUCache{
		capacity: capacity,
		cache:    map[int]*DoubleLinkNode{},
		head:     initDoubleLinkNode(0, 0),
		tail:     initDoubleLinkNode(0, 0),
	}
	l.head.next = l.tail
	l.tail.prev = l.head
	return l
}
func (l *LRUCache) Get(key int) int {
	if _, ok := l.cache[key]; !ok {
		return -1
	}
	node := l.cache[key]
	l.moveToHead(node)
	return node.value
}
func (l *LRUCache) Put(key, value int) {
	// 新增元素 放在链表头部
	if _, ok := l.cache[key]; !ok {
		node := initDoubleLinkNode(key, value)
		l.cache[key] = node
		l.addToHead(node)
		l.size++
		// 超出容量 删去最终一个元素
		if l.size > l.capacity {
			removed := l.removeTail()
			delete(l.cache, removed.key)
			l.size--
		}
	} else {
		// 更新元素 放在链表头部
		node := l.cache[key]
		node.value = value
		l.moveToHead(node)
	}
}
func (l *LRUCache) addToHead(node *DoubleLinkNode) {
	node.prev = l.head
	node.next = l.head.next
	l.head.next.prev = node
	l.head.next = node
}
func (l *LRUCache) removeNode(node *DoubleLinkNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}
func (l *LRUCache) moveToHead(node *DoubleLinkNode) {
	l.removeNode(node)
	l.addToHead(node)
}
func (l *LRUCache) removeTail() *DoubleLinkNode {
	node := l.tail.prev
	l.removeNode(node)
	return node
}
func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1)) //删去2 输出 1
	cache.Put(3, 3)
	fmt.Println(cache.Get(2)) // 输出 -1
	cache.Put(4, 4) // 删去 1
	fmt.Println(cache.Get(1)) // 输出 -1
	fmt.Println(cache.Get(3)) // 输出 3
	fmt.Println(cache.Get(4)) // 输出 4
}

代码运用了双向链表 + map完成了LRU数据结构。代码中采用了首尾虚拟节点，拜访到的节点移动到头部，超出容量时删去尾部的节点。

go代码完成LFU数据结构：

package main
import "fmt"
// LFUCache 最不常常运用
type LFUCache struct {
	size     int // 大小
	capacity int // 容量
	minFreq  int // 最小拜访次数
	cache    map[int]*Node
	freq     map[int]*DLinkedList
}
type Node struct {
	key        int
	value      int
	freq       int // 拜访次数
	prev, next *Node
}
// DLinkedList 拜访次数为n的元素组成的双向链表（LRU特性）
type DLinkedList struct {
	head, tail *Node
}
func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		freq:     make(map[int]*DLinkedList),
	}
}
func InitDLinkedList() *DLinkedList {
	head, tail := &Node{}, &Node{}
	head.next = tail
	tail.prev = head
	return &DLinkedList{
		head: head,
		tail: tail,
	}
}
func (d *DLinkedList) AddToHead(node *Node) {
	node.prev = d.head
	node.next = d.head.next
	d.head.next.prev = node
	d.head.next = node
}
func (d *DLinkedList) Remove(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
	node.prev = nil
	node.next = nil
}
func (d *DLinkedList) RemoveTail() *Node {
	// 空链表
	if d.IsEmpty() {
		return nil
	}
	last := d.tail.prev
	d.Remove(last)
	return last
}
func (d *DLinkedList) IsEmpty() bool {
	return d.head.next == d.tail
}
func (l *LFUCache) Get(key int) int {
	if node, ok := l.cache[key]; ok {
		l.addFreq(node)
		return node.value
	}
	return -1
}
func (l *LFUCache) Put(key, value int) {
	if l.capacity == 0 {
		return
	}
	// 更新
	if node, ok := l.cache[key]; ok {
		node.value = value
		l.addFreq(node)
	} else {
		// 超出容量，删去拜访次数最低的对应数据链表的最旧的元素
		if l.size >= l.capacity {
			node := l.freq[l.minFreq].RemoveTail()
			delete(l.cache, node.key)
			l.size--
		}
		node := &Node{key: key, value: value, freq: 1}
		l.cache[key] = node // 贮存新节点
		if l.freq[1] == nil {
			l.freq[1] = InitDLinkedList()
		}
		l.freq[1].AddToHead(node)
		l.minFreq = 1
		l.size++
	}
}
func (l *LFUCache) addFreq(node *Node) {
	n := node.freq
	l.freq[n].Remove(node)
	if l.minFreq == n && l.freq[n].IsEmpty() {
		l.minFreq++
		delete(l.freq, n)
	}
	node.freq++
	if l.freq[node.freq] == nil {
		l.freq[node.freq] = InitDLinkedList()
	}
	l.freq[node.freq].AddToHead(node)
}
func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1)) // 1
	cache.Put(3, 3)           // 删去2
	fmt.Println(cache.Get(2)) // -1
	fmt.Println(cache.Get(3)) // 3
	cache.Put(4, 4) // key2被筛选
	fmt.Println(cache.Get(1)) // -1
	fmt.Println(cache.Get(3)) // 3
	fmt.Println(cache.Get(4)) // 4
}

cache存储对应的数据节点，但是或许会出现节点拜访次数相同的情况。对应拜访次数相同的节点，我们把放在一个双向链表中，然后依据LRU最近最少运用，超越容量的时候删去双向链表尾部的节点。拿到节点的key,之后就能从map中删去贮存的节点了。

LRU和LFU 缓存淘汰算法（javascript与go语言实现）

介绍

相关文章

「NIO源码」JavaNIO源码 & JNI分析一：linux API介绍

一次api升级引发的“血案”

探索BottomSheet的背后秘密

部署机器学习模型必须考虑的5个要素；用Python快速写web应用的框架；神经网络可视化；3D医学图像分割工具包；前沿论文 | ShowMeAI资讯日报

作者信息