Created
September 24, 2013 10:59
-
-
Save gkeramidas/6683198 to your computer and use it in GitHub Desktop.
Caching the results of primality check, and expiring after a tunable TTL
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.concurrent.atomic.AtomicReference | |
import collection.immutable.HashMap | |
/* | |
* A module which implements a primality cache for integers, with a max-age parameter which controls | |
* when a primality result will be considered 'expired' and recalculated from scratch. | |
*/ | |
trait PrimeCacheModule { | |
/** The current time in milliseconds. Timestamp for cache entries and 'now' */ | |
def now = System.currentTimeMillis | |
class PrimeCache(maxAge: Long) { | |
case class CacheEntry(number: Long, prime: Boolean, time: Long) { | |
def age: Long = (now - time) | |
} | |
/** Returns the current cache, excluding entries which have expired. */ | |
def primes: HashMap[Long, CacheEntry] = | |
cache.get.filter{ case (key, entry) => entry.age <= maxAge } | |
/** Atomically updated reference to a HashMap holding the current cache. */ | |
private lazy val cache: AtomicReference[HashMap[Long, CacheEntry]] = | |
new AtomicReference(HashMap[Long, CacheEntry]()) | |
/** Check if a number is prime, using the primes cache for speedups. */ | |
def check(number: Long): Boolean = { | |
primes.find{ case (key, entry) => key == number && entry.age <= maxAge } match { | |
case Some((key, entry)) => | |
println("Cache hit for %8s => %-50s age: %s".format(key, entry, entry.age)) | |
entry.prime // Cache hit, but no update; aging continues normally. | |
case _ => | |
println("Cache miss for %s => calculating".format(number)) | |
val entry = CacheEntry(number, isPrime(number), now) | |
cache.set(primes + (number -> entry)) | |
entry.prime | |
} | |
} | |
/** Silly and expensive primality check. */ | |
def isPrime(number: Long): Boolean = { | |
def isPrimeIter(number: Long, divisor: Long): Boolean = | |
divisor match { | |
case d if (d > number / 2) => true | |
case d if (number % d == 0) => false | |
case _ => | |
isPrimeIter(number, divisor + 1) | |
} | |
number match { | |
case n if (n < 1) => false | |
case _ => isPrimeIter(number, 2) | |
} | |
} | |
} | |
} | |
class Primes(ttl: Long) extends PrimeCacheModule { | |
val cache = new PrimeCache(maxAge = ttl) | |
/** Checks is a number is prime, consulting the cache for any known prime values. */ | |
def check(number: Long): Boolean = cache.check(number) | |
} | |
// | |
// Sample code using Primes(ttl: Long) | |
// | |
val foo = new Primes(15000) // ttl of cache entries = 15 seconds | |
(1 to 40).foreach{k => foo.check(k.toLong)} // should print 'Cache miss' for all entries | |
(1 to 10).foreach{k => foo.check(k.toLong)} // should print 'Cache hit' for all entries | |
(1 to 10).foreach{k => foo.check(k.toLong)} // should print 'Cache hit' for all entries | |
/** Should display the cached entries which have not already expired. */ | |
foo.cache.primes.foreach{case (k, v) => println("entry %-50s age: %d".format(v, v.age))} |
Author
gkeramidas
commented
Sep 24, 2013
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment