[SCALA] 스칼라에서 memoize하는 일반적인 방법이 있나요?

스칼라에서 memoize하는 일반적인 방법이 있나요?

나는 이것을 memoize 싶었 :

def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)
println(fib(100)) // times out

내가 쓴이 놀라 울 정도로 컴파일하고 작품 그래서 (나는 FIB 자체를 참조 선언에 있기 때문에 놀라게하고있다)

case class Memo[A,B](f: A => B) extends (A => B) {
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A) = cache getOrElseUpdate (x, f(x))
}

val fib: Memo[Int, BigInt] = Memo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-1) + fib(n-2) 
}

println(fib(100))     // prints 100th fibonacci number instantly

내가 데프의 FIB의 내부를 선언 할 때, 나는 컴파일러 오류가 발생합니다 :

def foo(n: Int) = {
  val fib: Memo[Int, BigInt] = Memo {
    case 0 => 0
    case 1 => 1
    case n => fib(n-1) + fib(n-2) 
  }
  fib(n)
} 

위 오류를 컴파일에 실패 : 전방 참조 값의 FIB의 정의를 통해 확장 는 n => FIB (N-1) + FIB (N-2)

다음 DEF 클래스 / 객체 범위 작동에 실패하지만, 외부에서 내부에 왜 발에 FIB를 선언 하는가?

나는 데프 범위에서 재귀 memoized 함수를 선언 할 수 있습니다 이유를 명확히하기 위해 - 여기 부분 집합 합 문제에 대한 내 솔루션입니다 :

/**
   * Subset sum algorithm - can we achieve sum t using elements from s?
   *
   * @param s set of integers
   * @param t target
   * @return true iff there exists a subset of s that sums to t
   */
  def subsetSum(s: Seq[Int], t: Int): Boolean = {
    val max = s.scanLeft(0)((sum, i) => (sum + i) max sum)  //max(i) =  largest sum achievable from first i elements
    val min = s.scanLeft(0)((sum, i) => (sum + i) min sum)  //min(i) = smallest sum achievable from first i elements

    val dp: Memo[(Int, Int), Boolean] = Memo {         // dp(i,x) = can we achieve x using the first i elements?
      case (_, 0) => true        // 0 can always be achieved using empty set
      case (0, _) => false       // if empty set, non-zero cannot be achieved
      case (i, x) if min(i) <= x && x <= max(i) => dp(i-1, x - s(i-1)) || dp(i-1, x)  // try with/without s(i-1)
      case _ => false            // outside range otherwise
    }

    dp(s.length, t)
  }

해결법

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

   1.나는 스칼라를 사용하여 memoize 수있는 더 좋은 방법을 발견 :

   나는 스칼라를 사용하여 memoize 수있는 더 좋은 방법을 발견 :

   def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {
     override def apply(key: I) = getOrElseUpdate(key, f(key))
   }
   

   다음과 같이 이제 피보나치을 작성할 수 있습니다 :

   lazy val fib: Int => BigInt = memoize {
     case 0 => 0
     case 1 => 1
     case n => fib(n-1) + fib(n-2)
   }
   

   여기에 여러 인수합니다 (기능 선택) 하나입니다 :

   lazy val c: ((Int, Int)) => BigInt = memoize {
     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)
   }
   

   그리고 여기에 집합 합 문제는 다음과 같습니다

   // is there a subset of s which has sum = t
   def isSubsetSumAchievable(s: Vector[Int], t: Int) = {
     // f is (i, j) => Boolean i.e. can the first i elements of s add up to j
     lazy val f: ((Int, Int)) => Boolean = memoize {
       case (_, 0) => true        // 0 can always be achieved using empty list
       case (0, _) => false       // we can never achieve non-zero if we have empty list
       case (i, j) => 
         val k = i - 1            // try the kth element
         f(k, j - s(k)) || f(k, j)
     }
     f(s.length, t)
   }
   

   편집 :로, 여기 아래에 설명 스레드 안전 버전입니다

   def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {self =>
     override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key)))
   }
   

2. ==============================

   2.클래스 / 방법 및 개인 변수의 조합에 특성 수준 발 컴파일. 따라서 재귀 정의가 허용됩니다.

   클래스 / 방법 및 개인 변수의 조합에 특성 수준 발 컴파일. 따라서 재귀 정의가 허용됩니다.

   반면에 지역 발스는 일반 변수, 따라서 재귀 적 정의는 허용되지 않습니다.

   그런데, 데프 당신이 일을 정의 된 경우에도, 당신이 무엇을 기대하지 않을 것입니다. foo는 모든 호출에 새로운 함수 객체의 FIB가 만들어지고 그것의 자신있는 맵이있을 것이다. (당신은 정말 데프가 공개 인터페이스로 원하는 경우) 당신이 대신 일을해야하기 때문이다 :

   private val fib: Memo[Int, BigInt] = Memo {
     case 0 => 0
     case 1 => 1
     case n => fib(n-1) + fib(n-2) 
   }
   
   def foo(n: Int) = {
     fib(n)
   } 
   

3. ==============================

   3.Scalaz가에 대한 해결책을 가지고, 왜 재사용하지?

   Scalaz가에 대한 해결책을 가지고, 왜 재사용하지?

   import scalaz.Memo
   lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
     case 0 => 0
     case 1 => 1
     case n => fib(n-2) + fib(n-1)
   }
   

   당신은 Scalaz에 메모이 제이션에 대한 자세한 내용을보실 수 있습니다.

4. ==============================

   4.변경 가능한 HashMap의는 스레드로부터 안전하지 않습니다. 또한 기본 조건을 별도로 경우 문을 정의하는 것은 오히려지도가 초기 값으로로드 Memoizer에 전달 될 수 있고, 불필요한 특수 처리가 보인다. 이 메모 (불변지도) 및 공식을 받아 재귀 함수를 반환 Memoizer의 서명이 될 것입니다 다음.

   변경 가능한 HashMap의는 스레드로부터 안전하지 않습니다. 또한 기본 조건을 별도로 경우 문을 정의하는 것은 오히려지도가 초기 값으로로드 Memoizer에 전달 될 수 있고, 불필요한 특수 처리가 보인다. 이 메모 (불변지도) 및 공식을 받아 재귀 함수를 반환 Memoizer의 서명이 될 것입니다 다음.

   Memoizer과 같을 것이다

   def memoize[I,O](memo: Map[I, O], formula: (I => O, I) => O): I => O
   

   이제 다음 피보나치 공식을 주어,

   def fib(f: Int => Int, n: Int) = f(n-1) + f(n-2)
   

   Memoizer 피보나치와 같이 정의 될 수있다

   val fibonacci = memoize( Map(0 -> 0, 1 -> 1), fib)
   

   여기서 문맥 무관 범용 Memoizer 같이 정의된다

       def memoize[I, O](map: Map[I, O], formula: (I => O, I) => O): I => O = {
           var memo = map
           def recur(n: I): O = {
             if( memo contains n) {
               memo(n) 
             } else {
               val result = formula(recur, n)
               memo += (n -> result)
               result
             }
           }
           recur
         }
   

   유사 요인에 대한 수식은

   def fac(f: Int => Int, n: Int): Int = n * f(n-1)
   

   및 Memoizer와 요인이다

   val factorial = memoize( Map(0 -> 1, 1 -> 1), fac)
   

   영감 : 메모이 제이션, 더글러스 크록 포드에 의해 자바 스크립트 좋은 부품의 제 4 장

from https://stackoverflow.com/questions/16257378/is-there-a-generic-way-to-memoize-in-scala by cc-by-sa and MIT license