[SCALA] 스칼라 메모이 제이션 : 어떻게이 스칼라 메모 작동합니까?

스칼라 메모이 제이션 : 어떻게이 스칼라 메모 작동합니까?

다음 코드는 Pathikrit의 동적 프로그래밍 저장소에서입니다. 나는 그 아름다움과 특색 모두에 의해 신비화하고 있습니다.

def subsetSum(s: List[Int], t: Int) = {
  type DP = Memo[(List[Int], Int), (Int, Int), Seq[Seq[Int]]]
  implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)

  lazy val f: DP = Memo {
    case (Nil, 0) => Seq(Nil)
    case (Nil, _) => Nil
    case (a :: as, x) => (f(as, x - a) map {_ :+ a}) ++ f(as, x)
  }

  f(s, t)
}

유형 메모는 다른 파일에 구현되어 있습니다 :

case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
  import collection.mutable.{Map => Dict}
  val cache = Dict.empty[K, O]
  override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}

내 질문이 있습니다 :

3. 방법 (목록 [지능, 지능)의 암시 (INT, INT)로 변환합니까? = (x._1.toInt, x._2) : 나는 암시 데프 foo는 ((목록 [지능], INT) X)를 볼 수 없습니다. (조차 Implicits.scala 파일에 그것을 가져옵니다.

* 편집 : 글쎄, 난이 그리워 :

implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)

난 아주 많이 Pathikrit의 라이브러리 scalgos을 즐길 수 있습니다. 거기에 스칼라 진주 많이 있습니다. 내가 Pathikrit의 재치를 감상 할 수 있도록이 저를 도와주세요. 감사합니다. (:

해결법

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

   1.나는 위의 코드의 저자입니다.

   나는 위의 코드의 저자입니다.

   /**
    * Generic way to create memoized functions (even recursive and multiple-arg ones)
    *
    * @param f the function to memoize
    * @tparam I input to f
    * @tparam K the keys we should use in cache instead of I
    * @tparam O output of f
    */
   case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
     import collection.mutable.{Map => Dict}
     type Input = I
     type Key = K
     type Output = O
     val cache = Dict.empty[K, O]
     override def apply(x: I) = cache getOrElseUpdate (x, f(x))
   }
   
   object Memo {
     /**
      * Type of a simple memoized function e.g. when I = K
      */
     type ==>[I, O] = Memo[I, I, O]
   }
   

   메모에서는 [I <% K, K, O] :

   I: input
   K: key to lookup in cache
   O: output
   

   선 I는 K는 K가 I.에서 (즉, 암시 적 변환)를 볼 수있다 %를 의미 <

   대부분의 경우, 나는해야한다 K 예를 들어, 당신이 형 지능의 함수이다 피보나치를 작성하는 경우 => 지능, 그것은 지능 그 자체로 캐시에 괜찮습니다.

   당신이 메모이 제이션을 작성하는 때, 때때로, 당신은 항상 (목록을 memoize 또는 입력 자체 (내가)에 의해 캐시 아니라 입력 (K) 예를 들어, 당신은 유형의 입력을 가진 subsetSum 알고리즘을 작성하는 기능 싶지 않아 [지능, 지능은), 당신은 목록 [지능]를 사용하지 않으려는 캐시에있는 키의 일부로서 캐시에 키가 아니라 당신이 원하는 사용 목록 [지능] 크기는있다.

   그래서, 여기에 구체적인 사례는 다음과 같습니다

   /**
    * Subset sum algorithm - can we achieve sum t using elements from s?
    * O(s.map(abs).sum * s.length)
    *
    * @param s set of integers
    * @param t target
    * @return true iff there exists a subset of s that sums to t
    */
    def isSubsetSumAchievable(s: List[Int], t: Int): Boolean = {
       type I = (List[Int], Int)     // input type
       type K = (Int, Int)           // cache key i.e. (list.size, int)
       type O = Boolean              // output type      
   
       type DP = Memo[I, K, O]
   
       // encode the input as a key in the cache i.e. make K implicitly convertible from I
       implicit def encode(input: DP#Input): DP#Key = (input._1.length, input._2)   
   
       lazy val f: DP = Memo {
         case (Nil, x) => x == 0      // an empty sequence can only achieve a sum of zero
         case (a :: as, x) => f(as, x - a) || f(as, x)      // try with/without a.head
       }
   
       f(s, t)
    }
   

   당신은 당연히 한 줄에 모든이 단축 될 수 있습니다 : 메모 DP = [(리스트 [지능, INT) (INT, INT), 부울] 입력

   일반적인 경우 (내가 K를 =시)의 경우, 당신은 단순히이 수행 할 수 있습니다 유형을 ==> [I, O = 메모 [I, I, O] 재귀 메모이 제이션과 이항 COEFF을 계산하기 위해 다음과 같이 사용 :

     /**
      * http://mathworld.wolfram.com/Combination.html
      * @return memoized function to calculate C(n,r)
      */
     val c: (Int, Int) ==> BigInt = Memo {
       case (_, 0) => 1
       case (n, r) if r > n/2 => c(n, n - r)
       case (n, r) => c(n - 1, r - 1) + c(n - 1, r)
     }
   

   어떻게 작동하는지 위의 구문 세부 사항을 확인하려면,이 질문을 참조하시기 바랍니다.

   여기서 (Seq.length, Seq.length)에 입력 (서열, 서열) 모두의 파라미터를 부호화하여 editDistance을 계산하는 전체 예이다 :

    /**
      * Calculate edit distance between 2 sequences
      * O(s1.length * s2.length)
      *
      * @return Minimum cost to convert s1 into s2 using delete, insert and replace operations
      */
     def editDistance[A](s1: Seq[A], s2: Seq[A]) = {
   
       type DP = Memo[(Seq[A], Seq[A]), (Int, Int), Int]
       implicit def encode(key: DP#Input): DP#Key = (key._1.length, key._2.length)
   
       lazy val f: DP = Memo {
         case (a, Nil) => a.length
         case (Nil, b) => b.length
         case (a :: as, b :: bs) if a == b => f(as, bs)
         case (a, b) => 1 + (f(a, b.tail) min f(a.tail, b) min f(a.tail, b.tail))
       }
   
       f(s1, s2)
     }
   

   그리고 마지막으로, 정규 피보나치 예 :

   lazy val fib: Int ==> BigInt = Memo {
     case 0 => 0
     case 1 => 1
     case n if n > 1 => fib(n-1) + fib(n-2)
   }
   
   println(fib(100))
   

from https://stackoverflow.com/questions/25129721/scala-memoization-how-does-this-scala-memo-work by cc-by-sa and MIT license