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

Question

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

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

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

Answer 1

Вы можете использовать mutable.Map[TupleN[A1, A2, ..., AN], R] или, если проблема с памятью, WeakHashMap [1].Приведенные ниже определения (основанные на коде памятки из блога 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) позволяет запоминать рекурсивные функции:

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 и этот связанный вопрос .

Answer 2

Версия, предложенная 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))   
}

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

Answer 3

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

Работает отлично.Буду признателен за критику, если я что-то пропустил.

Answer 4

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

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

В дополнение к ответу Ландеи, я также хочу предложить восходящий (не запоминание) способ выполнения DP в Scala, и основная идея заключается в использовании 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
}