Tối ưu hóa GHC

Question

Hai chức năng Haskell bên dưới dường như chỉ khác nhau khi biến chỉ mục là ẩn hoặc rõ ràng nhưng sự khác biệt về hiệu suất là bởi hai đơn vị độ lớn.

Chức năng này mất khoảng 0,03 giây để tính toán mfib 30:

let mfib = (map fib [0..] !!) 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

Chức năng này mất khoảng 3 giây cho mfib 30:

let mfib i = map fib [0..] !! i 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

Tôi đoán nó đã làm với GHC inline quy tắc và đã cố gắng thêm pragmas nội dòng/không có dòng để có được hiệu suất phù hợp.

EDIT: Tôi hiểu cách thực hiện tra cứu trong danh sách lười có thể được sử dụng để ghi nhớ chức năng fib và tại sao định nghĩa truyền thống về fib rất chậm. Tôi đã mong đợi việc ghi nhớ để làm việc trong chức năng thứ hai cũng như đầu tiên và không hiểu tại sao nó không phải là.

Answer 1

Sẽ dễ dàng hơn để hiểu những khác biệt này khi xem mã được giải mã, do đó, đây là các phiên bản được giải thích một phần của hai hàm.

let mfib = let fib 0 = 0 
       fib 1 = 1 
       fib x = mfib (x-1) + mfib (x-2) 
      in (!!) (map fib [0..]) 

so

let mfib = \i -> 
       let fib 0 = 0 
        fib 1 = 1 
        fib x = mfib (x-1) + mfib (x-2) 
       in map fib [0..] !! i 

Lưu ý rằng trong chương trình thứ hai, khái niệm map fib [0..] xuất hiện bên \i -> ..., vì vậy nó sẽ (bình thường, mà không cần tối ưu hóa) đánh giá cho mỗi giá trị của i. Xem When is memoization automatic in GHC Haskell?

Answer 2

Không, điều này không liên quan gì đến nội tuyến. Sự khác biệt là mfib = (map fib [0..] !!) không có đối số. Nó vẫn là một chức năng của khóa học, nhưng đánh giá rằng chức năng không trả trước không yêu cầu phải vượt qua bất kỳ đối số. Cụ thể, việc đánh giá mfib này sẽ tạo danh sách fib theo cách có thể sử dụng lại cho tất cả các chỉ mục.

OTOH, mfib i = map fib [0..] !! i nghĩa là toàn bộ khối where sẽ chỉ được xem xét khi bạn thực sự vượt qua đối số i.

Hai chỉ khác nhau nếu bạn đánh giá một hàm nhiều lần lặp đi lặp lại. Thật không may cho phiên bản thứ hai, các chức năng đệ quy của riêng đã gọi nó một lần nữa và một lần nữa! Vì vậy, mfib (x-1) + mfib (x-2) sau đó cần thực hiện toàn bộ công việc của mfib (x-1), và sau đó lại một lần nữa toàn bộ công việc của mfib (x-2). Vì vậy, mfib n mất hơn gấp đôi so với chi phí tính toán của mfib (n-1), do đó mfib ∈ O (2 ⁿ).

Điều đó vô cùng lãng phí, bởi vì hầu hết các điều khoản trong mfib (x-2) cũng đã có trong mfib (x-1) và chỉ có thể được sử dụng lại. Vâng, đó là chính xác những gì phiên bản đầu tiên của bạn làm, bởi vì nó tính toán danh sách fib một lần và cho tất cả các chỉ số, vì vậy việc đánh giá mfib (x-1) sẽ thực hiện hầu hết công việc mà sau đó có thể được đọc lại bởi mfib (x-2), giảm độ phức tạp cho đa thức.