Guest User

Scala Single Generic Parameter Function Memoization

a guest
Aug 24th, 2015
160
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. The following code was created on the basis of Michid's Weblog https://michid.wordpress.com/2009/02/23/function_mem/
  3. and influenced by Daniel Spiewak's comment.
  4.  
  5. From what I understand, because of this implementation of Memoization, tail recursion compilation cannot be applied.
  6. As a result it is possible to have a StackOverflowError (try: fibonacci(250000)).  This can be avoided if the calculations are performed from the base cases up, instead of final case down to the base cases.
  7.  
  8. A bad solution to this that I can think of would be to check if the value is over a certain size (say 1000) and then calculate up from there. Below is a bad implementation of this idea.
  9.  
  10. Hugh Kaznowski
  11. */
  12. object Solution {
  13.  
  14.   class Memoize[-I, +O](f: (I, I=>O) => O) {
  15.     private[this] val cache = scala.collection.mutable.Map[I, O]();
  16.     def apply(i: I): O = {
  17.       if (cache.contains(i))
  18.         cache(i)
  19.       else {
  20.         println(s"Calculating for $i")
  21.         val ret = f(i, apply)
  22.         cache.put(i, ret)
  23.         ret
  24.       }
  25.     }
  26.   }
  27.  
  28.   def fib(v: Int, f: (Int=>Int)): Int = {
  29.     if (v<3)
  30.       1
  31.     else
  32.       f(v-2)+f(v-1)
  33.   }
  34.  
  35.   def badfib(v: Int, f: (Int=>Int)): Int = { // Can definitely be optimized
  36.     if (v>1000)
  37.       Range(v/2, v-2).foreach(f(_))
  38.     if (v<3)
  39.       1
  40.     else
  41.       f(v-2)+f(v-1)
  42.   }
  43.  
  44.   def main(args: Array[String]): Unit = {
  45.     val fibonacci = new Memoize(fib)
  46.     val bfibonacci = new Memoize(badfib)
  47.  
  48.     bfibonacci(2500000) // This will take a long time
  49.     println("-------------")
  50.     bfibonacci(26)
  51.   }
  52. }
RAW Paste Data