logo

LRU、LFU算法的代码实现

作者
Modified on
Reading time
8 分钟阅读:..评论:..

以下是对LFU和LRU算法的详细解释，并使用Golang、Java和C/C++实现这两个缓存淘汰算法。

一、LRU（Least Recently Used）算法

解释： LRU算法淘汰最近最少使用的缓存数据。实现LRU算法的常见方法是使用双向链表和哈希表。双向链表用于维护缓存数据的使用顺序，哈希表用于快速查找缓存数据。

Golang实现LRU算法

package main

import (
    "container/list"
    "fmt"
)

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

type entry struct {
    key, value int
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value
    }
    return -1
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    if c.list.Len() == c.capacity {
        backElem := c.list.Back()
        if backElem != nil {
            delete(c.cache, backElem.Value.(*entry).key)
            c.list.Remove(backElem)
        }
    }

    newElem := c.list.PushFront(&entry{key, value})
    c.cache[key] = newElem
}

func main() {
    lru := NewLRUCache(2)
    lru.Put(1, 1)
    lru.Put(2, 2)
    fmt.Println(lru.Get(1)) // 1
    lru.Put(3, 3)
    fmt.Println(lru.Get(2)) // -1
    lru.Put(4, 4)
    fmt.Println(lru.Get(1)) // -1
    fmt.Println(lru.Get(3)) // 3
    fmt.Println(lru.Get(4)) // 4
}

Java实现LRU算法

import java.util.*;

public class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache;
    private final LinkedHashMap<Integer, Integer> lru;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.lru = new LinkedHashMap<>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        lru.get(key); // Update LRU order
        return cache.get(key);
    }

    public void put(int key, int value) {
        cache.put(key, value);
        lru.put(key, value);
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1)); // 1
        lru.put(3, 3);
        System.out.println(lru.get(2)); // -1
        lru.put(4, 4);
        System.out.println(lru.get(1)); // -1
        System.out.println(lru.get(3)); // 3
        System.out.println(lru.get(4)); // 4
    }
}

C++实现LRU算法

#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        list.splice(list.begin(), list, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            list.splice(list.begin(), list, it->second);
            it->second->second = value;
            return;
        }
        if (list.size() == capacity) {
            int lruKey = list.back().first;
            list.pop_back();
            cache.erase(lruKey);
        }
        list.emplace_front(key, value);
        cache[key] = list.begin();
    }

private:
    int capacity;
    std::list<std::pair<int, int>> list;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;
};

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    std::cout << lru.get(1) << std::endl; // 1
    lru.put(3, 3);
    std::cout << lru.get(2) << std::endl; // -1
    lru.put(4, 4);
    std::cout << lru.get(1) << std::endl; // -1
    std::cout << lru.get(3) << std::endl; // 3
    std::cout << lru.get(4) << std::endl; // 4
}

二、LFU（Least Frequently Used）算法

解释： LFU算法淘汰使用频率最低的缓存数据。实现LFU算法通常使用两个哈希表，一个用于存储缓存数据及其频率，另一个用于存储同一频率的数据链表。

Golang实现LFU算法

package main

import (
    "container/list"
    "fmt"
)

type LFUCache struct {
    capacity int
    minFreq  int
    cache    map[int]*list.Element
    freq     map[int]*list.List
}

type entry struct {
    key, value, freq int
}

func NewLFUCache(capacity int) *LFUCache {
    return &LFUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        freq:     make(map[int]*list.List),
    }
}

func (c *LFUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        c.increaseFreq(elem)
        return elem.Value.(*entry).value
    }
    return -1
}

func (c *LFUCache) Put(key, value int) {
    if c.capacity == 0 {
        return
    }

    if elem, ok := c.cache[key]; ok {
        elem.Value.(*entry).value = value
        c.increaseFreq(elem)
        return
    }

    if len(c.cache) >= c.capacity {
        c.removeMinFreq()
    }

    ent := &entry{key, value, 1}
    if c.freq[1] == nil {
        c.freq[1] = list.New()
    }
    elem := c.freq[1].PushFront(ent)
    c.cache[key] = elem
    c.minFreq = 1
}

func (c *LFUCache) increaseFreq(elem *list.Element) {
    ent := elem.Value.(*entry)
    freq := ent.freq
    c.freq[freq].Remove(elem)
    if c.freq[freq].Len() == 0 {
        delete(c.freq, freq)
        if c.minFreq == freq {
            c.minFreq++
        }
    }

    ent.freq++
    if c.freq[ent.freq] == nil {
        c.freq[ent.freq] = list.New()
    }
    newElem := c.freq[ent.freq].PushFront(ent)
    c.cache[ent.key] = newElem
}

func (c *LFUCache) removeMinFreq() {
    if c.freq[c.minFreq] == nil {
        return
    }
    elem := c.freq[c.minFreq].Back()
    c.freq[c.minFreq].Remove(elem)
    if c.freq[c.minFreq].Len() == 0 {
        delete(c.freq, c.minFreq)
    }
    delete(c.cache, elem.Value.(*entry).key)
}

func main() {
    lfu := NewLFUCache(2)
    lfu.Put(1, 1)
    lfu.Put(2, 2)
    fmt.Println(lfu.Get(1)) // 1
    lfu.Put(3, 3)
    fmt.Println(lfu.Get(2)) // -1
    lfu.Put(4, 4)
    fmt.Println(lfu.Get(1)) // -1
    fmt.Println(lfu.Get(3)) // 3
    fmt.Println(lfu.Get(4)) // 4
}

Java实现LFU算法

import java.util.*;

class LFUCache {
    private final int capacity;
    private int minFreq;
    private final Map<Integer, Integer> vals;
    private final Map<Integer, Integer> counts;
    private final Map<Integer, LinkedHashSet<Integer>> freq;

    public LFUCache(int capacity) {
        this

继续提供LFU算法的实现代码，并使用Golang、Java和C++。

Java实现LFU算法

import java.util.*;

class LFUCache {
    private final int capacity;
    private int minFreq;
    private final Map<Integer, Integer> vals;
    private final Map<Integer, Integer> counts;
    private final Map<Integer, LinkedHashSet<Integer>> freq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.vals = new HashMap<>();
        this.counts = new HashMap<>();
        this.freq = new HashMap<>();
        freq.put(1, new LinkedHashSet<>());
    }

    public int get(int key) {
        if (!vals.containsKey(key)) {
            return -1;
        }
        int count = counts.get(key);
        counts.put(key, count + 1);
        freq.get(count).remove(key);
        if (count == minFreq && freq.get(count).size() == 0) {
            minFreq++;
        }
        freq.computeIfAbsent(count + 1, k -> new LinkedHashSet<>()).add(key);
        return vals.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        if (vals.containsKey(key)) {
            vals.put(key, value);
            get(key);
            return;
        }
        if (vals.size() >= capacity) {
            int evict = freq.get(minFreq).iterator().next();
            freq.get(minFreq).remove(evict);
            vals.remove(evict);
            counts.remove(evict);
        }
        vals.put(key, value);
        counts.put(key, 1);
        minFreq = 1;
        freq.get(1).add(key);
    }

    public static void main(String[] args) {
        LFUCache lfu = new LFUCache(2);
        lfu.put(1, 1);
        lfu.put(2, 2);
        System.out.println(lfu.get(1)); // 1
        lfu.put(3, 3);
        System.out.println(lfu.get(2)); // -1
        lfu.put(4, 4);
        System.out.println(lfu.get(1)); // -1
        System.out.println(lfu.get(3)); // 3
        System.out.println(lfu.get(4)); // 4
    }
}

C++实现LFU算法

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <list>

class LFUCache {
public:
    LFUCache(int capacity) : capacity(capacity), minFreq(0) {}

    int get(int key) {
        if (vals.find(key) == vals.end()) return -1;
        int count = counts[key];
        counts[key]++;
        freq[count].erase(keys[key]);
        if (freq[count].empty()) {
            freq.erase(count);
            if (count == minFreq) minFreq++;
        }
        freq[count + 1].push_front(key);
        keys[key] = freq[count + 1].begin();
        return vals[key];
    }

    void put(int key, int value) {
        if (capacity <= 0) return;

        if (vals.find(key) != vals.end()) {
            vals[key] = value;
            get(key);
            return;
        }
        if (vals.size() >= capacity) {
            int evict = freq[minFreq].back();
            freq[minFreq].pop_back();
            if (freq[minFreq].empty()) {
                freq.erase(minFreq);
            }
            vals.erase(evict);
            counts.erase(evict);
            keys.erase(evict);
        }
        vals[key] = value;
        counts[key] = 1;
        minFreq = 1;
        freq[1].push_front(key);
        keys[key] = freq[1].begin();
    }

private:
    int capacity;
    int minFreq;
    std::unordered_map<int, int> vals;
    std::unordered_map<int, int> counts;
    std::unordered_map<int, std::list<int>> freq;
    std::unordered_map<int, std::list<int>::iterator> keys;
};

int main() {
    LFUCache lfu(2);
    lfu.put(1, 1);
    lfu.put(2, 2);
    std::cout << lfu.get(1) << std::endl; // 1
    lfu.put(3, 3);
    std::cout << lfu.get(2) << std::endl; // -1
    lfu.put(4, 4);
    std::cout << lfu.get(1) << std::endl; // -1
    std::cout << lfu.get(3) << std::endl; // 3
    std::cout << lfu.get(4) << std::endl; // 4
}

以上代码展示了如何使用Golang、Java和C++实现LRU（Least Recently Used）和LFU（Least Frequently Used）算法。每种语言的实现都包括了创建缓存、插入数据、获取数据以及删除数据的操作。这些实现展示了如何利用数据结构和算法来管理缓存，并确保缓存的高效性和一致性。当然可以，以下是LFU（Least Frequently Used）算法和LRU（Least Recently Used）算法的优劣对比：

LRU（Least Recently Used）算法

优点：

  1. 简单性：LRU的实现和理解相对简单。通常使用双向链表和哈希表的组合来管理缓存。
  2. 时间局部性：LRU算法基于时间局部性原理，最近使用的数据很可能在不久的将来会再次被使用。
  3. 快速操作：插入、删除和查找操作的时间复杂度为O(1)。

缺点：

  1. 不考虑频率：LRU仅考虑最近的访问时间，而不考虑数据访问的频率。如果一些数据被频繁访问但由于时间间隔较大，可能会被淘汰。
  2. 空间开销：需要维护双向链表和哈希表，消耗一定的内存空间。

LFU（Least Frequently Used）算法

优点：

  1. 频率考虑：LFU算法基于访问频率，频繁访问的数据更不容易被淘汰，适用于某些特定场景，如热点数据较少变化的情况。
  2. 适应性强：在某些情况下，LFU算法能更好地保持热点数据，提升命中率。

缺点：

  1. 实现复杂：LFU的实现比LRU复杂得多，需要维护多个数据结构，如哈希表和频率链表。
  2. 冷启动问题：新加入的数据由于访问频率较低，容易被迅速淘汰，无法快速适应新的热点数据。
  3. 时间复杂度：插入和删除操作的时间复杂度相对较高，尤其在高并发环境中性能可能不如LRU。

使用场景

  • LRU适用场景：
    • 数据访问具有强时间局部性，即最近使用的数据很可能会被再次使用。
    • 需要快速的插入、删除和查找操作。
    • 实现简单，适合一般缓存需求。
  • LFU适用场景：
    • 数据访问具有强频率局部性，即被频繁访问的数据更有可能被再次访问。
    • 热点数据较少变化，且频率分布较为稳定。
    • 需要更高的缓存命中率，且能够接受实现复杂度较高的情况。

总结

  • LRU（Least Recently Used）：适用于大多数通用缓存场景，简单高效，能够很好地处理具有时间局部性的访问模式。
  • LFU（Least Frequently Used）：适用于访问频率分布稳定的缓存场景，能更好地保持热点数据，但实现复杂且在动态访问模式下可能表现不佳。

选择算法时应根据具体的应用场景和需求来权衡，确保选择最合适的缓存淘汰策略。

< Redis源码阅读笔记
怎么在Redis中实现一个高效的排行榜列表？ >