[SCALA] 어떤 종류의 스칼라에서 메모리 가변 데이터 테이블을 저장하기 위해 사용하는 방법?

어떤 종류의 스칼라에서 메모리 가변 데이터 테이블을 저장하기 위해 사용하는 방법?

아직 내가 메모리 테이블에 결과를 넣어 싶습니다 memoized되지 않은 인수 값의 주어진 집합에 대한 결과 않다면마다 함수가 호출된다. 한 열이 인수 값을 저장하기 위해, 다른 결과를 저장하기위한 것입니다.

내가 가장이 어떻게 구현합니까? 인수는 몇 가지 열거 형 등 다양한 유형의이다.

C #에서 나는 일반적 거라고 DataTable을 사용합니다. 스칼라에 해당하는이 있습니까?

해결법

1. ==============================

   1.당신은 mutable.Map [TupleN [A1, A2, ...,], R]를 사용하거나 수있는 메모리가 우려하는의 WeakHashMap 인 경우 [1]. (michid의 블로그에서 메모이 제이션 코드에 내장) 아래의 정의는 쉽게 여러 인수 기능을 memoize 수 있습니다. 예를 들면 :

   당신은 mutable.Map [TupleN [A1, A2, ...,], R]를 사용하거나 수있는 메모리가 우려하는의 WeakHashMap 인 경우 [1]. (michid의 블로그에서 메모이 제이션 코드에 내장) 아래의 정의는 쉽게 여러 인수 기능을 memoize 수 있습니다. 예를 들면 :

   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. ==============================

   2.변경 가능한지도를 사용 anovstrup 제안 버전은 기본적으로 C #에서와 동일하고 사용하는 것이 편리합니다.

   변경 가능한지도를 사용 anovstrup 제안 버전은 기본적으로 C #에서와 동일하고 사용하는 것이 편리합니다.

   하지만 당신은 또한뿐만 아니라 더 많은 기능 스타일을 사용할 수 원하는 경우. 그것은 accumalator의 일종으로 역할을 불변의 맵을 사용합니다. 키로 (예 대신이 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. ==============================

   3.이 주제에 초보자이기 때문에, 나는 완전히 주어진 예제 전혀 이해할 수 없었다 (그러나 어쨌든 감사드립니다). 정중하게, 나는 어떤 사람이 동일한 수준과 같은 문제가 여기에 오는 경우에 대한 내 자신의 솔루션을 제시 것입니다. 내 코드는 사람이 바로 아주 - 아주 기본적인 스칼라 지식이 명확한 결정이 될 수 있다고 생각합니다.

   이 주제에 초보자이기 때문에, 나는 완전히 주어진 예제 전혀 이해할 수 없었다 (그러나 어쨌든 감사드립니다). 정중하게, 나는 어떤 사람이 동일한 수준과 같은 문제가 여기에 오는 경우에 대한 내 자신의 솔루션을 제시 것입니다. 내 코드는 사람이 바로 아주 - 아주 기본적인 스칼라 지식이 명확한 결정이 될 수 있다고 생각합니다.

   
   
   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. ==============================

   4.메모이 제이션에 대한 변경 가능한 맵을 사용하는 경우, 하나는이 예를 들어, 일반적인 동시성 문제가 발생할 것이라는 점을 명심하여야한다 쓰기가 아직 완료되지 않은 경우 GET을하고. None이 아니라면 그것은 작은 가치 그래서 그러나 메모이 제이션의 스레드 안전이 시도는 할 제안합니다.

   메모이 제이션에 대한 변경 가능한 맵을 사용하는 경우, 하나는이 예를 들어, 일반적인 동시성 문제가 발생할 것이라는 점을 명심하여야한다 쓰기가 아직 완료되지 않은 경우 GET을하고. None이 아니라면 그것은 작은 가치 그래서 그러나 메모이 제이션의 스레드 안전이 시도는 할 제안합니다.

   다음 스레드 안전 코드가하는 memoized 피보나치 함수를 만듭니다 스레드의 몇 시작 (에서 이름을 'A' 'D'에 이르기까지)이 호출을합니다. 코드를 (REPL에서) 몇 번을 시도, 하나는 쉽게 F (2) 세트가 두 번 이상 인쇄됩니다 볼 수 있습니다. 이것은 스레드 A (2) F의 계산을 시작하지만, B는 전혀 모르고있다 계산의 복사본을 시작 스레드 의미합니다. 모든 스레드가 설립에는 하위 솔루션을 볼 수없고, 다른 절을 입력하기 때문에 이러한 무지는 캐시의 건설 단계에서 너무 만연이다.

   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. ==============================

   5.Landei의 대답 이외에, 나는 또한 스칼라에서 DP를하는 상향식 (비 메모이 제이션) 방법을 제안하고자하는 것은 가능하며, 핵심 아이디어는 foldLeft (들)을 사용하는 것입니다.

   Landei의 대답 이외에, 나는 또한 스칼라에서 DP를하는 상향식 (비 메모이 제이션) 방법을 제안하고자하는 것은 가능하며, 핵심 아이디어는 foldLeft (들)을 사용하는 것입니다.

   피보나치 수열을 계산하는 실시 예

     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
   }
   

from https://stackoverflow.com/questions/3640823/what-type-to-use-to-store-an-in-memory-mutable-data-table-in-scala by cc-by-sa and MIT license