LRU緩存替換策略及C#實現(xiàn)方法分享

更新時間：2023年04月21日 08:36:51 作者：黑洞視界

LRU（Least Recently Used）緩存替換策略是一種常用的緩存管理策略，它根據(jù)數(shù)據(jù)最近被訪問的時間來決定哪些數(shù)據(jù)應(yīng)該被保留在緩存中。本文將介紹LRU緩存替換策略的原理和C#實現(xiàn)方法。

LRU緩存替換策略

緩存是一種非常常見的設(shè)計，通過將數(shù)據(jù)緩存到訪問速度更快的存儲設(shè)備中，來提高數(shù)據(jù)的訪問速度，如內(nèi)存、CPU緩存、硬盤緩存等。

但與緩存的高速相對的是，緩存的成本較高，因此容量往往是有限的，當(dāng)緩存滿了之后，就需要一種策略來決定將哪些數(shù)據(jù)移除出緩存，以騰出空間來存儲新的數(shù)據(jù)。

這樣的策略被稱為緩存替換策略（Cache Replacement Policy）。

常見的緩存替換策略有：FIFO（First In First Out）、LRU（Least Recently Used）、LFU（Least Frequently Used）等。

今天給大家介紹的是LRU算法。

核心思想

LRU算法基于這樣一個假設(shè)：如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高。

大部分情況下這個假設(shè)是成立的，因此LRU算法也是比較常用的緩存替換策略。

基于這個假設(shè)，我們在實現(xiàn)的時候，需要維護一個有序的數(shù)據(jù)結(jié)構(gòu)，來記錄數(shù)據(jù)的訪問歷史，當(dāng)緩存滿了之后，就可以根據(jù)這個數(shù)據(jù)結(jié)構(gòu)來決定將哪些數(shù)據(jù)移除出緩存。

不適用場景

但如果數(shù)據(jù)的訪問模式不符合LRU算法的假設(shè)，那么LRU算法就會失效。

例如：數(shù)據(jù)的訪問模式是周期性的，那么LRU算法就會把周期性的數(shù)據(jù)淘汰掉，這樣就會導(dǎo)致緩存命中率的下降。

換個說法比如，如果現(xiàn)在緩存的數(shù)據(jù)只在白天被訪問，晚上訪問的是另一批數(shù)據(jù)，那么在晚上，LRU算法就會把白天訪問的數(shù)據(jù)淘汰掉，第二天白天又會把昨天晚上訪問的數(shù)據(jù)淘汰掉，這樣就會導(dǎo)致緩存命中率的下降。

后面有時間會給大家介紹LFU（Least Frequently Used）算法，以及LFU和LRU的結(jié)合LFRU（Least Frequently and Recently Used）算法，可以有效的解決這個問題。

算法基本實現(xiàn)

上文提到，LRU算法需要維護一個有序的數(shù)據(jù)結(jié)構(gòu)，來記錄數(shù)據(jù)的訪問歷史。通常我們會用雙向鏈表來實現(xiàn)這個數(shù)據(jù)結(jié)構(gòu)，因為雙向鏈表可以在O(1)的時間復(fù)雜度內(nèi)往鏈表的頭部或者尾部插入數(shù)據(jù)，以及在O(1)的時間復(fù)雜度內(nèi)刪除數(shù)據(jù)。

我們將數(shù)據(jù)存儲在雙向鏈表中，每次訪問數(shù)據(jù)的時候，就將數(shù)據(jù)移動到鏈表的尾部，這樣就可以保證鏈表的尾部就是最近訪問的數(shù)據(jù)，鏈表的頭部就是最久沒有被訪問的數(shù)據(jù)。

當(dāng)緩存滿了之后，如果需要插入新的數(shù)據(jù)，因為鏈表的頭部就是最久沒有被訪問的數(shù)據(jù)，所以我們就可以直接將鏈表的頭部刪除，然后將新的數(shù)據(jù)插入到鏈表的尾部。

如果我們要實現(xiàn)一個鍵值對的緩存，我們可以用一個哈希表來存儲鍵值對，這樣就可以在O(1)的時間復(fù)雜度內(nèi)完成查找操作，.NET 中我們可以使用 Dictionary。

同時我們使用 LinkedList 來作為雙向鏈表的實現(xiàn)，存儲緩存的 key，以此記錄數(shù)據(jù)的訪問歷史。

我們在每次操作 Dictionary 進行插入、刪除、查找的時候，都需要將對應(yīng)的 key 也插入、刪除、移動到鏈表的尾部。

// 實現(xiàn) IEnumerable 接口，方便遍歷
public class LRUCache<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private readonly LinkedList<TKey> _list;

    private readonly Dictionary<TKey, TValue> _dictionary;

    private readonly int _capacity;
    
    public LRUCache(int capacity)
    {
        _capacity = capacity;
        _list = new LinkedList<TKey>();
        _dictionary = new Dictionary<TKey, TValue>();
    }

    public TValue Get(TKey key)
    {
        if (_dictionary.TryGetValue(key, out var value))
        {
            // 在鏈表中刪除 key，然后將 key 添加到鏈表的尾部
            // 這樣就可以保證鏈表的尾部就是最近訪問的數(shù)據(jù)，鏈表的頭部就是最久沒有被訪問的數(shù)據(jù)
            // 但是在鏈表中刪除 key 的時間復(fù)雜度是 O(n)，所以這個算法的時間復(fù)雜度是 O(n)
            _list.Remove(key);
            _list.AddLast(key);
            return value;
        }

        return default;
    }

    public void Put(TKey key, TValue value)
    {
        if (_dictionary.TryGetValue(key, out _))
        {
            // 如果插入的 key 已經(jīng)存在，將 key 對應(yīng)的值更新，然后將 key 移動到鏈表的尾部
            _dictionary[key] = value;
            _list.Remove(key);
            _list.AddLast(key);
        }
        else
        {          
            if (_list.Count == _capacity)
            {
                // 緩存滿了，刪除鏈表的頭部，也就是最久沒有被訪問的數(shù)據(jù)
                _dictionary.Remove(_list.First.Value);
                _list.RemoveFirst();
            }

            _list.AddLast(key);
            _dictionary.Add(key, value);
        }
    }

    public void Remove(TKey key)
    {
        if (_dictionary.TryGetValue(key, out _))
        {
            _dictionary.Remove(key);
            _list.Remove(key);
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (var key in _list)
        {
            yield return new KeyValuePair<TKey, TValue>(key, _dictionary[key]);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

var lruCache = new LRUCache<int, int>(4);

lruCache.Put(1, 1);
lruCache.Put(2, 2);
lruCache.Put(3, 3);
lruCache.Put(4, 4);

Console.WriteLine(string.Join(" ", lruCache));
Console.WriteLine(lruCache.Get(2));
Console.WriteLine(string.Join(" ", lruCache));
lruCache.Put(5, 5);
Console.WriteLine(string.Join(" ", lruCache));
lruCache.Remove(3);
Console.WriteLine(string.Join(" ", lruCache));

輸出：

[1, 1] [2, 2] [3, 3] [4, 4] // 初始化
2                           // 訪問 2
[1, 1] [3, 3] [4, 4] [2, 2] // 2 移動到鏈表尾部
[3, 3] [4, 4] [2, 2] [5, 5] // 插入 5
[4, 4] [2, 2] [5, 5]        // 刪除 3

算法優(yōu)化

上面的實現(xiàn)中，對緩存的查詢、插入、刪除都會涉及到鏈表中數(shù)據(jù)的刪除（移動也是刪除再插入）。

因為我們在 LinkedList 中存儲的是 key，所以我們需要先通過 key 在鏈表中找到對應(yīng)的節(jié)點，然后再進行刪除操作，這就導(dǎo)致了鏈表的刪除操作的時間復(fù)雜度是 O(n)。

雖然 Dictionary 的查找、插入、刪除操作的時間復(fù)雜度都是 O(1)，但因為鏈表操作的時間復(fù)雜度是 O(n)，整個算法的最差時間復(fù)雜度是 O(n)。

算法優(yōu)化的關(guān)鍵在于如何降低鏈表的刪除操作的時間復(fù)雜度。

優(yōu)化思路：

在 Dictionary 中存儲 key 和 LinkedList 中節(jié)點的映射關(guān)系在 LinkedList 的節(jié)點中存儲 key-value

也就是說，我們讓兩個本來不相關(guān)的數(shù)據(jù)結(jié)構(gòu)之間產(chǎn)生聯(lián)系。

不管是在插入、刪除、查找緩存的時候，都可以通過這種聯(lián)系來將時間復(fù)雜度降低到 O(1)。

通過 key 在 Dictionary 中找到對應(yīng)的節(jié)點，然后再從 LinkedList 節(jié)點中取出 value，時間復(fù)雜度是 O(1) LinkedList 刪除數(shù)據(jù)之前，先通過 key 在 Dictionary 中找到對應(yīng)的節(jié)點，然后再刪除，這樣就可以將鏈表的刪除操作的時間復(fù)雜度降低到 O(1) LinkedList 刪除頭部節(jié)點時，因為節(jié)點中存儲了 key，所以我們可以通過 key 在 Dictionary 中刪除對應(yīng)的節(jié)點，時間復(fù)雜度是 O(1)

public class LRUCache_V2<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private readonly LinkedList<KeyValuePair<TKey, TValue>> _list;
    
    private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _dictionary;
    
    private readonly int _capacity;
    
    public LRUCache_V2(int capacity)
    {
        _capacity = capacity;
        _list = new LinkedList<KeyValuePair<TKey, TValue>>();
        _dictionary = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
    }
    
    public TValue Get(TKey key)
    {
        if (_dictionary.TryGetValue(key, out var node))
        {
            _list.Remove(node);
            _list.AddLast(node);
            return node.Value.Value;
        }
        
        return default;
    }
    
    public void Put(TKey key, TValue value)
    {
        if (_dictionary.TryGetValue(key, out var node))
        {
            node.Value = new KeyValuePair<TKey, TValue>(key, value);
            _list.Remove(node);
            _list.AddLast(node);
        }
        else
        {
            if (_list.Count == _capacity)
            {
                _dictionary.Remove(_list.First.Value.Key);
                _list.RemoveFirst();
            }
            
            var newNode = new LinkedListNode<KeyValuePair<TKey, TValue>>(new KeyValuePair<TKey, TValue>(key, value));
            _list.AddLast(newNode);
            _dictionary.Add(key, newNode);
        }
    }
    
    public void Remove(TKey key)
    {
        if (_dictionary.TryGetValue(key, out var node))
        {
            _dictionary.Remove(key);
            _list.Remove(node);
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return _list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

進一步優(yōu)化

因為我們對雙向鏈表的存儲需求是定制化的，要求節(jié)點中存儲 key-value，直接使用 C# 的 LinkedList 我們就需要用 KeyValuePair 這樣的結(jié)構(gòu)來間接存儲，會導(dǎo)致一些不必要的內(nèi)存開銷。

我們可以自己實現(xiàn)一個雙向鏈表，這樣就可以直接在節(jié)點中存儲 key-value，從而減少內(nèi)存開銷。

public class LRUCache_V3<TKey, TValue>
{
    private readonly DoubleLinkedListNode<TKey, TValue> _head;

    private readonly DoubleLinkedListNode<TKey, TValue> _tail;

    private readonly Dictionary<TKey, DoubleLinkedListNode<TKey, TValue>> _dictionary;

    private readonly int _capacity;

    public LRUCache_V3(int capacity)
    {
        _capacity = capacity;
        _head = new DoubleLinkedListNode<TKey, TValue>();
        _tail = new DoubleLinkedListNode<TKey, TValue>();
        _head.Next = _tail;
        _tail.Previous = _head;
        _dictionary = new Dictionary<TKey, DoubleLinkedListNode<TKey, TValue>>();
    }

    public TValue Get(TKey key)
    {
        if (_dictionary.TryGetValue(key, out var node))
        {
            RemoveNode(node);
            AddLastNode(node);
            return node.Value;
        }

        return default;
    }

    public void Put(TKey key, TValue value)
    {
        if (_dictionary.TryGetValue(key, out var node))
        {
            RemoveNode(node);
            AddLastNode(node);
            node.Value = value;
        }
        else
        {
            if (_dictionary.Count == _capacity)
            {
                var firstNode = RemoveFirstNode();

                _dictionary.Remove(firstNode.Key);
            }

            var newNode = new DoubleLinkedListNode<TKey, TValue>(key, value);
            AddLastNode(newNode);
            _dictionary.Add(key, newNode);
        }
    }

    public void Remove(TKey key)
    {
        if (_dictionary.TryGetValue(key, out var node))
        {
            _dictionary.Remove(key);
            RemoveNode(node);
        }
    }

    private void AddLastNode(DoubleLinkedListNode<TKey, TValue> node)
    {
        node.Previous = _tail.Previous;
        node.Next = _tail;
        _tail.Previous.Next = node;
        _tail.Previous = node;
    }

    private DoubleLinkedListNode<TKey, TValue> RemoveFirstNode()
    {
        var firstNode = _head.Next;
        _head.Next = firstNode.Next;
        firstNode.Next.Previous = _head;
        firstNode.Next = null;
        firstNode.Previous = null;
        return firstNode;
    }

    private void RemoveNode(DoubleLinkedListNode<TKey, TValue> node)
    {
        node.Previous.Next = node.Next;
        node.Next.Previous = node.Previous;
        node.Next = null;
        node.Previous = null;
    }
    
    internal class DoubleLinkedListNode<TKey, TValue>
    {    
        public DoubleLinkedListNode()
        {
        }

        public DoubleLinkedListNode(TKey key, TValue value)
        {
            Key = key;
            Value = value;
        }

        public TKey Key { get; set; }
        
        public TValue Value { get; set; }

        public DoubleLinkedListNode<TKey, TValue> Previous { get; set; }

        public DoubleLinkedListNode<TKey, TValue> Next { get; set; }
    }
}

Benchmark

使用 BenchmarkDotNet 對3個版本進行性能測試對比。

[MemoryDiagnoser]
public class WriteBenchmarks
{
    // 保證寫入的數(shù)據(jù)有一定的重復(fù)性，借此來測試LRU的最差時間復(fù)雜度
    private const int Capacity = 1000;
    private const int DataSize = 10_0000;
    
    private List<int> _data;

    [GlobalSetup]
    public void Setup()
    {
        _data = new List<int>();
        var shared = Random.Shared;
        for (int i = 0; i < DataSize; i++)
        {
            _data.Add(shared.Next(0, DataSize / 10));
        }
    }
    
    [Benchmark]
    public void LRUCache_V1()
    {
        var cache = new LRUCache<int, int>(Capacity);
        foreach (var item in _data)
        {
            cache.Put(item, item);
        }
    }
    
    [Benchmark]
    public void LRUCache_V2()
    {
        var cache = new LRUCache_V2<int, int>(Capacity);
        foreach (var item in _data)
        {
            cache.Put(item, item);
        }
    }
    
    [Benchmark]
    public void LRUCache_V3()
    {
        var cache = new LRUCache_V3<int, int>(Capacity);
        foreach (var item in _data)
        {
            cache.Put(item, item);
        }
    }
}

public class ReadBenchmarks
{
    // 保證寫入的數(shù)據(jù)有一定的重復(fù)性，借此來測試LRU的最差時間復(fù)雜度
    private const int Capacity = 1000;
    private const int DataSize = 10_0000;
    
    private List<int> _data;
    private LRUCache<int, int> _cacheV1;
    private LRUCache_V2<int, int> _cacheV2;
    private LRUCache_V3<int, int> _cacheV3;

    [GlobalSetup]
    public void Setup()
    {
        _cacheV1 = new LRUCache<int, int>(Capacity);
        _cacheV2 = new LRUCache_V2<int, int>(Capacity);
        _cacheV3 = new LRUCache_V3<int, int>(Capacity);
        _data = new List<int>();
        var shared = Random.Shared;
        for (int i = 0; i < DataSize; i++)
        {
            int dataToPut  = shared.Next(0, DataSize / 10);
            int dataToGet = shared.Next(0, DataSize / 10);
            _data.Add(dataToGet);
            _cacheV1.Put(dataToPut, dataToPut);
            _cacheV2.Put(dataToPut, dataToPut);
            _cacheV3.Put(dataToPut, dataToPut);
        }
    }
    
    [Benchmark]
    public void LRUCache_V1()
    {
        foreach (var item in _data)
        {
            _cacheV1.Get(item);
        }
    }
    
    [Benchmark]
    public void LRUCache_V2()
    {
        foreach (var item in _data)
        {
            _cacheV2.Get(item);
        }
    }
    
    [Benchmark]
    public void LRUCache_V3()
    {
        foreach (var item in _data)
        {
            _cacheV3.Get(item);
        }
    }
}

寫入性能測試結(jié)果：

|      Method |      Mean |     Error |    StdDev |    Median |     Gen0 |     Gen1 | Allocated |
|------------ |----------:|----------:|----------:|----------:|---------:|---------:|----------:|
| LRUCache_V1 | 16.890 ms | 0.3344 ms | 0.8012 ms | 16.751 ms | 750.0000 | 218.7500 |   4.65 MB |
| LRUCache_V2 |  7.193 ms | 0.1395 ms | 0.3958 ms |  7.063 ms | 703.1250 | 226.5625 |   4.22 MB |
| LRUCache_V3 |  5.761 ms | 0.1102 ms | 0.1132 ms |  5.742 ms | 585.9375 | 187.5000 |   3.53 MB |

查詢性能測試結(jié)果：

|      Method |      Mean |     Error |    StdDev |    Gen0 | Allocated |
|------------ |----------:|----------:|----------:|--------:|----------:|
| LRUCache_V1 | 19.475 ms | 0.3824 ms | 0.3390 ms | 62.5000 |  474462 B |
| LRUCache_V2 |  1.994 ms | 0.0273 ms | 0.0242 ms |       - |       4 B |
| LRUCache_V3 |  1.595 ms | 0.0187 ms | 0.0175 ms |       - |       3 B |

本文詳細介紹了LRU緩存替換策略的原理和實現(xiàn)方法，包括使用哈希表和雙向鏈表來實現(xiàn)LRU緩存。通過實現(xiàn)LRU緩存，可以有效地提高程序的性能和響應(yīng)速度。同時，本文還介紹了C#語言中實現(xiàn)LRU緩存的具體步驟和代碼實現(xiàn)。通過本文的學(xué)習(xí)，讀者可以深入了解LRU緩存替換策略，并掌握C#語言中實現(xiàn)LRU緩存的方法。

到此這篇關(guān)于LRU緩存替換策略及C#實現(xiàn)方法分享的文章就介紹到這了,更多相關(guān)LRU緩存替換策略內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: