I've been working on the classic LFU (Least Frequently Used) cache running in O(1) time problem lately and, as a student, I kind of struggled with the algorithms I found online. I got most of the idea behind them, but it still was a nightmare replicating them. I've tried to start coding it from scratch. Here's my result (Kotlin):
package main
// Object stored in the cache, could be anything
class Object (val key: String, val value: Int)
class LeastFrequentlyUsed (private val cacheLimit :Int) {
// Holds objects
private val cache = mutableListOf<Object>()
// Keeps track of hashes -> index, used in get(key) => hash(key) => index
private val indexLinks = mutableMapOf<Int,Int>()
// Keeps track of calls
private val calledObjects = mutableMapOf<Int, Int>()
// Keeps track of the last inserted index
private var lastInserted :Int = 0
// Collectors and printer for the LFU cache state
private fun collectCache() :MutableList<Pair<String,Int>> {
val collector = mutableListOf<Pair<String,Int>>()
cache.forEach {
collector.add(Pair(it.key, it.value))
}
return collector
}
private fun collectCounters () :MutableList<Pair<String,Int>> {
val collector = mutableListOf<Pair<String,Int>>()
cache.forEach {
collector.add(Pair(
it.key,
calledObjects[it.key.hashCode()]!!
))
}
return collector
}
private fun collectIndexLinks () :MutableList<Pair<String,Int>> {
val collector = mutableListOf<Pair<String,Int>>()
cache.forEach {
collector.add(Pair(
it.key,
indexLinks[it.key.hashCode()]!!
))
}
return collector
}
fun printLfu() {
println("Cache: ${collectCache()}")
println("Counters: ${collectCounters()}")
println("IndexLinks: ${collectIndexLinks()}")
println()
}
// LFU setter
fun set(key :String, value: Int) {
val hashKey = key.hashCode()
// If we reached the cache limit we need to take away the less used item in the cache
if (lastInserted == cacheLimit) {
// Lower lastInserted of 1 just to bring it back to max later
lastInserted--
// Brings up least used item, stored in the last index of the cache
val lessUsedItem = cache.last()
// Removes the least used item from cache
cache.removeLast()
// Clears indexLinks from the element removed from cache
indexLinks.remove(lessUsedItem.key.hashCode())
// Clears calledObjects from the element removed from cache
calledObjects.remove(lessUsedItem.key.hashCode())
}
// Adds the new element to cache
cache.add(Object(key,value))
// Adds the new element to indexLinks
indexLinks[hashKey] = lastInserted
// Adds the new element to calledObjects
calledObjects[hashKey] = 0
// Turns back lastInserted to max = cache limit
lastInserted++
}
// LFU getter
fun get (key :String) :Object? {
val hashKey = key.hashCode()
// Verify if the key is present in the LFU
indexLinks[hashKey] ?: return null
// Updates the calledObjects counter
calledObjects[hashKey] = calledObjects[hashKey]!!.plus(1)
// Gets the current element position in the cache
val currentItemIndex = indexLinks[hashKey]!!
if (currentItemIndex > 0 ) {
// Gets the previous element position in the cache, which is the current -1
val previousItemIndex = currentItemIndex - 1
// Gets the key of the previous item to find it in calledObjects and see its number of calls
val previousItemKey = cache[previousItemIndex].key.hashCode()
// Checks which is the most called: the current or the previous.
// If is the current, swap the two
if (calledObjects[hashKey]!! > calledObjects[previousItemKey]!!) {
// Adjusts the position in the cache
val temp = cache[previousItemIndex]
cache[previousItemIndex] = cache[currentItemIndex]
cache[currentItemIndex] = temp
// Adjusts their indices in the indexLists map
indexLinks[hashKey] = indexLinks[hashKey]!! - 1
indexLinks[previousItemKey] = indexLinks[previousItemKey]!! + 1
}
}
return cache[indexLinks[hashKey]!!]
}
}
fun main () {
val lfu = LeastFrequentlyUsed(3)
lfu.set("Alice", 10)
lfu.set("Bob", 20)
lfu.set("Charlie",30)
lfu.printLfu()
lfu.get("Charlie")
lfu.get("Charlie")
lfu.set("Dean", 50)
lfu.get("Dean")
lfu.printLfu()
lfu.get("gianni")
}
The code actually works, but would someone more experienced tell me how near to an actual solution I am? Any problems I did not see or hints for improvement?
Git gist of the code
