c++ - LRU 缓存如何比 HashMap 更快？

Question

除了 LRU 缓存由哪些结构构成之外，我并没有深入了解它，但我仍然对它比常规 hashmap 快得多感到惊讶。

我做了一个测试，一个递归组合问题，使用常规 HashMap 来保存递归(动态规划)期间的结果结果，并且做了同样的事情，唯一的区别是使用了 LRU 缓存实现(大小 1024)相反。

性能从 1 秒下降到 0.006 秒!

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

上下文:

• 我在这个项目中使用 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];
}

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

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

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