时间戳

首页 > 解决方案 > LRU缓存问题的两种解决方案：为什么一种比另一种快？

c# - LRU缓存问题的两种解决方案：为什么一种比另一种快？

问题描述

我提交了 leetcode 的 LRU 缓存问题的解决方案，它在运行时排名为 33%。然后我看到比其他提交速度快 98% 的提交几乎与我的相同，只是略有不同。我注意到的最大区别是，他们没有使用字典和整数链表，而是使用了用户定义的结构。我不明白为什么这会影响性能。谢谢！

我的解决方案：

public class LRUCache 
{
    Dictionary<int,int> LRUDict = new Dictionary<int,int>();
    LinkedList<int> keys = new LinkedList<int>();
    int capacity = 0;
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int Get(int key) {
        int retval = -1;
        int entry;
        if (LRUDict.TryGetValue(key,out entry))
        {
            retval = entry;
            keys.Remove(key);
            keys.AddLast(key);
        }
        return retval;
    }

    public void Put(int key, int value) {
        //case 1: exists, no need to increment count and check capacity, just change value and move up
        if (LRUDict.ContainsKey(key))
        {
            keys.Remove(key);
            keys.AddLast(key);
        }
        //case 2: does not exist, need to add new entry, may need to kick out oldest one
        else
        {
            keys.AddLast(key);
            if (keys.Count > capacity)
            {
                int LRUKey = keys.First.Value;
                keys.RemoveFirst();
                LRUDict.Remove(LRUKey);
            }
        }
        LRUDict[key] =value;
    }
}

更快的解决方案：

public class LRUCache {

    struct Cache {
        public int Key { get;set; }
        public int Val { get;set; }
    }

    private int _capacity;
    private LinkedList<Cache> _cache = new LinkedList<Cache>();
    private Dictionary<int, LinkedListNode<Cache>> _keys = new Dictionary<int, LinkedListNode<Cache>>();

    public LRUCache(int capacity) {
        _capacity = capacity;
    }

    public int Get(int key) {

        if (_keys.TryGetValue(key, out var node)) {

            _cache.Remove(node);
            _cache.AddLast(node);

            return node.Value.Val;
        }

        return -1;
    }

    public void Put(int key, int value) {

        LinkedListNode<Cache> n;
        var containsKey = _keys.TryGetValue(key, out n);
        if (_cache.Count >= _capacity && !containsKey) {
            var invalidNode = _cache.First;
            _cache.RemoveFirst();
            _keys.Remove(invalidNode.Value.Key);
        }

        if (containsKey) {

            _cache.Remove(n);

        } 

        var cache = new Cache { Key = key, Val = value };
        var node = new LinkedListNode<Cache>(cache);
        _cache.AddLast(node);
        _keys[key] = node;
    }        
}

标签： c#performance

解决方案

第二种解决方案更快，因为它删除了 LinkedListNode，这可以在 O(1) 中完成。第一个解决方案删除一个值，这需要搜索链表或 O(n) 时间。

因此，第一个解决方案对于更多项目的扩展性会很差。

查看在这两种情况下使用的确切 Remove 方法重载 - 以及相应的文档。

推荐阅读