Understanding LRU Cache in Python

The Least Recently Used (LRU) cache is a powerful data structure that helps in managing the use of memory in the most efficient manner by keeping track of the order in which items are accessed. It is primarily used to store a subset of data that should be readily available to the application. This makes it a great tool for optimizing performance-intensive applications.

Key APIs and Methods in LRU Cache

1. Creating an LRU Cache

  from collections import OrderedDict

  class LRUCache:
      def __init__(self, capacity: int):
          self.cache = OrderedDict()
          self.capacity = capacity

      def get(self, key: int) -> int:
          if key not in self.cache:
              return -1
          else:
              self.cache.move_to_end(key)
              return self.cache[key]

      def put(self, key: int, value: int) -> None:
          if key in self.cache:
              self.cache.move_to_end(key)
          self.cache[key] = value
          if len(self.cache) > self.capacity:
              self.cache.popitem(last=False)

2. Adding Items to the Cache

  cache = LRUCache(2)
  cache.put(1, 1)  # Cache is {1: 1}
  cache.put(2, 2)  # Cache is {1: 1, 2: 2}
  cache.put(3, 3)  # Cache is {2: 2, 3: 3} (1 is evicted)

3. Retrieving Items from the Cache

  print(cache.get(1))  # Returns -1 (not found)
  print(cache.get(2))  # Returns 2 (found)

4. Updating and Accessing the Cache

  cache.put(4, 4)  # Cache is {3: 3, 4: 4} (2 is evicted)
  print(cache.get(2))  # Returns -1 (not found)
  print(cache.get(3))  # Returns 3 (found)
  print(cache.get(4))  # Returns 4 (found)

Example Application Using LRU Cache

Consider a web application that fetches user profiles. Here’s how you can implement an LRU cache to store the profiles and improve performance.

  class UserProfileCache:
      def __init__(self, capacity: int):
          self.lru_cache = LRUCache(capacity)

      def get_user_profile(self, user_id: int):
          profile = self.lru_cache.get(user_id)
          if profile == -1:
              profile = self.fetch_from_db(user_id)
              self.lru_cache.put(user_id, profile)
          return profile

      def fetch_from_db(self, user_id: int):
          # Simulate a database fetch
          return {"user_id": user_id, "name": f"User{user_id}", "email": f"user{user_id}@example.com"}

  profile_cache = UserProfileCache(3)
  print(profile_cache.get_user_profile(1))  # Fetches from DB and caches
  print(profile_cache.get_user_profile(2))  # Fetches from DB and caches
  print(profile_cache.get_user_profile(1))  # Returns from cache
  print(profile_cache.get_user_profile(3))  # Fetches from DB and caches
  print(profile_cache.get_user_profile(4))  # Fetches from DB and caches
  print(profile_cache.get_user_profile(2))  # Returns -1, as it was evicted

By implementing an LRU cache, the application efficiently manages the most frequently accessed data in memory, providing quick access and overall improved performance.

Hash: 9872a5bb267f9a3a0a194693fd1b43bc428d9f77b12a9734045fa0964b806ea5