Khó hiểu hành vi phân bổ bộ nhớ Haskell

Question

Tôi tình cờ gặp Haskell và FP và bị choáng váng bởi các khả năng. Và mọt sách toán học cũ bên trong tôi không gặp khó khăn khi viết mã ngây thơ cho các mục đích hữu ích thực sự. Tuy nhiên, việc truyền cảm hứng cho tất cả các bài đọc, tôi vẫn thực sự có một thời gian khó hiểu làm thế nào để không đạt được một số nút cổ chai hiệu suất đáng ngạc nhiên.

Vì vậy, tôi viết các đoạn mã rất ngắn với triển khai ngây thơ và sau đó thử các thay đổi nhỏ để xem hiệu suất phản hồi như thế nào. Và đây là một ví dụ tôi thực sự không thể hiểu xung quanh ... Tôi đã viết hàm này tìm ra giải pháp cho Josephus problem, với mục đích với việc triển khai danh sách ngây thơ.

m = 3 
n = 3000 
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n" 

whosLeft [lucky] = lucky 
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers 

Sau đó chạy trong 190 mili giây, với năng suất 63% theo RTS.

Sau đó, điều đầu tiên tôi muốn thử là xóa (chiều dài người lính -1) và thay thế bằng số nguyên giảm dần.

Thời gian chạy nhảy lên đến 900 mili giây và năng suất giảm xuống 16% và sử dụng bộ nhớ gấp 47 lần so với mã đơn giản ở trên! Vì vậy, tôi đã thêm đánh giá nghiêm ngặt, buộc loại Int, thử những thứ như loại bỏ các biến toàn cầu và các biến số khác, nhưng không được tận dụng nhiều. Và tôi không thể hiểu được sự chậm lại này.

m = 3::Int 
n = 3000::Int 
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n" 

whosLeft 1 [lucky] = lucky 
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left 
       where left = take (n'-1) $ drop m $ cycle soldiers 

Tôi đã xem qua các bài viết và bài đăng liên quan đến hiệu suất, nhưng tôi dường như không nhận được gợi ý về điều này. Vẫn còn là một Noob Haskell tôi phải mất một cái gì đó lớn ... Làm thế nào có thể thêm một tham số này (tính toán nhai trước ...) giảm tốc độ rất nhiều?

PS: Tôi biết, nếu thực sự Josephus đã có 3000 binh sĩ, họ sẽ không cần thiết để tự tử ...

Answer 1

Các giải pháp đầu tiên buộc toàn bộ cột sống của danh sách những người lính bằng cách lấy chiều dài của nó. Giải pháp thứ hai chỉ có hiệu lực (sử dụng seq) số đầu của danh sách người lính. Thay thế số left ở giữa các số seq s bằng số length left và bạn sẽ nhận được hiệu suất của mình trở lại.