LRU 缓存为何比 hashmap 更快？

Question

除了 LRU 缓存的结构之外，我还没有读过太多关于它的内容，但我仍然对它比常规哈希图快得多感到惊讶。

我做了一个测试，一个递归组合问题，使用常规哈希图来保存递归期间的结果结果（动态编程），并做了相同的操作，唯一的区别是使用了 LRU 缓存实现（大小 1024）。

性能从1秒下降到0.006秒！

现在，这非常令人惊讶，我不知道为什么会这样。对于大多数操作来说，哈希图的时间复杂度为 O(1)，并且 LRU 缓存需要哈希图和双向链表。

语境：

• 我在这个项目中使用 C++。所讨论的 hashmap 是一个 unordered_map，以字符串作为键，以整数作为值。我听说过 unordered_map 最坏情况的复杂度为N或N ²，但据我所知，它通常在O(1)中执行所有操作。

• LRU 缓存实现是从堆栈溢出复制粘贴的：D

代码

使用 LRU 缓存

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

template <typename T,typename U>                                                   
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")


// LRU Cache implementation
template <class KEY_T, class VAL_T> class LRUCache{
private:
        list< pair<KEY_T,VAL_T> > item_list;
        unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
        size_t cache_size;
private:
        void clean(void){
                while(item_map.size()>cache_size){
                        auto last_it = item_list.end(); last_it --;
                        item_map.erase(last_it->first);
                        item_list.pop_back();
                }
        };
public:
        LRUCache(int cache_size_):cache_size(cache_size_){
                ;
        };

        void put(const KEY_T &key, const VAL_T &val){
                auto it = item_map.find(key);
                if(it != item_map.end()){
                        item_list.erase(it->second);
                        item_map.erase(it);
                }
                item_list.push_front(make_pair(key,val));
                item_map.insert(make_pair(key, item_list.begin()));
                clean();
        };
        bool exist(const KEY_T &key){
                return (item_map.count(key)>0);
        };
        VAL_T get(const KEY_T &key){
                assert(exist(key));
                auto it = item_map.find(key);
                item_list.splice(item_list.begin(), item_list, it->second);
                return it->second->second;
        };

};


// recursive solution to a combinatorics problem

// number of permutations of each parcel
int item_ways(int w, int n, int max_w){
    if (w == 0 and n == 0)
        return 1;
    if (w <= 0 or n <= 0)
        return 0;
    int ways = 0;
    for (int i = 1; i <= max_w; i++)
        ways += item_ways(w-i, n-1, i);
    return ways;
}   

// total combinations for answer
LRUCache<string,int> dp(1024);
//unordered_map<string,int> dp;
int parcel_ways(int p, int max_w, int n, int w){
    if (p == 0 and n == 0) 
        return 1;
    if (p <= 0 and n <= 0)
        return 0;

    string x; 
    x += char(p); 
    x += char(max_w);
    x += char(n);
    x += char(w);
    
    if(dp.exist(x)) // caching/dp skips recursion here
    {
        return dp.get(x);
    }

    int ways = 0;
    for (int i = 1; i <= n; i++){
        ways += parcel_ways(p-1, max_w, n-i, w) * item_ways(w, i, max_w);
    }
    
    dp.put(x,ways); // cache here
    return ways;
}

// input any 4 numbers for problem
void solve()
{
    auto start = high_resolution_clock::now();
    cout << parcel_ways(5,8,23,17);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function: "
         << duration.count() << " microseconds" << endl;

}

int main()
{
    solve();
    return 0;
}

使用 unordered_map （哈希图）

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

template <typename T,typename U>                                                   
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

// number of permutations of each parcel
int item_ways(int w, int n, int max_w){
    if (w == 0 and n == 0)
        return 1;
    if (w <= 0 or n <= 0)
        return 0;
    int ways = 0;
    for (int i = 1; i <= max_w; i++)
        ways += item_ways(w-i, n-1, i);
    return ways;
}   

// total combinations for answer
unordered_map<string,int> dp;
int parcel_ways(int p, int max_w, int n, int w){
    if (p == 0 and n == 0) 
        return 1;
    if (p <= 0 and n <= 0)
        return 0;

    string x; 
    x += char(p); 
    x += char(max_w);
    x += char(n);
    x += char(w);
    
    if(dp[x]) // caching/dp skips recursion here
    {
        return dp[x];
    }

    int ways = 0;
    for (int i = 1; i <= n; i++){
        ways += parcel_ways(p-1, max_w, n-i, w) * item_ways(w, i, max_w);
    }
    
    dp[x] = ways; // cache here
    return ways;
}

void solve()
{
    auto start = high_resolution_clock::now();
    cout << parcel_ways(5,8,23,17);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken by function: "
         << duration.count() << " microseconds" << endl;
}

int main()
{
    solve();
    return 0;
}

Answer 1

在您的实现中，有很多事情并不是最佳的，但我看到的唯一可以使您看到的差异程度是这样的：

if(dp[x]) // caching/dp skips recursion here
{
    return dp[x];
}

这不会返回 if dp[x]==0，因此您将重新计算任何 0 结果。

具有 LRU 缓存的版本使用exists，在这种情况下它将提前返回。

这可以通过使用（或者如果你没有 c++20）来完成dp.contains(x) dp.count(x)