Welche Art zu verwenden, zu speichern, eine in-memory-veränderliche Daten-Tabelle in der Scala?

Könnte man eine mutable.Map[TupleN[A1, A2, ..., AN], R] , oder wenn der Speicher ist ein Anliegen, eine WeakHashMap[1]. Die Definitionen unten (gebaut auf der memoization code von michid ' s blog) können Sie einfach memoize Funktionen mit mehreren Argumenten. Zum Beispiel:

import Memoize._

def reallySlowFn(i: Int, s: String): Int = {
   Thread.sleep(3000)
   i + s.length
}

val memoizedSlowFn = memoize(reallySlowFn _)
memoizedSlowFn(1, "abc") //returns 4 after about 3 seconds
memoizedSlowFn(1, "abc") //returns 4 almost instantly

Definitionen:

/**
 * A memoized unary function.
 *
 * @param f A unary function to memoize
 * @param [T] the argument type
 * @param [R] the return type
 */
class Memoize1[-T, +R](f: T => R) extends (T => R) {
   import scala.collection.mutable
   //map that stores (argument, result) pairs
   private[this] val vals = mutable.Map.empty[T, R]

   //Given an argument x, 
   //  If vals contains x return vals(x).
   //  Otherwise, update vals so that vals(x) == f(x) and return f(x).
   def apply(x: T): R = vals getOrElseUpdate (x, f(x))
}

object Memoize {
   /**
    * Memoize a unary (single-argument) function.
    *
    * @param f the unary function to memoize
    */
   def memoize[T, R](f: T => R): (T => R) = new Memoize1(f)

   /**
    * Memoize a binary (two-argument) function.
    * 
    * @param f the binary function to memoize
    * 
    * This works by turning a function that takes two arguments of type
    * T1 and T2 into a function that takes a single argument of type 
    * (T1, T2), memoizing that "tupled" function, then "untupling" the
    * memoized function.
    */
   def memoize[T1, T2, R](f: (T1, T2) => R): ((T1, T2) => R) = 
      Function.untupled(memoize(f.tupled))

   /**
    * Memoize a ternary (three-argument) function.
    *
    * @param f the ternary function to memoize
    */
   def memoize[T1, T2, T3, R](f: (T1, T2, T3) => R): ((T1, T2, T3) => R) =
      Function.untupled(memoize(f.tupled))

   //... more memoize methods for higher-arity functions ...

   /**
    * Fixed-point combinator (for memoizing recursive functions).
    */
   def Y[T, R](f: (T => R) => T => R): (T => R) = {
      lazy val yf: (T => R) = memoize(f(yf)(_))
      yf
   }
}

Den fixed-point-combinator (Memoize.Y) macht es möglich memoize rekursive Funktionen:

val fib: BigInt => BigInt = {                         
   def fibRec(f: BigInt => BigInt)(n: BigInt): BigInt = {
      if (n == 0) 1 
      else if (n == 1) 1 
      else (f(n-1) + f(n-2))                           
   }                                                     
   Memoize.Y(fibRec)
}

[1] WeakHashMap funktioniert nicht gut als cache. Sehen http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html und in diesem Zusammenhang Frage.

Ein Neuling in diesem Thema, könnte ich voll verstehen keines der Beispiele gegeben (aber danke trotzdem). Bei allem Respekt, ich möchte hier meine Lösung für den Fall, jemand kommt hier mit einem gleichen level und das gleiche problem. Ich denke mein code können Sie crystal clear für jemand mit nur die sehr-sehr grundlegende Kenntnisse in Scala.

def MyFunction(dt : DateTime, param : Int) : Double
{
  val argsTuple = (dt, param)
  if(Memo.contains(argsTuple)) Memo(argsTuple) else Memoize(dt, param, MyRawFunction(dt, param))
}

def MyRawFunction(dt : DateTime, param : Int) : Double
{
  1.0 //A heavy calculation/querying here
}

def Memoize(dt : DateTime, param : Int, result : Double) : Double
{
  Memo += (dt, param) -> result
  result
}

val Memo = new  scala.collection.mutable.HashMap[(DateTime, Int), Double]

 

Funktioniert perfekt. Würde ich mich über Kritik, Wenn ich was übersehen habe.

Neben Landei Antwort, ich möchte auch vorschlagen, die bottom-up - (nicht-memoization) Weise zu tun, DP in Scala möglich ist, und die Kern-Idee ist die Verwendung foldLeft(s).

Beispiel für die Berechnung Fibonacci-zahlen

  def fibo(n: Int) = (1 to n).foldLeft((0, 1)) {
    (acc, i) => (acc._2, acc._1 + acc._2)
  }._1

Beispiel mit der längsten steigenden Teilfolge

def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
  xs.foldLeft(List[(Int, List[T])]()) {
    (memo, x) =>
      if (memo.isEmpty) List((1, List(x)))
      else {
        val resultIfEndsAtCurr = (memo, xs).zipped map {
          (tp, y) =>
            val len = tp._1
            val seq = tp._2
            if (ord.lteq(y, x)) { //current is greater than the previous end
              (len + 1, x :: seq) //reversely recorded to avoid O(n)
            } else {
              (1, List(x)) //start over
            }
        }
        memo :+ resultIfEndsAtCurr.maxBy(_._1)
      }
  }.maxBy(_._1)._2.reverse
}