Scala备忘:此Scala备忘如何工作? [英] Scala Memoization: How does this Scala memo work?

问题描述

以下代码来自

The following code is from Pathikrit's Dynamic Programming repository. I'm mystified by both its beauty and peculiarity.

def subsetSum(s: List[Int], t: Int) = {
  type DP = Memo[(List[Int], Int), (Int, Int), Seq[Seq[Int]]]
  implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)

  lazy val f: DP = Memo {
    case (Nil, 0) => Seq(Nil)
    case (Nil, _) => Nil
    case (a :: as, x) => (f(as, x - a) map {_ :+ a}) ++ f(as, x)
  }

  f(s, t)
}

Memo类型在另一个文件中实现:

The type Memo is implemented in another file:

case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
  import collection.mutable.{Map => Dict}
  val cache = Dict.empty[K, O]
  override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}

我的问题是:

1. 为什么在subsetSum中将type K声明为(Int, Int)?

(Int, Int)中的int分别代表什么?

<罢工> 3. (List[Int], Int)如何隐式转换为(Int, Int)?
我看不到implicit def foo(x:(List[Int],Int)) = (x._1.toInt,x._2). (甚至不在导入的Implicits.scala文件中.

3. How does (List[Int], Int) implicitly convert to (Int, Int)?
I see no implicit def foo(x:(List[Int],Int)) = (x._1.toInt,x._2). ( not even in the Implicits.scala file it imports.

*好吧，我想念这个了:

* Well, I miss this:

implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)

我非常喜欢Pathikrit的库 scalgos .里面有很多斯卡拉珍珠.请帮助我，让我欣赏Pathikrit的机智.谢谢你. (:

I enjoy Pathikrit's library scalgos very much. There are a lot of Scala pearls in it. Please help me with this so I can appreciate Pathikrit's wit. Thank you. (:

推荐答案

我是在Memo[I <% K, K, O]中:

I: input
K: key to lookup in cache
O: output

I <% K行表示K可以可见I中的a>(即隐式转换).

The line I <% K means the K can be viewable (i.e. implicitly converted) from I.

在大多数情况下，I应该是K，例如如果您编写的是Int => Int类型的函数fibonacci，则可以通过Int本身进行缓存.

In most cases, I should be K e.g. if you are writing fibonacci which is a function of type Int => Int, it is okay to cache by Int itself.

但是，有时在编写备忘录时，您不希望总是通过输入本身(I)进行备忘录或缓存，而是希望输入(K)的功能，例如在编写输入类型为(List[Int], Int)的算法，您不想使用List[Int]作为缓存中的键，而是希望使用List[Int].size作为缓存中键的一部分.

But, sometimes when you are writing memoization, you do not want to always memoize or cache by the input itself (I) but rather a function of the input (K) e.g when you are writing the subsetSum algorithm which has input of type (List[Int], Int), you do not want to use List[Int] as the key in your cache but rather you want use List[Int].size as the part of the key in your cache.

所以，这是一个具体案例:

So, here's a concrete case:

/**
 * Subset sum algorithm - can we achieve sum t using elements from s?
 * O(s.map(abs).sum * s.length)
 *
 * @param s set of integers
 * @param t target
 * @return true iff there exists a subset of s that sums to t
 */
 def isSubsetSumAchievable(s: List[Int], t: Int): Boolean = {
    type I = (List[Int], Int)     // input type
    type K = (Int, Int)           // cache key i.e. (list.size, int)
    type O = Boolean              // output type      

    type DP = Memo[I, K, O]

    // encode the input as a key in the cache i.e. make K implicitly convertible from I
    implicit def encode(input: DP#Input): DP#Key = (input._1.length, input._2)   

    lazy val f: DP = Memo {
      case (Nil, x) => x == 0      // an empty sequence can only achieve a sum of zero
      case (a :: as, x) => f(as, x - a) || f(as, x)      // try with/without a.head
    }

    f(s, t)
 }

您当然可以将所有这些缩短为一行: type DP = Memo[(List[Int], Int), (Int, Int), Boolean]

You can ofcourse shorten all these into a single line: type DP = Memo[(List[Int], Int), (Int, Int), Boolean]

对于常见情况(当I = K时)，您可以简单地执行以下操作:type ==>[I, O] = Memo[I, I, O] 并像这样使用它来通过递归记忆来计算二项式系数:

For the common case (when I = K), you can simply do this: type ==>[I, O] = Memo[I, I, O] and use it like this to calculate the binomial coeff with recursive memoization:

  /**
   * http://mathworld.wolfram.com/Combination.html
   * @return memoized function to calculate C(n,r)
   */
  val c: (Int, Int) ==> BigInt = Memo {
    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)
  }

要详细了解上述语法的工作原理，请

To see details how above syntax works, please refer to this question.

这里是一个完整的示例，该示例通过对输入 editDistance >到(Seq.length, Seq.length):

Here is a full example which calculates editDistance by encoding both the parameters of the input (Seq, Seq) to (Seq.length, Seq.length):

 /**
   * Calculate edit distance between 2 sequences
   * O(s1.length * s2.length)
   *
   * @return Minimum cost to convert s1 into s2 using delete, insert and replace operations
   */
  def editDistance[A](s1: Seq[A], s2: Seq[A]) = {

    type DP = Memo[(Seq[A], Seq[A]), (Int, Int), Int]
    implicit def encode(key: DP#Input): DP#Key = (key._1.length, key._2.length)

    lazy val f: DP = Memo {
      case (a, Nil) => a.length
      case (Nil, b) => b.length
      case (a :: as, b :: bs) if a == b => f(as, bs)
      case (a, b) => 1 + (f(a, b.tail) min f(a.tail, b) min f(a.tail, b.tail))
    }

    f(s1, s2)
  }

最后，是典型的斐波那契示例:

And lastly, the canonical fibonacci example:

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

println(fib(100))

这篇关于Scala备忘:此Scala备忘如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！