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

Ответ 1

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

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 рекурсивные функции:

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

Ответ 2

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

Но если вы хотите, вы также можете использовать более функциональный стиль. Он использует неизменные карты, которые действуют как своего рода накопитель. Наличие 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))   
}

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

Ответ 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]

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

Ответ 4

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

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

Ответ 5

В дополнение к ответам Landei, я также хочу предположить, что возможен снимок (не memoization) для 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
}