Haskell Fibonacci có vẻ chậm

Question

tôi đang học Haskell, và tôi đã viết một chức năng đơn giản Fibonacci:

fib :: Int -> Int 

fib 1 = 1 
fib 0 = 0 
fib n = (fib (n-1)) + (fib (n-2)) 

Dường như để biên dịch ok, và tải đoạn mã trên vào REPL GHCI tôi có thể lộn xộn xung quanh với một vài số điện thoại . Tôi đã thử

fib 33 

và rất ngạc nhiên khi mất khoảng 4 giây để đưa ra kết quả. (Xin lỗi tôi không biết làm thế nào để thời gian một chức năng trong Haskell được nêu ra, do đó, tính bản thân mình).

Fib 33 không đặc biệt đánh thuế. Câu trả lời là ít hơn 4 triệu. Vì vậy, tôi giả định mã của tôi không phải là rất tốt bằng văn bản hoặc có một số vấn đề với cách tôi đang làm đệ quy có lẽ (tốt, nó không phải là tốt bằng văn bản ở chỗ nó không đưa vào tài khoản số nguyên âm). Câu hỏi đặt ra là, tại sao nó lại chậm? Bất kỳ trợ giúp nào được đánh giá cao.

Answer 1

Việc đánh giá mất nhiều thời gian hơn bạn mong đợi bởi vì chức năng của bạn không sử dụng memoization. Xem ví dụ this question hoặc that question để có câu trả lời cho cách xác định hàm fibonacci trong Haskell bằng cách sử dụng ghi nhớ.

Answer 2

Bạn có so sánh thời gian đó với các ngôn ngữ khác không?

Đây là thuật toán đệ quy có độ phức tạp O (2^n). Tại n = 33, cung cấp số lượng cuộc gọi đáng kinh ngạc. Nếu bạn đếm có bao nhiêu miliseconds hoặc nano giây đã có trên mỗi cuộc gọi như vậy bạn còn lại với một câu trả lời rất đáng chú ý về hiệu suất thực tế. Hãy nhớ rằng, một số môi trường biên dịch/thực thi có thể nhớ các giá trị trả về hàm (Frerich có bộ nhớ tốt hơn để gọi nó là: memoization), giúp cải thiện hiệu suất trong trường hợp của thuật toán này rất nhiều. Trong trường hợp này nó không xảy ra, vì vậy tất cả những cuộc gọi đệ quy 2^n đó xảy ra.

Answer 3

Thuật toán của bạn không tốt lắm. Bạn có thể cải thiện nó một chút bằng cách sử dụng ghi nhớ, lên đến O (n). Sử dụng phân chia và chinh phục, bạn có thể nhận được lên đến O (log n):

import Data.Matrix 

fib :: Integer -> Integer 
fib n = ((fromLists [[1,1],[1,0]])^n) ! (1,2) 

Ý tưởng là, nhân đó là kết hợp, vì vậy bạn có thể đặt niềng răng của bạn về địa điểm chiến lược:

5^10 = (5 * 5 * 5 * 5 * 5) * (5 * 5 * 5 * 5 * 5) = (5 * 5 * 5 * 5 * 5)^2 = ((5 * 5) * (5 * 5) * 5)^2 = ((5 * 5)^2 * 5)^2 = (((5^2)^2) * 5)^2

Có thể áp dụng cùng một mẫu để nhân ma trận. Và Haskell đã thực hiện điều này trong thư viện mặc định của nó cho (^).

này hoạt động thực sự:

map fib [1..21] 
--! [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]