que - ¿Qué tipo usar para almacenar una tabla de datos mutables en la memoria en Scala?

por que string es inmutable

Question

Cada vez que se llama a una función, si todavía no se ha memorizado el resultado para un conjunto dado de valores de argumento, me gustaría poner el resultado en una tabla en la memoria. Una columna está destinada a almacenar un resultado, otras a almacenar valores de argumentos.

¿Cómo mejor implemento esto? Los argumentos son de diversos tipos, incluidas algunas enumeraciones.

En C # generalmente usaría DataTable. ¿Hay un equivalente en Scala?

Answer 1

La versión sugerida por anovstrup usando un mapa mutable es básicamente la misma que en C # y, por lo tanto, es fácil de usar.

Pero si lo desea, también puede usar un estilo más funcional. Utiliza mapas inmutables, que actúan como una especie de accumalator. Tener Tuples (en lugar de Int en el ejemplo) como teclas funciona exactamente como en el caso mutable.

def fib(n:Int) = fibM(n, Map(0->1, 1->1))._1
def fibM(n:Int, m:Map[Int,Int]):(Int,Map[Int,Int]) = m.get(n) match {
case Some(f) => (f, m)
case None => val (f_1,m1) = fibM(n-1,m)
val (f_2,m2) = fibM(n-2,m1)
val f = f_1+f_2
(f, m2 + (n -> f))
}

Por supuesto, esto es un poco más complicado, pero una técnica útil para saber (tenga en cuenta que el código anterior apunta a la claridad, no a la velocidad).

Answer 2

Siendo un novato en este tema, pude entender completamente ninguno de los ejemplos dados (pero me gustaría agradecer de todos modos). Respetuosamente, presentaría mi propia solución para el caso, alguien viene aquí con el mismo nivel y el mismo problema. Creo que mi código puede ser muy claro para cualquiera que tenga el conocimiento muy básico de Scala .

def MyFunction(dt : DateTime, param : Int) : Double
{
val argsTuple = (dt, param)
if(Memo.contains(argsTuple)) Memo(argsTuple) else Memoize(dt, param, MyRawFunction(dt, param))
}
def MyRawFunction(dt : DateTime, param : Int) : Double
{
1.0 // A heavy calculation/querying here
}
def Memoize(dt : DateTime, param : Int, result : Double) : Double
{
Memo += (dt, param) -> result
result
}
val Memo = new scala.collection.mutable.HashMap[(DateTime, Int), Double]

Funciona perfectamente. Apreciaría la crítica si me he perdido algo.

Answer 3

Además de la respuesta de Landei, también quiero sugerir que la manera de hacer DP desde abajo hacia arriba (sin memorización) es posible en Scala, y la idea central es usar foldLeft (s).

Ejemplo para calcular los números de Fibonacci

 def fibo(n: Int) = (1 to n).foldLeft((0, 1)) {
(acc, i) => (acc._2, acc._1 + acc._2)
}._1

Ejemplo para la subsecuencia creciente más larga

def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
xs.foldLeft(List[(Int, List[T])]()) {
(memo, x) =>
if (memo.isEmpty) List((1, List(x)))
else {
val resultIfEndsAtCurr = (memo, xs).zipped map {
(tp, y) =>
val len = tp._1
val seq = tp._2
if (ord.lteq(y, x)) { // current is greater than the previous end
(len + 1, x :: seq) // reversely recorded to avoid O(n)
} else {
(1, List(x)) // start over
}
}
memo :+ resultIfEndsAtCurr.maxBy(_._1)
}
}.maxBy(_._1)._2.reverse
}

Answer 4

Al usar un mapa mutable para la memorización, se debe tener en cuenta que esto causaría problemas típicos de simultaneidad, por ejemplo, hacer un get cuando una escritura no se haya completado aún. Sin embargo, el intento de memorización de subprocesos sugiere que tiene poco valor si no ninguno.

El siguiente código de seguridad de subprocesos crea una función de Fonacacci memorada, inicia un par de subprocesos (denominados de ''a'' a ''d'') que hacen llamadas a él. Pruebe el código un par de veces (en REPL), se puede ver fácilmente que f(2) set se imprime más de una vez. Esto significa que un hilo A ha iniciado el cálculo de f(2) pero el hilo B no tiene idea de ello y comienza su propia copia del cálculo. Tal ignorancia es tan generalizada en la fase de construcción de la memoria caché, porque todos los hilos ven que no se ha establecido una solución secundaria y entrarían en la cláusula else .

object ScalaMemoizationMultithread {
// do not use case class as there is a mutable member here
class Memo[-T, +R](f: T => R) extends (T => R) {
// don''t even know what would happen if immutable.Map used in a multithreading context
private[this] val cache = new java.util.concurrent.ConcurrentHashMap[T, R]
def apply(x: T): R =
// no synchronized needed as there is no removal during memoization
if (cache containsKey x) {
Console.println(Thread.currentThread().getName() + ": f(" + x + ") get")
cache.get(x)
} else {
val res = f(x)
Console.println(Thread.currentThread().getName() + ": f(" + x + ") set")
cache.putIfAbsent(x, res) // atomic
res
}
}
object Memo {
def apply[T, R](f: T => R): T => R = new Memo(f)
def Y[T, R](F: (T => R) => T => R): T => R = {
lazy val yf: T => R = Memo(F(yf)(_))
yf
}
}
val fibonacci: Int => BigInt = {
def fiboF(f: Int => BigInt)(n: Int): BigInt = {
if (n <= 0) 1
else if (n == 1) 1
else f(n - 1) + f(n - 2)
}
Memo.Y(fiboF)
}
def main(args: Array[String]) = {
(''a'' to ''d'').foreach(ch =>
new Thread(new Runnable() {
def run() {
import scala.util.Random
val rand = new Random
(1 to 2).foreach(_ => {
Thread.currentThread().setName("Thread " + ch)
fibonacci(5)
})
}
}).start)
}
}

Answer 5

Puede usar un mutable.Map[TupleN[A1, A2, ..., AN], R] , o si la memoria es una preocupación, un WeakHashMap [1]. Las definiciones a continuación (basadas en el código de memorización del blog de michid ) le permiten memorizar fácilmente funciones con múltiples argumentos. Por ejemplo:

import Memoize._
def reallySlowFn(i: Int, s: String): Int = {
Thread.sleep(3000)
i + s.length
}
val memoizedSlowFn = memoize(reallySlowFn _)
memoizedSlowFn(1, "abc") // returns 4 after about 3 seconds
memoizedSlowFn(1, "abc") // returns 4 almost instantly

Definiciones:

/**
* A memoized unary function.
*
* @param f A unary function to memoize
* @param [T] the argument type
* @param [R] the return type
*/
class Memoize1[-T, +R](f: T => R) extends (T => R) {
import scala.collection.mutable
// map that stores (argument, result) pairs
private[this] val vals = mutable.Map.empty[T, R]
// Given an argument x,
// If vals contains x return vals(x).
// Otherwise, update vals so that vals(x) == f(x) and return f(x).
def apply(x: T): R = vals getOrElseUpdate (x, f(x))
}
object Memoize {
/**
* Memoize a unary (single-argument) function.
*
* @param f the unary function to memoize
*/
def memoize[T, R](f: T => R): (T => R) = new Memoize1(f)
/**
* Memoize a binary (two-argument) function.
*
* @param f the binary function to memoize
*
* This works by turning a function that takes two arguments of type
* T1 and T2 into a function that takes a single argument of type
* (T1, T2), memoizing that "tupled" function, then "untupling" the
* memoized function.
*/
def memoize[T1, T2, R](f: (T1, T2) => R): ((T1, T2) => R) =
Function.untupled(memoize(f.tupled))
/**
* Memoize a ternary (three-argument) function.
*
* @param f the ternary function to memoize
*/
def memoize[T1, T2, T3, R](f: (T1, T2, T3) => R): ((T1, T2, T3) => R) =
Function.untupled(memoize(f.tupled))
// ... more memoize methods for higher-arity functions ...
/**
* Fixed-point combinator (for memoizing recursive functions).
*/
def Y[T, R](f: (T => R) => T => R): (T => R) = {
lazy val yf: (T => R) = memoize(f(yf)(_))
yf
}
}

El combinador de punto fijo ( Memoize.Y ) hace posible memorizar funciones recursivas:

val fib: BigInt => BigInt = {
def fibRec(f: BigInt => BigInt)(n: BigInt): BigInt = {
if (n == 0) 1
else if (n == 1) 1
else (f(n-1) + f(n-2))
}
Memoize.Y(fibRec)
}

[1] WeakHashMap no funciona bien como un caché. Consulte http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html y esta pregunta relacionada .