什么types用于存储在Scala中的内存中的可变数据表?

每次调用一个函数时,如果它是给定的一组参数值的结果还没有记忆,我想把结果放到一个内存表中。 一列是为了存储结果,而另一列是为了存储参数值。

我如何最好地实施这个? 参数是不同的types,包括一些枚举。

在C#中我通常使用DataTable。 在Scala中有相当的吗?

你可以使用一个mutable.Map[TupleN[A1, A2, ..., AN], R] ,或者如果内存是一个问题,可以使用WeakHashMap [1]。 下面的定义(build立在来自michid博客的记忆代码上 )使您可以轻松地使用多个参数来记忆函数。 例如:

 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 

定义:

 /** * 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 } } 

定点组合器( Memoize.Y )可以记忆recursion函数:

 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不能很好地作为caching。 见http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html和这个相关的问题; 。

anovstrup使用可变Map的build议版本与C#基本相同,因此易于使用。

但是如果你想要的话,你也可以使用更多function的风格。 它使用不可变的地图,作为一种准分子。 在元组中使用元组(而不是在这个例子中的int)作为关键字就像在可变的情况下一样。

 def fib(n:Int) = fibM(n, Map(0->1, 1->1))._1 def fibM(n:Int, m:Map[Int,Int]):(Int,Map[Int,Int]) = m.get(n) match { case Some(f) => (f, m) case None => val (f_1,m1) = fibM(n-1,m) val (f_2,m2) = fibM(n-2,m1) val f = f_1+f_2 (f, m2 + (n -> f)) } 

当然这有点复杂,但要知道一个有用的技术(注意上面的代码是为了清晰,而不是为了速度)。

作为这个主题的新手,我完全可以不了解所给出的任何例子(但无论如何要感谢)。 尊敬的,我会介绍我自己的解决scheme的情况下,有一个人来到这里有一个相同的水平和相同的问题。 我认为我的代码对于任何拥有非常非常基础的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]
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] 

完美的作品。 我会很感激批评如果我错过了一些东西。

当使用可变映射进行记忆时,应该记住,这会导致典型的并发问题,例如写入尚未完成时得到一个get。 但是,线程安全的memoization尝试build议这样做,如果不是没有价值的话,它是没有价值的。

以下线程安全的代码创build一个memoized fibonaccifibonacci函数,启动一些线程(从'a'到'd'),调用它。 尝试代码几次(在REPL),可以很容易地看到f(2) set打印不止一次。 这意味着一个线程A已经启动了f(2)的计算,但线程B完全不知道它,并开始自己的计算副本。 这种无知在caching的构build阶段是如此普遍,因为所有的线程都没有看到子解决scheme,并且会进入else子句。

 object ScalaMemoizationMultithread { // do not use case class as there is a mutable member here class Memo[-T, +R](f: T => R) extends (T => R) { // don't even know what would happen if immutable.Map used in a multithreading context private[this] val cache = new java.util.concurrent.ConcurrentHashMap[T, R] def apply(x: T): R = // no synchronized needed as there is no removal during memoization if (cache containsKey x) { Console.println(Thread.currentThread().getName() + ": f(" + x + ") get") cache.get(x) } else { val res = f(x) Console.println(Thread.currentThread().getName() + ": f(" + x + ") set") cache.putIfAbsent(x, res) // atomic res } } object Memo { def apply[T, R](f: T => R): T => R = new Memo(f) def Y[T, R](F: (T => R) => T => R): T => R = { lazy val yf: T => R = Memo(F(yf)(_)) yf } } val fibonacci: Int => BigInt = { def fiboF(f: Int => BigInt)(n: Int): BigInt = { if (n <= 0) 1 else if (n == 1) 1 else f(n - 1) + f(n - 2) } Memo.Y(fiboF) } def main(args: Array[String]) = { ('a' to 'd').foreach(ch => new Thread(new Runnable() { def run() { import scala.util.Random val rand = new Random (1 to 2).foreach(_ => { Thread.currentThread().setName("Thread " + ch) fibonacci(5) }) } }).start) } } 

除了Landei的回答之外,我也想提出在Scala中做DP的自下而上(非memoization)的方式是可能的,核心思想是使用foldLeft (s)。

计算斐波那契数的例子

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

最长的子序列的例子

 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 }