C++ LRU 缓存——需要关于如何提高速度的建议

Question

任务是实现 O(1) 最近最少使用的缓存

这里是leetcode上的题目
https://leetcode.com/problems/lru-cache/

这是我的解决方案，虽然它是 O(1)，但它不是最快的实施方式
您能否提供一些反馈以及关于如何优化它的想法？谢谢！


#include<unordered_map>
#include<list>

class LRUCache {

    // umap<key,<value,listiterator>>
    // store the key,value, position in list(iterator) where push_back occurred
private:
    unordered_map<int,pair<int,list<int>::iterator>> umap;
    list<int> klist;  
    int cap = -1;

public:
    LRUCache(int capacity):cap(capacity){

    }

    int get(int key) {
        // if the key exists in the unordered map
        if(umap.count(key)){
            // remove it from the old position 
            klist.erase(umap[key].second);
            klist.push_back(key);
            list<int>::iterator key_loc = klist.end();
            umap[key].second = --key_loc;
            return umap[key].first;
        }
        return -1;
    }

    void put(int key, int value) {

        // if key already exists delete it from the the umap and klist
        if(umap.count(key)){
            klist.erase(umap[key].second);
            umap.erase(key);
        }
        // if the unordered map is at max capacity
        if(umap.size() == cap){
            umap.erase(klist.front());
            klist.pop_front();
        }
        // finally update klist and umap
        klist.push_back(key);
        list<int>::iterator key_loc = klist.end();
        umap[key].first = value;
        umap[key].second = --key_loc;
        return;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Answer 1

Here is my solution, while it is O(1) it is not the fastest implementation could you give some feedback and maybe ideas on how can I optimize this ? Thank you !

在这里接受 selbie 的观点：
if(umap.count(key)) 的每个实例都将搜索密钥，使用 umap[key] 等同于搜索。您可以通过分配一个迭代器来避免双重搜索，该迭代器通过单个 std::unordered_map::find() 操作指向该键。

selbie 已经给出了 int get() 的搜索代码，这里是 void put() 的搜索代码：

auto it = umap.find(key);
if (it != umap.end()) 
{
    klist.erase(it ->second);
    umap.erase(key);
}

侧箱：

由于缺少输入和输出工作，目前不适用于您的代码，但如果您使用 std::cin 和 std::cout，您可以禁用 C 和 C++ 流之间的同步，并将 cin 从 cout 中解开作为优化：（默认情况下它们是捆绑在一起的）

// If your using cin/cout or I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Answer 2

下面是一些可能有帮助的优化：

从get函数中取出这段代码：

    if(umap.count(key)){
        // remove it from the old position 
        klist.erase(umap[key].second);

以上将在地图中查找 key 两次。一次为count方法查看是否存在。另一个调用 [] 运算符来获取它的值。这样做可以节省几个周期：

auto itor = umap.find(key);
if (itor != umap.end()) {
        // remove it from the old position 
        klist.erase(itor->second);

在put函数中，你这样做：

    if(umap.count(key)){
        klist.erase(umap[key].second);
        umap.erase(key);
    }

和get一样，可以通过umap避免冗余搜索。此外，没有理由调用 umap.erase 只是为了在几行之后将相同的键添加回地图。

此外，这也是低效的

    umap[key].first = value;
    umap[key].second = --key_loc;

与上面类似，在地图中重复查找 key 两次。在第一个赋值语句中， key 不在映射中，因此它默认构造一个新的值对事物。第二项任务是在地图中进行另一次查找。

让我们重组您的 put 函数，如下所示：

void put(int key, int value) {

    auto itor = umap.find(key);
    bool reinsert = (itor != umap.end());

    // if key already exists delete it from the klist only
    if (reinsert) {
        klist.erase(umap[key].second);
    }
    else {
        // if the unordered map is at max capacity
        if (umap.size() == cap) {
            umap.erase(klist.front());
            klist.pop_front();
        }
    }

    // finally update klist and umap
    klist.push_back(key);
    list<int>::iterator key_loc = klist.end();
    auto endOfList = --key_loc;

    if (reinsert) {
        itor->second.first = value;
        itor->second.second = endOfList;
    }
    else  {
        const pair<int, list<int>::iterator> itempair = { value, endOfList };
        umap.emplace(key, itempair);
    }
}

这是您使用 std::list 可能达到的极限。 list 类型的缺点是无法将现有节点从中间移动到前面（或后面），除非先将其删除然后再将其添加回去。这是一些不需要的内存分配来更新列表。可能的替代方法是您只使用自己的双链表类型并自己手动修复 prev/next 指针。

C++ LRU 缓存——需要关于如何提高速度的建议

C++ LRU cache - need suggestions on how to improve speed

c++

algorithm

lru