Skip to content

Instantly share code, notes, and snippets.

@jeffreyolchovy
Created August 6, 2012 21:19
  • Star 6 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jeffreyolchovy/3278505 to your computer and use it in GitHub Desktop.
LRU cache implementation in Scala
import akka.stm._
import scala.collection.immutable.ListMap
case class LRUCache[A, B](private val MAX_ENTRIES: Int)
{
protected val cache = Ref(ListMap.empty[A, B])
def getOrElse(key: A)(fn: => B): B = {
get(key).getOrElse {
val result = fn
put(key, result)
result
}
}
def get(key: A): Option[B] = atomic {
cache.get.get(key)
}
def put(key: A, value: B) = atomic {
cache.alter { current =>
val altered = current + (key -> value)
if(altered.size > MAX_ENTRIES) altered.takeRight(MAX_ENTRIES) else altered
}
}
def remove(key: A) = atomic {
cache.alter { current => current - key }
}
}
@pathikrit
Copy link

What about:

import collection.JavaConversions._
def lruCache[A, B](maxEntries: Int): mutable.Map[A, B] = new java.util.LinkedHashMap[A, B]() {
  override def removeEldestEntry(eldest: java.util.Map.Entry[A,B]) = size > maxEntries
}

@miwanowski
Copy link

How's this LRU cache if values are not moved to the front when accessed?

@fairjm
Copy link

fairjm commented May 25, 2015

get(key).getOrElse {
  val result = fn
  put(key, result)
  result
}

not thread safe and the fn will be computed more than once...using java.util.concurrent.ConcurrentMap.computeIfAbsent is better

@leolee192
Copy link

just a FIFO rather than a LRU?

@baol
Copy link

baol commented Mar 11, 2020

What about:

import collection.JavaConversions._
def lruCache[A, B](maxEntries: Int): mutable.Map[A, B] = new java.util.LinkedHashMap[A, B]() {
  override def removeEldestEntry(eldest: java.util.Map.Entry[A,B]) = size > maxEntries
}

The code above is not LRU, in the sense that does not update the freshness on access.

It is possible to get LRU behaviour using a different constructor:

object LruMap {
  import collection.JavaConversions._
  def apply[A, B](maxEntries: Int): collection.mutable.Map[A, B] = new java.util.LinkedHashMap[A, B](16, 0.75F, true) {
    override def removeEldestEntry(eldest: java.util.Map.Entry[A,B]): Boolean = size > maxEntries
  }
}

@hayd
Copy link

hayd commented Jul 23, 2020

What are you supposed to do now that akka has dropped stm?
(and twitter dropped util-collections which had an LRUCache implementation.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment