Tại sao chức năng độ dài nghiêm ngặt lại hoạt động nhanh hơn đáng kể?

Question

Tôi đã chơi đùa với các định nghĩa để hiểu rõ hơn mô hình đánh giá và viết hai cho chiều dài của một danh sách.

Định nghĩa ngây thơ:

len :: [a] -> Int 
len [] = 0 
len (_:xs) = 1 + len xs 

Các nghiêm ngặt (và đuôi-đệ quy) định nghĩa:

slen :: [a] -> Int -> Int 
slen [] n = n 
slen (_:xs) !n = slen xs (n+1) 

len [1..10000000] mất khoảng 5-6 giây để thực hiện.
slen [1..10000000] 0 mất khoảng 3-4 giây để thực hiện.

Tôi tò mò tại sao. Trước khi tôi kiểm tra các buổi biểu diễn, tôi đã tích cực rằng họ sẽ biểu diễn như nhau bởi vì len chỉ nên có thêm một bài đánh giá để đánh giá nhiều nhất. Đối với mục đích trình diễn:

len [a,b,c,d] 
= 1 + len [b,c,d] 
= 1 + 1 + len [c,d] 
= 1 + 1 + 1 + len [d] 
= 1 + 1 + 1 + 1 + len [] 
= 1 + 1 + 1 + 1 + 0 
= 4 

Và

slen [a,b,c,d] 0 
= slen [b,c,d] 1 
= slen [c,d] 2 
= slen [d]  3 
= slen []  4 
= 4 

Điều gì làm cho slen nhanh hơn trông thấy?

P.S. Tôi cũng đã viết một hàm lười đệ quy đuôi (giống như slen nhưng lười) như là một nỗ lực để đóng-vào lý do - có lẽ đó là vì nó là đệ quy đuôi - nhưng nó thực hiện giống như định nghĩa ngây thơ.

Answer 1

Bước cuối cùng của len không phải là O (1). Nó là O (n) để cộng các số n lại với nhau. len cũng sử dụng bộ nhớ O (n) trong khi slen sử dụng bộ nhớ O (1).

Lý do sử dụng bộ nhớ O (n) là mỗi đoạn sử dụng hết bộ nhớ. Vì vậy, khi bạn có một cái gì đó như thế này:

1 + 1 + 1 + 1 + len [] 

có năm thunks unevaluated (bao gồm len [])

Trong GHCi, chúng ta có thể xem xét hành vi thunk này một chút dễ dàng hơn với các lệnh :sprint. Lệnh :sprint in giá trị đã cho mà không buộc đánh giá bất kỳ khối nào (bạn có thể tìm hiểu thêm từ :help). Tôi sẽ sử dụng conses ((:)) vì chúng ta có thể dễ dàng đánh giá từng thunk một tại một thời điểm, nhưng nguyên tắc là như nhau.

λ> let ys = map id $ 1 : 2 : 3 : [] :: [Int] -- map id prevents GHCi from being too eager here 
λ> :sprint ys 
ys = _ 
λ> take 1 ys 
[1] 
λ> :sprint ys 
ys = 1 : _ 
λ> take 2 ys 
[1,2] 
λ> :sprint ys 
ys = 1 : 2 : _ 
λ> take 3 ys 
[1,2,3] 
λ> :sprint ys 
ys = 1 : 2 : 3 : _ 
λ> take 4 ys 
[1,2,3] 
λ> :sprint ys 
ys = [1,2,3] 

thunks Unevaluated được đại diện bởi _ và bạn có thể thấy rằng trong bản gốc ys có 4 thunks lồng vào bên trong của nhau, một cho từng phần của danh sách (bao gồm cả []).

Không có cách nào tốt mà tôi biết để thấy điều này trong Int vì đánh giá của nó là nhiều hơn hoặc không có gì, nhưng nó vẫn xây dựng một thunk lồng nhau theo cùng một cách. Nếu bạn có thể thấy nó như thế này, đánh giá của nó sẽ trông giống như sau:

len [a,b,c,d] 
= 1 + len [b,c,d] 
= 1 + 1 + len [c,d] 
= 1 + 1 + 1 + len [d] 
= 1 + 1 + 1 + 1 + len [] 
= 1 + 1 + 1 + 1 + 0 
= 1 + 1 + 1 + 1  -- Here it stops building the thunks and starts evaluating them 
= 1 + 1 + 2 
= 1 + 3 
= 4 

Answer 2

Câu trả lời của David Young đưa ra giải thích đúng về sự khác biệt trong thứ tự đánh giá. Bạn nên suy nghĩ về đánh giá Haskell theo cách ông vạch ra.

Hãy để tôi chỉ cho bạn cách bạn có thể thấy sự khác biệt trong Lõi. Tôi nghĩ rằng nó thực sự rõ ràng hơn với các tối ưu hóa, bởi vì việc đánh giá kết thúc như một tuyên bố rõ ràng case. Nếu bạn chưa bao giờ chơi với Core trước đó, hãy xem câu hỏi SO chuẩn tắc về chủ đề: Reading GHC Core.

Tạo đầu ra lõi với ghc -O2 -ddump-simpl -dsuppress-all -ddump-to-file SO27392665.hs. Bạn sẽ thấy rằng GHC tách cả hai len và slen thành chức năng "công nhân" đệ quy, $wlen hoặc $wslen và chức năng "trình bao bọc" không phản hồi. Bởi vì phần lớn thời gian là chi tiêu trong các "công nhân" đệ quy tập trung vào họ:

Rec { 
$wlen 
$wlen = 
    \ @ a_arZ w_sOR -> 
    case w_sOR of _ { 
     [] -> 0; 
     : ds_dNU xs_as0 -> 
     case $wlen xs_as0 of ww_sOU { __DEFAULT -> +# 1 ww_sOU } 
    } 
end Rec } 

len 
len = 
    \ @ a_arZ w_sOR -> 
    case $wlen w_sOR of ww_sOU { __DEFAULT -> I# ww_sOU } 

Rec { 
$wslen 
$wslen = 
    \ @ a_arR w_sOW ww_sP0 -> 
    case w_sOW of _ { 
     [] -> ww_sP0; 
     : ds_dNS xs_asW -> $wslen xs_asW (+# ww_sP0 1) 
    } 
end Rec } 

slen 
slen = 
    \ @ a_arR w_sOW w1_sOX -> 
    case w1_sOX of _ { I# ww1_sP0 -> 
    case $wslen w_sOW ww1_sP0 of ww2_sP4 { __DEFAULT -> I# ww2_sP4 } 
    } 

Bạn có thể thấy rằng chỉ có một $wslencase có, trong khi $wlen có hai. Nếu bạn nhìn vào câu trả lời của David, bạn có thể theo dõi những gì xảy ra trong $wlen: phân tích trường hợp của nó trên hàm tạo danh sách ngoài cùng ([]/:), sau đó thực hiện cuộc gọi đệ quy tới $wlen xs_as0 (tức là len xs), cũng là case s, tức là lực lượng thunk tích lũy.

Mặt khác, trong $wslen, chỉ có một tuyên bố case. Trong nhánh đệ quy, chỉ đơn giản là một phần bổ sung không được mở, (+# ww_sP0 1), không tạo ra một đoạn.

(Lưu ý: một phiên bản trước của câu trả lời này đã tuyên bố rằng với -O GHC thể chuyên $wslen nhưng không $wlen sử dụng không có hộp bọc Int# s Đó không phải là trường hợp..)