Mémoization Scala: Comment fonctionne ce mémo Scala?
le code suivant est tiré de Pathikrit's Dynamic Programming repository. Je suis mystifié par sa beauté et sa particularité.
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)
}
le type Memo
est implémenté dans un autre fichier:
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))
}
mes questions sont:
-
pourquoi
type K
est-il déclaré comme(Int, Int)
dans subsetSum? -
que signifie
int
dans(Int, Int)
respectivement?
3. Comment (List[Int], Int)
se transforme-t-il implicitement en (Int, Int)
?
Je ne vois pas implicit def foo(x:(List[Int],Int)) = (x._1.toInt,x._2)
. ( pas même dans le Implicits.scala
fichier des importations.
*Edit: bon, je m'ennuie de cette:
implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)
j'aime Pathikrit de la bibliothèque de l' scalgos très bien. Il y a beaucoup de perles de Scala dedans. Aidez-moi avec ça pour que je puisse apprécier L'esprit de Pathikrit. Remercier. (:
1 réponses
je suis l'auteur du ci-dessus code .
/**
* 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]
}
Dans Memo[I <% K, K, O]
:
I: input
K: key to lookup in cache
O: output
la ligne I <% K
signifie que K
peut être visible (c'est-à-dire converti implicitement) de I
.
dans la plupart des cas, I
devrait être K
par exemple , si vous écrivez fibonacci
qui est une fonction de type Int => Int
, il est d'accord pour mettre en cache par Int
lui-même.
Mais, parfois, quand vous écrivez memoization, vous ne voulez pas toujours memoize ou cache de l'entrée elle-même ( I
), mais plutôt une fonction de l'entrée ( K
) e.g lorsque vous écrivez subsetSum
algorithme qui a une entrée de type (List[Int], Int)
, vous ne voulez pas utiliser List[Int]
comme clé dans votre cache, mais plutôt que vous voulez utiliser List[Int].size
comme la partie de la clé dans votre cache.
donc, voici un cas concret:
/**
* 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)
}
vous pouvez bien sûr raccourcir tous ces en une seule ligne:
type DP = Memo[(List[Int], Int), (Int, Int), Boolean]
pour le cas commun (quand I = K
), vous pouvez simplement faire ceci: type ==>[I, O] = Memo[I, I, O]
et l'utiliser comme ceci pour calculer le coeff binomial avec mémoization récursive:
/**
* 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)
}
pour voir les détails comment la syntaxe ci-dessus fonctionne, s'il vous plaît se référer à cette question .
voici un exemple complet qui calcule editDistance en encodant les deux paramètres de l'entrée (Seq, Seq)
à (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)
}
et enfin, l'exemple canonique de fibonacci:
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))