除了它由哪些结构组成，我没有仔细研究过LRU缓存，但我仍然很惊讶它比常规哈希表快多了。
我进行了一个测试，使用常规哈希表保存递归（动态规划）期间结果的问题（一个递归组合问题），并且只有一个区别：使用了LRU缓存实现（大小为1024）。
性能从1秒下降到0.006秒！
现在，这非常令人惊讶，我不知道为什么会这样。哈希表对于大多数操作具有O(1)时间复杂度，而LRU缓存需要同时哈希表和双向链表。
背景：
我在此项目中使用c ++。所讨论的哈希表是具有字符串键和整数值的unordered_map。我听说过unordered_map具有最坏情况下的复杂度N或N2，但据我所知，它通常在O(1)中执行所有操作。
LRU缓存实现是从stackoverflow上复制粘贴的: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;
}
unordered_map<T>实际上很差。由于标准所要求的限制，它基本上必须被实现为一个std::vector<std::list<T>>。这保证了每次访问至少有一个缓存未命中，很可能还会更多。这意味着你最好以 RAM 速度运行。 - NathanOliver#include <bits/stdc++.h>这个头文件，这个不太好。另外还有#define mp make_pair、#define pb push_back和#define ll long long，这也不太好。你是在使用一个“在线编程竞赛”网站来编写你的例子吗？同时，这段代码中也没有输入数据。 - PaulMcKenzie