Quale tipo utilizzare per memorizzare una tabella di dati mutabili in memoria in Scala?

Ogni volta che viene chiamata una funzione, se il risultato per un dato insieme di valori di argomento non è ancora memoized, mi piacerebbe inserire il risultato in una tabella in memoria. Una colonna è pensata per memorizzare un risultato, altri per memorizzare i valori degli argomenti.

Come faccio a implementarlo al meglio? Gli argomenti sono di vario tipo, inclusi alcuni enumerati.

In C # generalmente uso DataTable. Esiste un equivalente in Scala?

Potresti usare un mutable.Map[TupleN[A1, A2, ..., AN], R] , o se la memoria è un problema, una WeakHashMap [1]. Le definizioni seguenti (create sul codice di memoizzazione dal blog di michid ) consentono di memorizzare facilmente funzioni con più argomenti. Per esempio:

 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 

definizioni:

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

Il combinatore a virgola fissa ( Memoize.Y ) consente di memoizzare le funzioni ricorsive:

 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 non funziona bene come cache. Vedi http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html e questa domanda correlata .

La versione suggerita da anovstrup usando una mappa mutevole è fondamentalmente la stessa di C #, e quindi facile da usare.

Ma se vuoi puoi anche usare uno stile più funzionale. Usa mappe immutabili, che agiscono come una specie di accumulatore. Avere Tuple (invece di Int nell’esempio) come chiavi funziona esattamente come nel caso mutabile.

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

Certo, questo è un po ‘più complicato, ma una tecnica utile da sapere (si noti che il codice sopra mira alla chiarezza, non alla velocità).

Essendo un principiante in questo argomento, ho potuto comprendere appieno nessuno degli esempi forniti (ma vorrei comunque ringraziarlo). Rispettosamente, presenterei la mia soluzione per il caso che qualcuno viene qui con lo stesso livello e lo stesso problema. Penso che il mio codice possa essere chiaro per chiunque abbia solo la conoscenza di base molto semplice .

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

Funziona perfettamente. Apprezzerei la critica se mi fosse sfuggito qualcosa.

Quando si utilizza la mappa mutevole per la memoizzazione, si deve tenere presente che ciò causerebbe problemi di concorrenza tipici, ad es. Un get quando una scrittura non è ancora stata completata. Tuttavia, il tentativo di memoizzazione thread-safe suggerisce di farlo è di poco valore se non nessuno.

Il seguente codice thread-safe crea una funzione fibonacci memoized, avvia un paio di thread (denominati da ‘a’ a ‘d’) che effettuano chiamate su di esso. Prova il codice un paio di volte (in REPL), si può facilmente vedere che il f(2) set viene stampato più di una volta. Questo significa che un thread A ha iniziato il calcolo di f(2) ma Thread B non ne ha idea e inizia la propria copia di calcolo. Tale ignoranza è così pervasiva nella fase di costruzione della cache, perché tutti i thread non vedono alcuna soluzione secondaria stabilita e entrerebbero nella clausola 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) } } 

Oltre alla risposta di Landei, voglio anche suggerire che è ansible utilizzare il foldLeft bottom-up (non-memoization) di DP in Scala, e l’idea di base è usare foldLeft (s).

Esempio per calcolare i numeri di Fibonacci

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

Esempio per sottosequenze crescenti più lunghe

 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 }