使用 Memo.mutableHashMapMemo 在 Scala 中进行斐波那契记忆

Question

我正在尝试使用记忆在 Scala 中实现斐波那契函数

此处给出的一个示例使用了 case 语句： Is there a generic way to memoize in Scala?

import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-2) + fib(n-1)
}

似乎变量 n 被隐式定义为第一个参数，但是如果我将 n 替换为 _

会出现编译错误

此外，lazy 关键字在这里有什么优势，因为该函数在使用和不使用此关键字时似乎都同样有效。

但是我想通过适当的类型将其概括为更通用的函数定义

import scalaz.Memo
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
    var value : Int = 0
    if( n <= 1 ) { value = n; }
    else         { value = fibonachi(n-1) + fibonachi(n-2) }
    return value
}

但我得到以下编译错误

cmd10.sc:4: type mismatch;
 found   : Int => Int
 required: Int
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
                                                                         ^Compilation Failed
Compilation Failed

所以我试图了解向 Scala def 函数添加记忆注释的通用方法

Answer 1

实现斐波那契数列的一种方法是通过递归 Stream。

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)

流的一个有趣的方面是，如果流的头部有内容，计算结果会自动记忆。因此，在这种情况下，因为标识符 fib 是 val 而不是 def，所以 fib(n) 的值只计算一次，然后简单地检索。

但是，索引一个 Stream 仍然是一个线性操作。如果你想把它记下来，你可以创建一个简单的备忘录包装器。

def memo[A,R](f: A=>R): A=>R =
  new collection.mutable.WeakHashMap[A,R] {
    override def apply(a: A) = getOrElseUpdate(a,f(a))
  }

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)
val mfib = memo(fib)
mfib(99)  //res0: BigInt = 218922995834555169026

Answer 2

The more general question I am trying to ask is how to take a pre-existing def function and add a mutable/immutable memoization annotation/wrapper to it inline.

不幸的是，在 Scala 中没有办法做到这一点，除非你愿意为此使用 macro annotation，这对我来说感觉有点矫枉过正，或者使用一些非常丑陋的设计。

矛盾的要求是“def”和"inline"。这样做的根本原因是无论你用 def 做什么内联都不能创建任何新的地方来存储记忆值（除非你使用一个可以重写代码引入新的 val/ 的宏vars）。您可以尝试使用一些全局缓存来解决这个问题，但这个恕我直言属于 "ugly design" 分支。

ScalaZ Memo 的设计用于创建 Function[K,V] 类型的 val，通常用 Scala 编写为 K => V 而不是 def.通过这种方式，生成的 val 也可以包含缓存值的存储。另一方面，从语法上讲，def 方法和 K => V 函数的用法之间的差异很小，因此效果很好。由于 Scala 编译器知道如何将 def 方法转换为函数，因此您可以用 Memo 包装 def 但您不能从中得到 def 。如果出于某种原因你仍然需要 def，你将需要另一个包装器 def.

import scalaz.Memo

object Fib {

  def fib(n: Int): BigInt = n match {
    case 0 => BigInt(0)
    case 1 => BigInt(1)
    case _ => fib(n - 2) + fib(n - 1)
  }

  // "fib _" converts a method into a function. Sometimes "_" might be omitted 
  // and compiler can imply it but sometimes the compiler needs this explicit hint 
  lazy val fib_mem_val: Int => BigInt = Memo.mutableHashMapMemo(fib _) 

  def fib_mem_def(n: Int): BigInt = fib_mem_val(n)

}

println(Fib.fib(5))
println(Fib.fib_mem_val(5))
println(Fib.fib_mem_def(5))

请注意，尽管 fib_mem_val 是一个值，但调用 fib、fib_mem_val 和 fib_mem_def 的语法没有区别。你也可以试试这个例子 online

注意：请注意某些 ScalaZ Memo 实现不是线程安全的。

至于 lazy 部分，好处是任何 lazy val 的典型：在第一次使用之前不会创建具有底层存储的实际值。如果无论如何都会使用该方法，我认为将其声明为 lazy

没有任何好处

使用 Memo.mutableHashMapMemo 在 Scala 中进行斐波那契记忆

Fibonacci memoization in Scala with Memo.mutableHashMapMemo

scala

fibonacci

scalaz

memoization