Какой тип использовать для хранения измененной таблицы данных в памяти в Scala?

Каждый раз, когда вызывается функция, если результат для данного набора значений аргументов еще не сохранен, я хотел бы поместить результат в таблицу в памяти. Один столбец предназначен для хранения результата, другие – для хранения значений аргументов.

Как лучше всего реализовать это? Аргументы имеют разные типы, включая некоторые enums.

В C # я обычно использовал DataTable. Есть ли эквивалент в Scala?

Вы можете использовать mutable.Map[TupleN[A1, A2, ..., AN], R] , или если память является проблемой, WeakHashMap [1]. Нижеприведенные определения (построенные на блоке memoization из блога michid ) позволяют легко запоминать функции с несколькими аргументами. Например:

 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 

Определения:

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

Комбинатор с фиксированной запятой ( Memoize.Y ) позволяет Memoize.Y рекурсивные функции:

 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 работает не так, как кеш. См. http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html и этот связанный с этим вопрос .

Версия, предложенная anovstrup с использованием измененной карты, в основном такая же, как и на C #, и поэтому проста в использовании.

Но если вы хотите, вы также можете использовать более функциональный стиль. Он использует неизменные карты, которые действуют как своего рода накопитель. Наличие Tuples (вместо Int в примере) в качестве ключей работает точно так же, как в изменчивом случае.

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

Конечно, это немного сложнее, но полезный метод, чтобы знать (обратите внимание, что вышеприведенный код направлен на ясность, а не на скорость).

Будучи новичком в этом вопросе, я не мог полностью понять ни один из приведенных примеров (но хотел бы поблагодарить в любом случае). С уважением, я представляю свое собственное решение для случая, когда кто-то приходит сюда с одинаковым уровнем и той же проблемой. Я думаю, что мой код может быть кристально чистым для любого, у кого есть только очень-очень базовое знание 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]
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] 

Работает отлично. Я был бы признателен за критику. Если я что-то пропустил.

При использовании изменчивой карты для memoization следует иметь в виду, что это может вызвать типичные проблемы параллелизма, например, делать, когда запись еще не завершена. Тем не менее, streamобезопасная проверка memoization предлагает сделать так, что это малозначительно, если нет.

Следующий поточно-безопасный код создает memoized функцию fibonacci , инициирует пару streamов (от «a» до «d»), которые совершают вызовы. Попробуйте код пару раз (в REPL), можно легко увидеть, что f(2) set печатается несколько раз. Это означает, что stream A инициировал вычисление f(2) но Thread B полностью не знает об этом и запускает собственную копию расчета. Такое незнание настолько широко распространено на этапе построения кэша, потому что все streamи не видят никакого суб-решения и будут вводить условие 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) } } 

В дополнение к ответам Landei, я также хочу предположить, что возможный DP- foldLeft в Scala может быть снизу вверх (не memoization), и основной идеей является использование foldLeft (s).

Пример вычисления чисел Фибоначчи

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

Пример для самой длинной увеличивающейся подпоследовательности

 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 } 
  • Нечитаемая только альтернатива анонимным типам
  • Эффективность STL priority_queue
  • Разделить список в подсписках с помощью LINQ
  • Давайте будем гением компьютера.