Tại sao thêm hiệu suất phân loại chữ ký đa hình?

Question

Dưới đây là một chức năng đơn giản để tính số Fibonacci:

fib :: [Int] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

Trong ghci tôi có thể tính toán hàng loạt một cách nhanh chóng. Trong thực tế, một chút thử nghiệm cho thấy rằng tính toán chạy trong khoảng thời gian tuyến tính.

ghci> last $ take 100000 fib 
354224848179261915075   -- takes under a second 

Nếu tôi thay đổi chữ ký loại là đa hình thay vì:

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

Sau đó, các thuật toán trở nên chậm hơn. Trong thực tế, có vẻ như nó bây giờ chạy trong thời gian mũ!

Việc chuyển sang chữ ký kiểu đa hình có nghĩa là danh sách đang được tính toán lại hoàn toàn ở từng giai đoạn không? Nếu vậy, tại sao?

Answer 1

Điều này là do bản dịch từ điển.

fib :: [Int] 

là hằng số cấp cao nhất.

Nhưng điều này:

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

chỉ là một chức năng cấp cao nhất, mà sẽ được áp dụng cho một cuốn từ điển Num khi chạy. Cũng giống như vậy:

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d)) 

Vì vậy, nếu bạn biên dịch này mà không cần bất kỳ tối ưu, như vậy mà không chuyên môn hóa có thể xảy ra, bạn sẽ kết thúc với mũ thời gian fib, như danh sách được xây dựng lại từ đầu, trên mỗi cuộc gọi chức năng - nó không phải là một cấu trúc dữ liệu lười biếng nữa.

Answer 2

Có, chữ ký kiểu đa hình có nghĩa là chữ ký được tính toán lại ở mỗi giai đoạn. Cốt lõi được sản xuất bởi GHC-7.4.2 với -O2:

lvl_rcZ :: GHC.Integer.Type.Integer 
[GblId, Str=DmdType] 
lvl_rcZ = __integer 1 

Rec { 
PolyFib.fib [Occ=LoopBreaker] 
    :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W] 
[GblId, Arity=1, Str=DmdType L] 
PolyFib.fib = 
    \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) -> 
    GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.List.zipWith 
      @ a_aal 
      @ a_aal 
      @ a_aal 
      (GHC.Num.+ @ a_aal $dNum_aam) 
      (PolyFib.fib @ a_aal $dNum_aam) 
      (case PolyFib.fib @ a_aal $dNum_aam of _ { 
       [] -> GHC.List.tail1 @ a_aal; 
       : _ xs_abD -> xs_abD 
      }))) 
end Rec } 

Lý do là nó không khả thi để cache một danh sách các số Fibonacci đối với từng loại thuộc Num, và fib là một cách rõ ràng giá trị đa hình, do đó nó không được lưu trữ.

Nếu bạn muốn cache nó ít nhất là cho việc tính toán ở từng loại, sử dụng danh sách địa phương

pfibs :: Num a => [a] 
pfibs = res 
    where 
    res = 1 : 1 : zipWith (+) res (tail res) 

hiện bộ nhớ đệm cho mỗi tính toán (vì vậy pfibs !! 500 ví dụ như là nhanh) kể từ bây giờ danh sách là monomorphic trong mỗi tính toán. Nó sẽ vẫn được tính toán lại cho mỗi truy vấn (trừ khi bạn liên kết nó với một tên đơn), nhưng không phải cho mỗi phần tử danh sách đơn lẻ.

*PolyFib> pfibs !! 999999 :: Int 
-4249520595888827205 
(0.31 secs, 137462088 bytes)