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

Introduction

Recently, I studied LRU (Least Recently Used) and LFU (Least Frequently Used) while preparing for an information processing exam. To apply what I’ve learned, I decided to implement an image cacher. In this post, we’ll use the LRU caching strategy to create a simple yet efficient ImageCacher.

Explanation

LRU caching keeps the most recently used data in the cache and removes old data. This ensures frequently used data stays in the cache, while unused data is automatically removed. Below is an example of a thread-safe LRU cache implemented using Swift’s actor.

import UIKit

actor ImageCacher {
    static let shared = ImageCacher()
    private init() { }
    
    private var cachedImages: [String: UIImage] = [:]
    private var accessOrder: [String] = []
    private let cacheLimit = 100
    
    func cachedImage(for key: String) -> UIImage? {
        if let image = cachedImages[key] {
            updateAccessOrder(for: key)
            return image
        }
        return nil
    }
    
    func cacheImage(_ image: UIImage, for key: String) {
        if cachedImages.keys.count >= cacheLimit {
            removeOldestImage()
        }
        cachedImages[key] = image
        updateAccessOrder(for: key)
    }
    
    private func updateAccessOrder(for key: String) {
        accessOrder.removeAll { $0 == key }
        accessOrder.append(key)
    }
    
    private func removeOldestImage() {
        if let oldestKey = accessOrder.first {
            cachedImages.removeValue(forKey: oldestKey)
            accessOrder.removeFirst()
        }
    }
}

Code Explanation

Cache Structure:

• cachedImages: A dictionary to store image data.
• accessOrder: An array to store the access order of image keys.
• cacheLimit: Sets the maximum number of images to store in the cache.

cachedImage(for:):

• Returns the image for the given key.
• Updates the access order if the image exists.

cacheImage(_:for:):

• Stores the image and key in the cache.
• Removes the oldest image if the cache exceeds its limit.
• Updates the access order.

updateAccessOrder(for:):

• Removes the accessed key from accessOrder and appends it to the end to mark it as the most recently accessed.

removeOldestImage():

• Removes the first item from the accessOrder array and the corresponding image from cachedImages.

Conclusion

We have implemented an image cacher using the LRU (Least Recently Used) page replacement algorithm. This approach maintains frequently used data in the cache and efficiently manages memory by automatically removing old data. The use of Swift’s actor ensures thread safety.