Introduction #

This tutorial is part of a collection tutorials on basic data structures and algorithms that are created using Kotlin. This project is useful if you are trying to get more fluency in Kotlin or need a refresher to do interview prep for software engineering roles.

How to run this project #

You can get the code for this and all the other tutorials in this collection from this github repo. Here’s a screen capture of project in this repo in action.

Once you’ve cloned the repo, type ./gradlew run in order to build and run this project from the command line.

Importing this project into JetBrains IntelliJ IDEA #

  • This project was created using JetBrains Idea as a Gradle and Kotlin project (more info). - When you import this project into Idea as a Gradle project, make sure not to check “Offline work” (which if checked, won’t allow the gradle dependencies to be downloaded). - As of Jun 24 2018, Java 10 doesn’t work w/ this gradle distribution (v4.4.x), so you can use Java 9 or 8, or upgrade to a newer version of gradle (4.8+).

LRU and MRU # 

enum class Type { LRU, MRU }

class Cache<T>(val type: Type, val size: Int) {
    val map = mutableMapOf<T, Int>()
    var rank = 0

    fun put(value: T): T? {
        var evictedKey: T? = null

        when {
            map.containsKey(value) -> {
                // Increase rank of existing value.
                map[value] = rank++
            }
            map.size == size -> {
                // Remove the lowest or highest rank item in the map depending on Type.
                evictedKey = findKeyToEvict()
                map.remove(evictedKey)
                map.put(value, rank++)
            }
            else -> {
                // Add the new item.
                map.put(value, rank++)
            }
        }

        return evictedKey
    }

    /**
     * LRU means evict the item in the map w/ the lowest rank.
     * MRU means evict the item in the map w/ the highest rank.
     */
    fun findKeyToEvict(): T? {
        val rankToEvict = when (type) {
            Type.MRU -> Collections.max(map.values)
            Type.LRU -> Collections.min(map.values)
        }
        val keyToEvict = map.entries.find { it.value == rankToEvict }?.key
        return keyToEvict
    }

    override fun toString(): String = StringBuilder().apply {
        val list = mutableListOf<String>().apply {
            for (entry in map)
                add("'${entry.key}'->rank=${entry.value}".yellow())
        }
        append(list.joinToString(", ", "{", "}"))
    }.toString()
}

Notes on implementation #

  • According to the LRU Algorithm, the lowest rank item will be removed when a new one is inserted and there’s no space left in the cache. Also, every time an item is inserted into the cache it’s rank is set to the highest rank.
  • According to the MRU Algorithm, the highest rank item will be removed when a new one is inserted and there’s no space left in the cache. Also, every time an item is inserted into the cache it’s rank is set to the highest rank.

LRU cache w/ O(1) cost of cache eviction #

In the above implementations of LRU and MRU caches, there’s a cost to finding the key that needs to be evicted when the capacity has been reached. The following implementation provides a way to do this w/out incurring such a cost.

/**
 * This is a LRU cache that has no performance impact for cache insertions
 * once the capacity of the cache has been reached. For cache hit,
 * performance is O(1) and for cache eviction, it is O(1).
 */
class LowCostLRUCache<K, V>(private val capacity: Int = 5) {
    private val cache = HashMap<K, V>()
    private val insertionOrder = LinkedList<K>()

    /**
     * [HashMap] put and remove is O(1).
     * More info: https://stackoverflow.com/a/4578039/2085356
     */
    fun put(key: K, value: V): K? {
        var evictedKey: K? = null
        if (cache.size >= capacity) {
            evictedKey = getKeyToEvict()
            cache.remove(evictedKey)
        }
        cache[key] = value
        insertionOrder.addLast(key)
        return evictedKey
    }

    /**
     * [HashMap] get is O(1).
     * More info: https://stackoverflow.com/a/4578039/2085356
     */
    fun get(key: K): V? = cache[key]

    /**
     * The head of the [insertionOrder] is removed, which is O(1), since this
     * is a linked list, and it's inexpensive to remove an item from head.
     * More info: https://stackoverflow.com/a/42849573/2085356
     */
    private fun getKeyToEvict(): K? = insertionOrder.removeFirst()

    override fun toString() = cache.toString()
}

References #

You can get more information on Cache replacement policies on wikipedia.

Resources #

CS Fundamentals #

Data Structures #

Math #

Big-O Notation #

Kotlin #

Markdown utilities #

#cs #kt

Related Posts