Lập trình động trong F #

Question

Cách thanh lịch nhất để triển khai các thuật toán lập trình động giải quyết problems with overlapping subproblems là gì? Trong chương trình bắt buộc người ta thường tạo ra một mảng được lập chỉ mục (ít nhất là trong một chiều) theo kích thước của bài toán, và sau đó thuật toán sẽ bắt đầu từ những vấn đề đơn giản và làm việc phức tạp hơn một lần, sử dụng kết quả đã tính toán.

Ví dụ đơn giản nhất tôi có thể nghĩ ra được tính toán số thứ N Fibonacci:

int Fibonacci(int N) 
{ 
    var F = new int[N+1]; 
    F[0]=1; 
    F[1]=1; 
    for(int i=2; i<=N; i++) 
    { 
     F[i]=F[i-1]+F[i-2]; 
    } 
    return F[N]; 
} 

Tôi biết bạn có thể thực hiện điều tương tự trong F #, nhưng tôi đang tìm kiếm một giải pháp chức năng đẹp (đó là O (N) cũng rõ ràng).

Answer 1

Một kỹ thuật khá hữu ích cho lập trình động được gọi là ghi nhớ. Để biết thêm chi tiết, xem ví dụ blog post by Don Syme hoặc introduction by Matthew Podwysocki.

Ý tưởng là bạn viết (ngây thơ) đệ quy chức năng và sau đó thêm bộ nhớ cache lưu trữ kết quả trước đó. Điều này cho phép bạn viết hàm theo kiểu chức năng thông thường, nhưng nhận được hiệu suất của thuật toán được triển khai bằng cách sử dụng lập trình động.

Ví dụ, một (không hiệu quả) chức năng ngây thơ để tính số Fibonacci trông như thế này:

let rec fibs n = 
    if n < 1 then 1 else 
    (fibs (n - 1)) + (fibs (n - 2)) 

này là không hiệu quả, bởi vì khi bạn gọi fibs 3, nó sẽ gọi fibs 1 ba lần (và nhiều lần hơn nếu bạn gọi, ví dụ: fibs 6). Ý tưởng đằng sau việc ghi nhớ là chúng tôi viết bộ nhớ cache lưu trữ kết quả của fib 1 và fib 2, v.v., do đó, các cuộc gọi lặp lại sẽ chỉ chọn giá trị được tính trước từ bộ nhớ cache.

Một chức năng chung mà không được memoization có thể được viết như thế này:

open System.Collections.Generic 

let memoize(f) =  
    // Create (mutable) cache that is used for storing results of 
    // for function arguments that were already calculated. 
    let cache = new Dictionary<_, _>() 
    (fun x -> 
     // The returned function first performs a cache lookup 
     let succ, v = cache.TryGetValue(x) 
     if succ then v else 
     // If value was not found, calculate & cache it 
     let v = f(x) 
     cache.Add(x, v) 
     v) 

Để viết chức năng Fibonacci hiệu quả hơn, bây giờ chúng ta có thể gọi memoize và cung cấp cho nó chức năng mà thực hiện việc tính toán như một cuộc tranh cãi:

let rec fibs = memoize (fun n -> 
    if n < 1 then 1 else 
    (fibs (n - 1)) + (fibs (n - 2))) 

Lưu ý rằng đây là giá trị đệ quy - phần thân của hàm gọi hàm được ghi nhớ là fibs.

Answer 2

Câu trả lời của Tomas là một cách tiếp cận chung tốt. Trong trường hợp cụ thể hơn, có thể có các kỹ thuật khác hoạt động tốt - ví dụ, trong trường hợp Fibonacci của bạn, bạn thực sự chỉ cần một số lượng hữu hạn của trạng thái (2 số trước), không phải tất cả các giá trị được tính trước đó. Vì vậy, bạn có thể làm một cái gì đó như thế này:

let fibs = Seq.unfold (fun (i,j) -> Some(i,(j,i+j))) (1,1) 
let fib n = Seq.nth n fibs 

Bạn cũng có thể làm điều này nhiều hơn trực tiếp (không sử dụng Seq.unfold):

let fib = 
    let rec loop i j = function 
    | 0 -> i 
    | n -> loop j (i+j) (n-1) 
    loop 1 1 

Answer 3

let fibs = 
    (1I,1I) 
    |> Seq.unfold (fun (n0, n1) -> Some (n0 , (n1, n0 + n1))) 
    |> Seq.cache