I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib is called 10 times compared to 276 without it. I discovered that val fib is required: def fib results in the memo object being created on each call to fib!
I realize that this could eventually be generalized by parameterising memoize with a type T (or key K and value V) to replace Int. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib is called 10 times compared to 276 without it. I discovered that val fib is required: def fib results in the memo object being created on each call to fib!
I realize that this could eventually be generalized by parameterising memoize with a type T (or key K and value V) to replace Int. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib is called 10 times compared to 276 without it. I discovered that val fib is required: def fib results in the memo object being created on each call to fib!
I realize that this could eventually be generalized by parameterising memoize with a type T (or key K and value V) to replace Int. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.
Memoization of fibonacciFibonacci using generic Int => Int helper
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization. Here's the code I wrote
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib is called 10 times compared to 276 without it. I discovered that val fib is required: def fib results in the memo object being created on each call to fib!
I realize that this could eventually be generalized by parameterising memoize with a type T (or key K and value V) to replace Int. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.
Memoization of fibonacci using generic Int => Int helper
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization. Here's the code I wrote
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib is called 10 times compared to 276 without it. I discovered that val fib is required: def fib results in the memo object being created on each call to fib!
I realize that this could eventually be generalized by parameterising memoize with a type T (or key K and value V) to replace Int. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.
Memoization of Fibonacci using generic Int => Int helper
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
class memoize private (val f: Int => Int) {
import scala.collection.mutable
val cache = new mutable.HashMap[Int, Int]()
def memoized_f(x : Int) : Int =
cache.getOrElseUpdate(x, f(x))
}
object memoize {
def apply(f: Int => Int) : Int => Int = new memoize(f).memoized_f
}
val fib : Int=>Int = memoize((n:Int) => {
if (n <= 1) n else fib(n-1) + fib(n-2)
})
With memoization the function fib is called 10 times compared to 276 without it. I discovered that val fib is required: def fib results in the memo object being created on each call to fib!
I realize that this could eventually be generalized by parameterising memoize with a type T (or key K and value V) to replace Int. But I wanted to start somewhere simple to understand how the technique works. Given that I'm looking at memoizing only Int => Int functions, could what I've done be improved in terms of function or style?
I've also discovered a couple of related items on the web: Is there a generic way to memoize in Scala? and Memo in ScalaZ (see also this tutorial), but I'm not entirely sure how what I've done relates to them.