在 Scala 中是否有一种通用的记忆方法？

Question

提问by pathikrit

I wanted to memoize this:

我想记住这个：

def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)
println(fib(100)) // times out

So I wrote this and this surprisingly compiles and works (I am surprised because fibreferences itself in its declaration):

所以我写了这个，这个令人惊讶的编译和工作（我很惊讶，因为fib在它的声明中引用了自己）：

case class Memo[A,B](f: A => B) extends (A => B) {
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A) = cache getOrElseUpdate (x, f(x))
}

val fib: Memo[Int, BigInt] = Memo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2) 
}

println(fib(100))     // prints 100th fibonacci number instantly

But when I try to declare fib inside of a def, I get a compiler error:

但是当我尝试在 a 中声明 fib 时def，出现编译器错误：

def foo(n: Int) = {
  val fib: Memo[Int, BigInt] = Memo {
    case 0 => 0
    case 1 => 1
    case n => fib(n-1) + fib(n-2) 
  }
  fib(n)
}

Above fails to compile error: forward reference extends over definition of value fib case n => fib(n-1) + fib(n-2)

以上编译失败 error: forward reference extends over definition of value fib case n => fib(n-1) + fib(n-2)

Why does declaring the val fibinside a def fails but outside in the class/object scope works?

为什么val fib在 def 内部声明失败，但在类/对象范围之外声明有效？

To clarify, why I might want to declare the recursive memoized function in the def scope - here is my solution to the subset sum problem:

澄清一下，为什么我可能想在 def 范围内声明递归记忆化函数 - 这是我对子集求和问题的解决方案：

/**
   * Subset sum algorithm - can we achieve sum t using elements from s?
   *
   * @param s set of integers
   * @param t target
   * @return true iff there exists a subset of s that sums to t
   */
  def subsetSum(s: Seq[Int], t: Int): Boolean = {
    val max = s.scanLeft(0)((sum, i) => (sum + i) max sum)  //max(i) =  largest sum achievable from first i elements
    val min = s.scanLeft(0)((sum, i) => (sum + i) min sum)  //min(i) = smallest sum achievable from first i elements

    val dp: Memo[(Int, Int), Boolean] = Memo {         // dp(i,x) = can we achieve x using the first i elements?
      case (_, 0) => true        // 0 can always be achieved using empty set
      case (0, _) => false       // if empty set, non-zero cannot be achieved
      case (i, x) if min(i) <= x && x <= max(i) => dp(i-1, x - s(i-1)) || dp(i-1, x)  // try with/without s(i-1)
      case _ => false            // outside range otherwise
    }

    dp(s.length, t)
  }

Answer 1

采纳答案by pathikrit

I found a better way to memoize using Scala:

我找到了一种使用 Scala 进行记忆的更好方法：

def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {
  override def apply(key: I) = getOrElseUpdate(key, f(key))
}

Now you can write fibonacci as follows:

现在你可以写斐波那契如下：

lazy val fib: Int => BigInt = memoize {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2)
}

Here's one with multiple arguments (the choose function):

这是一个带有多个参数的参数（选择函数）：

lazy val c: ((Int, Int)) => BigInt = memoize {
  case (_, 0) => 1
  case (n, r) if r > n/2 => c(n, n - r)
  case (n, r) => c(n - 1, r - 1) + c(n - 1, r)
}

And here's the subset sum problem:

这是子集和问题：

// is there a subset of s which has sum = t
def isSubsetSumAchievable(s: Vector[Int], t: Int) = {
  // f is (i, j) => Boolean i.e. can the first i elements of s add up to j
  lazy val f: ((Int, Int)) => Boolean = memoize {
    case (_, 0) => true        // 0 can always be achieved using empty list
    case (0, _) => false       // we can never achieve non-zero if we have empty list
    case (i, j) => 
      val k = i - 1            // try the kth element
      f(k, j - s(k)) || f(k, j)
  }
  f(s.length, t)
}

EDIT: As discussed below, here is a thread-safe version

编辑：如下所述，这是一个线程安全版本

def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {self =>
  override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key)))
}

Answer 2

回答by missingfaktor

Class/trait level valcompiles to a combination of a method and a private variable. Hence a recursive definition is allowed.

类/特征级别val编译为方法和私有变量的组合。因此允许递归定义。

Local vals on the other hand are just regular variables, and thus recursive definition is not allowed.

val另一方面，局部变量只是常规变量，因此不允许递归定义。

By the way, even if the defyou defined worked, it wouldn't do what you expect. On every invocation of fooa new function object fibwill be created and it will have its own backing map. What you should be doing instead is this (if you really want a defto be your public interface):

顺便说一句，即使def你定义的工作，它也不会做你期望的。每次调用foo一个新的函数对象时fib都会被创建，并且它会有自己的支持映射。相反，您应该做的是（如果您真的希望 adef成为您的公共接口）：

private val fib: Memo[Int, BigInt] = Memo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2) 
}

def foo(n: Int) = {
  fib(n)
}

Answer 3

回答by michau

Scalaz has a solution for that, why not reuse it?

Scalaz 有一个解决方案，为什么不重用它？

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

You can read more about memoization in Scalaz.

您可以在 Scalaz 中阅读有关记忆的更多信息。

Answer 4

回答by Boolean

Mutable HashMap isn't thread safe. Also defining case statements separately for base conditions seems unnecessary special handling, rather Map can be loaded with initial values and passed to Memoizer. Following would be the signature of Memoizer where it accepts a memo(immutable Map) and formula and returns a recursive function.

可变 HashMap 不是线程安全的。此外，为基本条件单独定义 case 语句似乎是不必要的特殊处理，而 Map 可以加载初始值并传递给 Memoizer。以下是 Memoizer 的签名，它接受备忘录（不可变映射）和公式并返回递归函数。

Memoizer would look like

备忘录看起来像

def memoize[I,O](memo: Map[I, O], formula: (I => O, I) => O): I => O

Now given a following Fibonacci formula,

现在给出以下斐波那契公式，

def fib(f: Int => Int, n: Int) = f(n-1) + f(n-2)

fibonacci with Memoizer can be defined as

带有 Memoizer 的斐波那契可以定义为

val fibonacci = memoize( Map(0 -> 0, 1 -> 1), fib)

where context agnostic general purpose Memoizer is defined as

其中上下文无关的通用 Memoizer 被定义为

    def memoize[I, O](map: Map[I, O], formula: (I => O, I) => O): I => O = {
        var memo = map
        def recur(n: I): O = {
          if( memo contains n) {
            memo(n) 
          } else {
            val result = formula(recur, n)
            memo += (n -> result)
            result
          }
        }
        recur
      }

Similarly, for factorial, a formula is

类似地，对于阶乘，一个公式是

def fac(f: Int => Int, n: Int): Int = n * f(n-1)

and factorial with Memoizer is

和 Memoizer 的阶乘是

val factorial = memoize( Map(0 -> 1, 1 -> 1), fac)

Inspiration: Memoization, Chapter 4 of Javascript good parts by Douglas Crockford

灵感：记忆，Douglas Crockford 的 Javascript 好部分的第 4 章

在 Scala 中是否有一种通用的记忆方法？

提问by pathikrit

采纳答案by pathikrit

回答by missingfaktor

回答by michau

回答by Boolean

相关推荐

最近更新

标签

在 Scala 中是否有一种通用的记忆方法？

提问by pathikrit

采纳答案by pathikrit

回答by missingfaktor

回答by michau

回答by Boolean

相关推荐

scala 附加到可变 LinkedList

scala 如何在元组列表中找到最大值？

初学者：Scala 2.10 中的 Scala 类型别名？

scala 动态类型如何工作以及如何使用它？

相关推荐

最近更新

标签