LFU Cache 🎯

Welcome to our deep dive into the world of LFU Cache! This lesson is designed to be both beginner-friendly and informative for intermediates. By the end of this tutorial, you'll understand what an LFU Cache is, why it's important, and how to implement one in Python. Let's get started!

What is an LFU Cache? 📝

LFU Cache, or Least Frequently Used Cache, is a type of cache that uses the principle of least usage to evict the least frequently used items when the cache is full. This strategy helps to balance the trade-off between the cache size and the cache hit ratio.

Why Use an LFU Cache? 💡

Improved Cache Hit Ratio: By evicting the least frequently used items, we can increase the chance of accessing frequently used items, thus improving the cache hit ratio.
Efficient Resource Usage: LFU Cache helps in optimizing the use of memory by evicting infrequently used items, which in turn reduces the memory overhead.

Implementing an LFU Cache in Python 💻

Let's implement an LFU Cache in Python using a simple dictionary to store the cache items and a defaultdict from the collections library to count the frequency of item access.

python

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.freq_counter = defaultdict(int)
        self.min_freq = 0

    def get(self, key: str) -> int:
        if key not in self.cache:
            return -1

        self.freq_counter[key] += 1
        self.min_freq = min(self.min_freq, self.freq_counter[key])

        return self.cache[key]

    def put(self, key: str, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.freq_counter[key] += 1
            self.min_freq = min(self.min_freq, self.freq_counter[key])
        elif len(self.cache) < self.capacity:
            self.cache[key] = value
            self.freq_counter[key] = 1
        else:
            to_evict = None
            for k in self.freq_counter:
                if self.freq_counter[k] == self.min_freq:
                    to_evict = k
                    break

            del self.cache[to_evict]
            del self.freq_counter[to_evict]
            self.cache[key] = value
            self.freq_counter[key] = 1
            self.min_freq += 1

That's it for our LFU Cache tutorial! We hope you found this lesson informative and practical. Now that you understand the concept and have a working implementation, you can start using LFU Caches in your projects to optimize cache performance. Happy coding! 👋