Loại sử dụng để lưu trữ bảng dữ liệu có thể thay đổi trong bộ nhớ trong Scala?

Question

Mỗi khi một hàm được gọi, nếu kết quả cho một tập các giá trị đối số đã cho chưa được ghi nhớ, tôi muốn đưa kết quả vào một bảng trong bộ nhớ. Một cột có nghĩa là lưu trữ kết quả, một cột khác lưu trữ các giá trị đối số.

Làm cách nào để triển khai tốt nhất tính năng này? Đối số là các loại đa dạng, bao gồm một số enums.

Trong C#, tôi thường sử dụng DataTable. Có tương đương với Scala không?

Answer 1

Bạn có thể sử dụng mutable.Map[TupleN[A1, A2, ..., AN], R] hoặc nếu bộ nhớ là mối quan tâm, WeakHashMap [1]. Các định nghĩa bên dưới (được xây dựng trên mã ghi nhớ từ michid's blog) cho phép bạn dễ dàng ghi nhớ các hàm có nhiều đối số. Ví dụ:

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 

Định nghĩa:

/** 
* 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 
    } 
} 

Các combinator điểm cố định (Memoize.Y) làm cho nó có thể để memoize chức năng đệ quy:

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 không hoạt động tốt dưới dạng bộ nhớ cache. Xem http://www.codeinstructions.com/2008/09/weakhashmap-is-not-cache-understanding.html và this related question.

Answer 2

Phiên bản do anovstrup đề xuất sử dụng Bản đồ có thể thay đổi về cơ bản giống như trong C# và do đó dễ sử dụng.

Nhưng nếu bạn muốn, bạn cũng có thể sử dụng phong cách chức năng hơn. Nó sử dụng bản đồ bất biến, hoạt động như một loại máy tích lũy. Có Tuples (thay vì Int trong ví dụ) khi các khóa hoạt động chính xác như trong trường hợp có thể thay đổi.

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)) 
} 

Tất nhiên điều này phức tạp hơn một chút, nhưng kỹ thuật hữu ích cần biết (lưu ý rằng mã ở trên nhằm mục đích rõ ràng chứ không phải tốc độ).

Answer 3

Là một người mới trong chủ đề này, tôi hoàn toàn có thể hiểu không có ví dụ nào được đưa ra (nhưng cũng xin cảm ơn). Trân trọng, tôi sẽ trình bày giải pháp của riêng tôi cho trường hợp một số đến đây có cùng cấp độ và cùng một vấn đề. Tôi nghĩ rằng mã của tôi có thể được tinh thể rõ ràng cho bất cứ ai chỉ có the very-very basic Scala knowledge.

 


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] 

 

Hoạt động hoàn hảo. Tôi đánh giá cao phê bình Nếu tôi đã bỏ lỡ một cái gì đó.

Answer 4

Khi sử dụng bản đồ có thể thay đổi để ghi nhớ, người ta phải nhớ rằng điều này sẽ gây ra các vấn đề đồng thời điển hình, ví dụ: làm một khi một văn bản chưa hoàn thành. Tuy nhiên, việc sử dụng tính năng ghi nhớ an toàn theo chủ đề gợi ý để làm như vậy nó có giá trị nhỏ nếu không phải là không.

Đoạn mã an toàn sau đây tạo ra hàm fibonacci được ghi nhớ, khởi tạo một vài chuỗi (được đặt tên từ 'a' đến 'd') thực hiện cuộc gọi đến nó. Hãy thử mã một vài lần (trong REPL), người ta có thể dễ dàng nhìn thấy f(2) set được in nhiều lần. Điều này có nghĩa là một chủ đề A đã bắt đầu tính toán của f(2) nhưng Chủ đề B hoàn toàn không có ý tưởng về nó và bắt đầu bản sao của nó tính toán. Sự thiếu hiểu biết này phổ biến ở giai đoạn xây dựng của bộ đệm, bởi vì tất cả các luồng không thấy giải pháp con nào được thiết lập và sẽ nhập mệnh đề 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

Ngoài câu trả lời Landei, tôi cũng muốn đề nghị từ dưới lên (không memoization) cách làm DP ở Scala là có thể, và ý tưởng cốt lõi là sử dụng foldLeft (s).

Ví dụ để tính số Fibonacci

def fibo(n: Int) = (1 to n).foldLeft((0, 1)) { 
    (acc, i) => (acc._2, acc._1 + acc._2) 
    }._1 

Ví dụ để tăng dài nhất dãy

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 
}