CS, Swift: Implementing an ImageCacher Using LFU(Least Frequently Used )

Introduction

Recently, while studying for the Information Processing Engineer exam, I learned about LRU (Least Recently Used) and LFU (Least Frequently Used) caching strategies. To apply this knowledge in practice, I will implement an image cacher. In this article, we will create a simple yet efficient ImageCacher using the LFU caching strategy.

Previous Post

CS, Swift: Implementing an ImageCacher Using LRU (Least Recently Used)

Exaplanation

LFU caching is a strategy that retains the most frequently used data in the cache and removes data that is less frequently used. This way, infrequently used data is automatically removed, and frequently used data remains in the cache. Below is an example of implementing a thread-safe LFU cache using Swift’s actor.

actor ImageCacher {    

  static let shared = ImageCacher()
  private init() { }
  
  private var cachedImages: [String: UIImage] = [:]
  private var accessFrequency: [String: Int] = [:]
  private let cacheLimit = 100
  
  func cachedImage(for key: String) -> UIImage? {
      if let image = cachedImages[key] {
          updateAccessFrequency(for: key)
          return image
      }
      return nil
  }
  
  func cacheImage(_ image: UIImage, for key: String) {
      if cachedImages.keys.count >= cacheLimit {
          removeLeastFrequentlyUsedImage()
      }
      cachedImages[key] = image
      updateAccessFrequency(for: key, initial: true)
  }
  
  private func updateAccessFrequency(for key: String, initial: Bool = false) {
      if initial {
          accessFrequency[key] = 1
      } else {
          accessFrequency[key, default: 0] += 1
      }
  }
  
  private func removeLeastFrequentlyUsedImage() {
      if let leastFrequentlyUsedKey = accessFrequency.min(by: { $0.value < $1.value })?.key {
          cachedImages.removeValue(forKey: leastFrequentlyUsedKey)
          accessFrequency.removeValue(forKey: leastFrequentlyUsedKey)
      }
  }
}

Code Explanation

Cache Structure:

• cachedImages: A dictionary to store image data.
• accessFrequency: A dictionary to store the access frequency of each image key.
• cacheLimit: The maximum number of images to store in the cache.

cachedImage(for:):

• Returns the image corresponding to the given key.
• If the image exists, updates the access frequency.

cacheImage(_:for:):

• Stores the given image data with the specified key in the cache.
• If the cache size exceeds the limit, removes the least frequently used image.
• Updates the access frequency.

updateAccessFrequency(for:initial:):

• Updates the access frequency of the accessed key.
• Sets the access frequency to 1 when initially storing.

removeLeastFrequentlyUsedImage():

• Finds and removes the image with the lowest access frequency.

Conclusion

We have implemented an image cacher using the LFU (Least Frequently Used) page replacement algorithm. This method efficiently manages memory usage by automatically removing infrequently used data. Using Swift’s actor ensures thread safety. LFU retains frequently used data in the cache and removes data with lower access frequencies, effectively increasing cache hit rates.