Scala记忆化：这个Scala记忆化是如何工作的？

Question

以下代码来自Pathikrit的动态规划存储库。我对它的美丽和奇特感到困惑。

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类型在另一个文件中实现：

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)？

2. (Int, Int)中的int分别代表什么意思？

3. (List[Int], Int)如何隐式转换为(Int, Int)？
我没有看到implicit def foo(x:(List[Int],Int)) = (x._1.toInt,x._2)。（即使在它导入的Implicits.scala文件中也没有。）

*编辑：好吧，我错过了这个：

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

我非常喜欢Pathikrit的scalgos库。里面有很多Scala珍珠。请帮我理解这个，这样我就能欣赏Pathikrit的智慧了。谢谢。(:

- Yun-Chih Chen

---

关于＃3，您忘记读取带有implicit def encode的行。 - pathikrit

我看到了这个问题在这里，但我仍然想知道值f是否真的进行了记忆化？似乎每次调用subsetSum时，都会创建一个新的Memo实例，而不是我们想要的最后一个memo。这是真的吗？ - Yun-Chih Chen

是的，对于给定的s和t，它返回一个Memo对象。如果之前已经计算过，那么对该Memo对象的进一步调用将是O(1)的。您可以通过编写一个简单的斐波那契记忆化函数来验证自己，例如：lazy val factorial: Int ==> BigInt = Memo { case 0 => 1 case n => n * factorial(n - 1) } - pathikrit

说服自己的另一种方法是将此行放入Memo.scala中：cache getOrElseUpdate (x，（y）=> println（s“Cache miss：$ y”）; f（y）） - pathikrit

使用动态规划计算值并返回f(s, t)与返回动态程序（即对s和t进行记忆化的闭包）即返回f本身是有区别的。请参见我在此处对您的回复。 - pathikrit

Answer 1

我是上面代码的作者。

/**
 * Generic way to create memoized functions (even recursive and multiple-arg ones)
 *
 * @param f the function to memoize
 * @tparam I input to f
 * @tparam K the keys we should use in cache instead of I
 * @tparam O output of f
 */
case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
  import collection.mutable.{Map => Dict}
  type Input = I
  type Key = K
  type Output = O
  val cache = Dict.empty[K, O]
  override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}

object Memo {
  /**
   * Type of a simple memoized function e.g. when I = K
   */
  type ==>[I, O] = Memo[I, I, O]
}

在Memo[I <% K, K, O]中：

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

这行代码 I <% K 的意思是可以从 I 隐式转换为 viewable（即可视为）K。

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

但是，在编写记忆化时，有时您不希望始终通过输入本身 (I) 进行记忆化或缓存，而是要使用输入的函数 (K) 的一部分作为 key，例如当您编写具有类型 (List[Int], Int) 的 subsetSum 算法时，您不想将 List[Int] 用作缓存中的键，而是想使用 List[Int].size 作为缓存中的键的一部分。

因此，这里有一个具体的案例：

/**
 * 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] 对于常见情况（当I = K时），你可以简单地这样做：type ==>[I, O] = Memo[I, I, O]，并像这样使用递归记忆化来计算二项式系数。

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

如需了解以上语法的详细信息，请参考此问题。

以下是一个完整的示例，它通过将输入(Seq，Seq)的两个参数编码为(Seq.length, Seq.length)来计算editDistance：

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

最后，经典的斐波那契例子：

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))

- pathikrit

---

非常好的工作。只有一件事：由于Memo包含具有移动哈希的成员，因此不应在此处使用case class。 - lcn

我可以在哪里找到关于==> 符号的内容？ - Krever

@Krever：看一下这行代码：type ==>[I, O] = Memo[I, I, O] 通常这些被称为“中缀类型”。参考：https://dev59.com/D3A75IYBdhLWcg3wm6ex - pathikrit

@ipburbank：因为f在其自身定义中引用了自己。 - pathikrit

@pathikrit，为什么不使用scala.collection.concurrent.TrieMap？ - Noel Yap