LRU高速缓存问题的两个解决方案:为什么一个解决方案比另一个更快

Question

我提交了leetcode的LRU缓存问题的解决方案，并且在运行时排名为33％。然后，我看到提交的速度比其余的速度快98％的速度几乎与我的差异相同。我注意到的最大区别是，他们使用了用户定义的结构，而不是使用INT的字典和LinkedList。我不明白为什么这会有所作为。谢谢！

我的解决方案：

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;
    }        
}

Answer 1

第二个解决方案更快，因为它可以删除linkedlistnode，可以在O（1）中完成。第一个解决方案删除了一个值，该值需要搜索链接列表或O（n）时间。

因此，第一个解决方案将随着更多项目而缩放得很差。

查看两种情况下使用的确切删除方法过载 - 以及相应的文档。

• linkedlist.remove（t） - 在第一个解决方案中使用

  删除指定值的第一次出现。该方法执行线性搜索；因此，此方法是O（n）操作。

• linkedlist.remove（linkedlistnode＆lt; t>） - 在第二个解决方案中使用

  删除指定的节点。此方法是O（1）操作。