Haskell: Danh sách v. Mảng, sự khác biệt về hiệu suất

Question

Một câu hỏi khác từ Haskell n00b.

Tôi so sánh hiệu quả của các phương pháp khác nhau được sử dụng để giải quyết Vấn đề # 14 trên trang web Dự án Euler. Đặc biệt, tôi hy vọng sẽ hiểu rõ hơn các yếu tố dẫn đến sự khác biệt trong thời gian đánh giá cho bốn (một chút) cách tiếp cận khác nhau để giải quyết vấn đề.

(mô tả của vấn đề # 14 và phương pháp tiếp cận khác nhau dưới đây.)

Đầu tiên, một cái nhìn tổng quát về vấn đề # 14. Nó phải làm với "số Collatz" (tức là, cùng một bài tập lập trình như bài trước của tôi đã khám phá một khía cạnh khác của Haskell). Số Collatz cho một số nguyên nhất định bằng với chiều dài của chuỗi Collatz cho số nguyên đó. Một chuỗi Collatz cho một số nguyên được tính như sau: số đầu tiên ("n0") trong dãy là số nguyên chính nó; nếu n0 là số chẵn, số tiếp theo trong dãy ("n1") bằng n/2; nếu n0 là lẻ, thì n1 bằng 3 * n0 + 1. Chúng ta tiếp tục mở rộng đệ quy chuỗi cho đến khi chúng ta đến 1, lúc đó trình tự kết thúc. Ví dụ, chuỗi collatz cho 5 là: {5, 16, 8, 4, 2, 1} (vì 16 = 3 * 5 + 1, 8 = 16/2, 4 = 8/2, ...).

Bài toán 14 yêu cầu chúng tôi tìm số nguyên dưới 1.000.000 mà có số Collatz lớn nhất. Để có hiệu lực đó, chúng ta có thể xem xét một hàm "collatz" mà khi truyền một số nguyên "n" làm đối số, trả về số nguyên bên dưới n với số Collatz lớn nhất. Nói cách khác, p 1000000 cho chúng ta câu trả lời cho Bài toán số 14.

Theo mục đích của bài tập này (ví dụ, tìm hiểu sự khác biệt về thời gian thẩm định), chúng tôi có thể xem xét các phiên bản Haskell của 'Collatz' mà khác nhau giữa hai chiều:

(1) Thực hiện: Chúng ta lưu trữ các dữ liệu của Số collatz (sẽ được tạo cho tất cả các số nguyên 1..n) dưới dạng danh sách hoặc mảng? Tôi gọi đây là thứ nguyên "triển khai", tức là, việc triển khai chức năng là "danh sách" hoặc "mảng".

(2) Thuật toán: chúng tôi tính số Collatz cho bất kỳ số nguyên n nào bằng cách mở rộng chuỗi Collatz cho đến khi nó hoàn thành (tức là, cho đến khi chúng ta đạt đến 1)? Hay chúng ta chỉ mở rộng chuỗi cho đến khi chúng ta đạt đến một số k nhỏ hơn n (tại thời điểm đó chúng ta chỉ có thể sử dụng số k collatz mà chúng ta đã tính toán)? Tôi gọi đây là thứ nguyên "thuật toán", tức là thuật toán của hàm là "hoàn thành" (tính số Collatz cho mỗi số nguyên) hoặc "một phần". Sau này rõ ràng đòi hỏi ít hoạt động hơn.

Dưới đây là bốn phiên bản thể của hàm "Collatz": mảng/phần, danh sách/phần, mảng/đầy đủ và danh sách/hoàn thành:

import Data.Array ((!) , listArray , assocs) 
import Data.Ord (comparing) 
import Data.List (maximumBy) 

--array implementation; partial algorithm (FEWEST OPERATIONS) 
collatzAP x = maximumBy (comparing snd) $ assocs a where 
    a = listArray (0,x) (0:1:[c n n | n <- [2..x]]) 
    c n i = let z = if even i then div i 2 else 3*i+1 
     in if i < n then a ! i else 1 + c n z 

--list implementation; partial algorithm 
collatzLP x = maximum a where 
    a = zip (0:1:[c n n | n <- [2..x]]) [0..x] 
    c n i = let z = if even i then div i 2 else 3*i+1 
     in if i < n then fst (a!!i) else 1 + c n z 

--array implementation, complete algorithm 
collatzAC x = maximumBy (comparing snd) $ assocs a where 
    a = listArray (0,x) (0:1:[c n n | n <- [2..x]]) 
    c n i = let z = if even i then div i 2 else 3*i+1 
    in if i == 1 then 1 else 1 + c n z  

--list implementation, complete algorithm (MOST OPERATIONS) 
collatzLC x = maximum a where 
    a = zip (0:1:[c n n | n <- [2..x]]) [0..x] 
    c n i = let z = if even i then div i 2 else 3*i+1 
     in if i == 1 then 1 else 1 + c n z 

Về tốc độ đánh giá: Tôi biết rằng mảng là truy cập nhanh hơn các danh sách (ví dụ, thời gian truy cập O (1) so với O (n) cho một chỉ mục n) vì vậy tôi mong đợi việc triển khai "mảng" của "collatz" nhanh hơn việc thực hiện 'danh sách', ceteris paribus. Ngoài ra, tôi dự kiến ​​thuật toán 'một phần' sẽ nhanh hơn thuật toán 'hoàn thành' (ceteris paribus), vì nó cần thực hiện ít hoạt động hơn để xây dựng tập dữ liệu của số Collatz.

Kiểm tra bốn chức năng của chúng tôi trên đầu vào kích thước khác nhau, chúng ta quan sát các lần đánh giá sau (bình luận dưới đây):

Đó là thực sự là trường hợp đó, phiên bản 'mảng/phần' là phiên bản nhanh nhất của "collatz" (bởi một lợi nhuận tốt).Tuy nhiên, tôi thấy một chút phản trực giác rằng 'danh sách/hoàn thành' không phải là phiên bản chậm nhất. Danh dự đó đi vào 'danh sách/một phần', chậm hơn 20 lần so với 'danh sách/hoàn thành'!

Câu hỏi của tôi: Sự khác biệt về thời gian đánh giá giữa 'danh sách/một phần' và 'danh sách/hoàn thành' (so sánh giữa 'mảng/một phần' và 'mảng/hoàn thành') hoàn toàn do sự khác biệt về quyền truy cập hiệu quả giữa các danh sách và mảng trong Haskell? Hay tôi không thực hiện "thử nghiệm được kiểm soát" (tức là, có các yếu tố khác khi chơi)?

Answer 1

Tôi không hiểu làm thế nào các câu hỏi về hiệu suất tương đối của hai thuật toán làm việc với danh sách có liên quan đến mảng ở tất cả ... nhưng đây là quan điểm của tôi:

Cố gắng tránh danh sách chỉ mục, danh sách đặc biệt dài, nếu hiệu suất là bất kỳ mối quan tâm nào. Lập chỉ mục thực sự là một traversal (như bạn đã biết). "Danh sách/một phần" là lập chỉ mục/duyệt qua rất nhiều. Danh sách/hoàn thành không phải là. Do đó sự khác biệt giữa mảng/hoàn thành và danh sách/hoàn thành là không đáng kể, và khác nhau giữa "danh sách/một phần" và phần còn lại là rất lớn.