LFU Caching Algorithm
Description
LFU (Least Frequently Used) caching algorithm is used to manage a cache where the least frequently used items are evicted when the cache reaches its capacity. It requires tracking both the frequency of access and the recentness of access for each item in the cache.
C++ Code
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LFUCache {
private:
int capacity;
unordered_map<int, pair<int, int>> cache;
unordered_map<int, list<int>> freqMap;
unordered_map<int, list<int>::iterator> iterMap;
int minFrequency;
public:
LFUCache(int capacity) {
this->capacity = capacity;
minFrequency = 0;
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
int value = cache[key].first;
int freq = cache[key].second;
freqMap[freq].erase(iterMap[key]);
cache[key].second++;
freqMap[freq + 1].push_back(key);
iterMap[key] = --freqMap[freq + 1].end();
if (freqMap[minFrequency].empty()) {
minFrequency++;
}
return value;
}
void put(int key, int value) {
if (capacity <= 0) {
return;
}
if (get(key) != -1) {
cache[key].first = value;
return;
}
if (cache.size() >= capacity) {
int evictKey = freqMap[minFrequency].front();
freqMap[minFrequency].pop_front();
cache.erase(evictKey);
iterMap.erase(evictKey);
}
cache[key] = {value, 1};
freqMap[1].push_back(key);
iterMap[key] = --freqMap[1].end();
minFrequency = 1;
}
};
int main() {
LFUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl;
cache.put(3, 3);
cout << cache.get(2) << endl;
cache.put(4, 4);
cout << cache.get(1) << endl;
cout << cache.get(3) << endl;
cout << cache.get(4) << endl;
return 0;
}
Time and Space Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Get(key) | O(1) | O(1) |
| Put(key, value) | O(1) | O(1) |
Where:
- n: Number of items in the cache.
- m: Capacity of the cache.