什么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 fibonacci那fibonacci函数，启动一些线程（从'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 }
