2.1.4 LFU Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

/*

Maintains a least-frequently-used cache with fixed capacity. The cache supports lookups and updates
by key, evicting the entry with the fewest accesses whenever an insertion would exceed capacity, and
breaking ties among equally frequent entries by evicting the least recently used of them.

The difficulty compared to the least-recently-used cache of section 2.1.3 is that frequencies form
an unbounded set of buckets rather than a single ordering, so a naive implementation scans for the
minimum on every eviction. The fix is to bucket the keys by frequency, keeping one list of keys per
frequency in most-recently-used order, and to track the smallest occupied frequency. Every access
moves a key from bucket $f$ to bucket $f + 1$, which is O(1) with an iterator stored per key.

The tracked minimum needs no search either. An insertion always creates a key of frequency $1$, so
the minimum becomes $1$; an access raises exactly one key from the minimum bucket, so the minimum
can only rise by one, and it does so only when that bucket empties. Both updates are O(1), which is
what makes the whole structure constant time.

- `LFUCache<K, V>(capacity)` constructs an empty cache holding at most `capacity` keys, which must
  be positive. The key type `K` must support `operator==` and have `std::hash<K>` defined.
- `size()` returns the number of keys currently stored.
- `freq(key)` returns the number of accesses counted for `key`, or $0$ if it is absent.
- `get(key, &value)` returns whether `key` is present. On success, it copies the associated value
  into `value` and counts an access.
- `put(key, value)` inserts or updates `key`, counts an access, and evicts the least frequently used
  key if the insertion would exceed capacity.

Frequencies grow continually, so a long-lived cache can be held hostage by keys popular only once;
real implementations periodically halve every count, ageing the statistics without reordering them.
This implementation uses `int64_t` counts and asserts before their theoretical overflow.

Time Complexity:
- O(1) expected amortized per call to `get()`, `put()`, and `freq()`, and O(n) in the
  collision-heavy worst case for the hash table.
- O(1) per call to `size()`.

Space Complexity:
- O(n), where $n$ is the cache capacity.

*/

#include <cassert>
#include <cstdint>
#include <list>
#include <unordered_map>

template<typename K, typename V>
class LFUCache {
  struct Entry {
    V value;
    int64_t freq;
    typename std::list<K>::iterator pos;
  };

  int cap;
  int64_t min_freq;
  std::unordered_map<K, Entry> entries;
  std::unordered_map<int64_t, std::list<K>> buckets;  // Each frequency, newest at the front.

  // Moves an existing key from its bucket to the next one up, counting one access.
  void touch(const K &key) {
    Entry &entry = entries[key];
    assert(entry.freq < INT64_MAX);
    std::list<K> &bucket = buckets[entry.freq];
    bucket.erase(entry.pos);
    if (bucket.empty()) {
      buckets.erase(entry.freq);
      if (min_freq == entry.freq) {
        min_freq++;
      }
    }
    entry.freq++;
    buckets[entry.freq].push_front(key);
    entry.pos = buckets[entry.freq].begin();
  }

 public:
  explicit LFUCache(int capacity) : cap(capacity), min_freq(0) { assert(cap > 0); }

  LFUCache(const LFUCache &) = delete;
  LFUCache &operator=(const LFUCache &) = delete;
  int size() const { return static_cast<int>(entries.size()); }

  int64_t freq(const K &key) const {
    auto it = entries.find(key);
    return it == entries.end() ? 0 : it->second.freq;
  }

  bool get(const K &key, V *value) {
    auto it = entries.find(key);
    if (it == entries.end()) {
      return false;
    }
    if (value != nullptr) {
      *value = it->second.value;
    }
    touch(key);
    return true;
  }

  void put(const K &key, const V &value) {
    if (entries.count(key) > 0) {
      entries[key].value = value;
      touch(key);
      return;
    }
    if (size() == cap) {
      // The back of the minimum bucket is the least recently used of the least frequent keys.
      entries.erase(buckets[min_freq].back());
      buckets[min_freq].pop_back();
      if (buckets[min_freq].empty()) {
        buckets.erase(min_freq);
      }
    }
    min_freq = 1;
    buckets[1].push_front(key);
    entries[key] = Entry{value, 1, buckets[1].begin()};
  }
};

/*** Example Usage ***/

#include <string>
using namespace std;

int main() {
  LFUCache<int, string> cache(2);
  string value;
  assert(!cache.get(1, &value));

  cache.put(1, "one");
  cache.put(2, "two");
  assert(cache.size() == 2);
  assert(cache.get(1, &value) && value == "one");
  assert(cache.freq(1) == 2 && cache.freq(2) == 1);

  cache.put(3, "three");  // Key 2 is the least frequently used, so it is evicted.
  assert(!cache.get(2, &value));
  assert(cache.get(3, &value) && value == "three");

  // Keys 1 and 3 now both have frequency 2, so the least recently used of the two goes next.
  assert(cache.freq(1) == 2 && cache.freq(3) == 2);
  cache.put(4, "four");
  assert(!cache.get(1, &value));
  assert(cache.get(3, &value) && value == "three");

  // Updating a stored key counts as an access rather than an insertion.
  cache.put(3, "tres");
  assert(cache.get(3, &value) && value == "tres" && cache.size() == 2);
  return 0;
}