LFU Cache
Least Frequently Used (LFU) cache keeps track of how frequently an item is accessed or used. It works by ejecting the least frequently accessed items.
LFU Cache Operations
a. Get Operation.
b. Put Operation.
Get checks if the key exists in the cache.
If it exists:
Retrieve the value associated with the key.
Increase the frequency count for that key.
Update the data structures to reflect the new frequency.
Else
Return null or -1.
Complexity: O(1) on average, depending on the underlying data structure used to implement LFU.
Put checks if the key already exists in the cache.
If it does.
Update the value and increment the frequency count.
Else
If the cache is at capacity,
Evict the least frequently used item.
Else
Insert the new key-value pair and set its frequency to 1.
Complexity: O(1) on average, depending on the underlying data structure used.
Data Structures to implement an LFU cache efficiently, you typically use:
HashMap: For quick access to key-value pairs.
HashMap for Frequencies: To map frequency counts to the corresponding keys.
List: To maintain the order of keys by frequency and support quick removal and addition.
Uses of LFU
- Database cache
LFU caching can be used to keep track of the frequently queried database results.
Redis supports LFU caching in its eviction policy. Redis can be configured to use LFU eviction in addition to other eviction strategies like LRU (Least Recently Used).
Oracle Database offers LFU caching support through its SQL query cache.
Apache Cassandra has a cache configuration system where LFU can be employed for certain cache types.
Program to implement LFU (Least Frequently Used) Cache
#include<iostream>
#include<map>
#include<list>
#include<vector>
using namespace std;
class LFUCache {
int size; // Size of LFU cache
int count; // keys track of the elements that are pushed.
map <int, pair<int, int>> cache; // LFU cache table stores < key, < value, frequency > >
// Table stores list of keys based on their frequency. The first element of the list is the LRU key.
map <int, list<int>> freq_table;
public:
LFUCache (int arg_size) : size (arg_size), count(0) { }
// Update the frequency of the key
void Update_FrequencyTable (int freq, int key) {
// Update would involve deleting the previous pair <frequency, <key>> from the list.
if (freq > 1) { // Element should be already be present at previous frequency. So remove it.
freq_table[freq-1].remove(key);
}
freq_table[freq].push_back(key);
cout << "Frequency Table" << endl;
cout << "===============" << endl;
for (int freq=1; freq<=count; freq++) {
cout << "Freq [" << freq << "] : ";
list<int> :: iterator it;
for (it = freq_table[freq].begin(); it != freq_table[freq].end(); ++it)
cout << *it << " ";
cout << endl;
}
}
int Get (int key) {
cout << "\nOperation GET : " << key << endl;
if (cache.find(key) != cache.end()) {
cache[key].second += 1;
int freq = cache[key].second;
Update_FrequencyTable (freq, key);
cout << "Return ----> ";
return cache[key].first;
}
return -1;
}
void Put (int key, int value) {
if (size == 0)
return;
cout << "\nOperation PUT : [" << key << ":" << value << "]" << endl;
if (cache.find(key) != cache.end()) { // Key is found in the cache
cache[key].first = value;
cache[key].second += 1;
int freq = cache[key].second;
Update_FrequencyTable (freq, key);
} else { // Key not found in the cache
count++;
if (cache.size() == size) { // Cache is already full
cout << "Cache is full !!" << endl;
for (int freq=1; freq<=count; freq++) {
if (freq_table.find(freq) != freq_table.end() and freq_table[freq].size() > 0) {
int key = freq_table[freq].front();
cout << "Erasing key : " << key << endl;
cache.erase(key);
freq_table[freq].pop_front();
break;
}
}
}
cache[key].first = value;
cache[key].second = 1;
Update_FrequencyTable (1, key);
}
}
};
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;
cout << cache.Get(3) << endl;
cache.Put(4,4);
cout << cache.Get(1) << endl;
cout << cache.Get(3) << endl;
cout << cache.Get(4) << endl;
return 0;
}
Output
Operation PUT : [1:1]
Frequency Table
===============
Freq [1] : 1
Operation PUT : [2:2]
Frequency Table
===============
Freq [1] : 1 2
Freq [2] :
Operation GET : 1
Frequency Table
===============
Freq [1] : 2
Freq [2] : 1
Return ----> 1
Operation PUT : [3:3]
Cache is full !!
Erasing key : 2
Frequency Table
===============
Freq [1] : 3
Freq [2] : 1
Freq [3] :
Operation GET : 2
-1
Operation GET : 3
Frequency Table
===============
Freq [1] :
Freq [2] : 1 3
Freq [3] :
Return ----> 3
Operation PUT : [4:4]
Cache is full !!
Erasing key : 1
Frequency Table
===============
Freq [1] : 4
Freq [2] : 3
Freq [3] :
Freq [4] :
Operation GET : 1
-1
Operation GET : 3
Frequency Table
===============
Freq [1] : 4
Freq [2] :
Freq [3] : 3
Freq [4] :
Return ----> 3
Operation GET : 4
Frequency Table
===============
Freq [1] :
Freq [2] : 4
Freq [3] : 3
Freq [4] :
Return ----> 4