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

Question

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

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

En C# En general, utilizaría DataTable. ¿Hay un equivalente en Scala?

Answer 1

Se puede usar un mutable.Map[TupleN[A1, A2, ..., AN], R] , o si la memoria no es una preocupación, un WeakHashMap [1]. Las definiciones a continuación (basadas en el código de memoria de michid's blog) 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 memoize 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é Ver http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html y this related question.

Answer 2

La versión sugerida por anovstrup utilizando 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 utilizar 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 tiene como objetivo para una mayor claridad, no para la velocidad).

Answer 3

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 solo the very-very basic Scala knowledge.

 


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 4

Al utilizar mapa mutable para la memorización, se debe tener en cuenta que esto causaría problemas típicos de simultaneidad, p. Ej. haciendo un get cuando una escritura no se ha completado todavía. 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 memorada fibonacci, inicia un par de subprocesos (llamados 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 omnipresente en la fase de construcción de la memoria caché, porque todos los hilos no ven una solución secundaria establecida e ingresarían 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

Además de la respuesta de Landei, también quiero sugerir la de abajo hacia arriba (no memoization) forma de hacer DP en Scala es posible, y la idea central es utilizar foldLeft (s).

Ejemplo para el cálculo de 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 aumentar más larga subsecuencia

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 
}