Các mẹo đơn giản để tăng hiệu suất của Haskell (đối với các vấn đề về ProjectEuler)?

Question

Tôi mới lập trình và học Haskell bằng cách đọc và làm việc thông qua các vấn đề về Dự án Euler. Tất nhiên, điều quan trọng nhất người ta có thể làm để cải thiện hiệu suất trên những vấn đề này là sử dụng một thuật toán tốt hơn. Tuy nhiên, rõ ràng với tôi rằng có những cách đơn giản và dễ thực hiện khác để cải thiện hiệu suất. Một tìm kiếm lướt qua mang lên this question, và this question, trong đó cung cấp các mẹo sau đây:

• Sử dụng cờ GHC -O2 và -fllvm.
• Sử dụng loại Int, thay vì Integer, vì nó không được hộp (hoặc thậm chí là Integer thay vì Int64). Điều này đòi hỏi phải gõ các chức năng, không để cho trình biên dịch quyết định trên bay.
• Sử dụng rem, không mod, để thử nghiệm phân chia.
• Sử dụng Schwartzian transformations khi thích hợp.
• Sử dụng bộ tích lũy trong các hàm đệ quy (tối ưu hóa đệ quy đuôi, tôi tin).
• Memoization

(Một câu trả lời cũng đề cập đến lao động/chuyển đổi wrapper, nhưng điều đó dường như khá tiên tiến.)

Câu hỏi (?): gì khác tối ưu đơn giản người ta có thể thực hiện trong Haskell để cải thiện hiệu suất về các vấn đề kiểu Euler? Có bất kỳ ý tưởng hoặc tính năng cụ thể nào khác của Haskell (hoặc chức năng lập trình cụ thể không?) Có thể được sử dụng để giúp tăng tốc các giải pháp cho các vấn đề của Project Euler? Ngược lại, những gì nên xem ra cho? Một số điều phổ biến nhưng không hiệu quả cần tránh là gì?

Answer 1

Có fairly large section of the Haskell wiki về hiệu suất.

Một vấn đề khá phổ biến là quá ít (hoặc quá nhiều) độ nghiêm ngặt (điều này được đề cập trong các phần được liệt kê trong phần General techniques của trang hoạt động bên trên). Quá nhiều lười biếng gây ra một số lượng lớn các khối được tích lũy, quá nhiều độ nghiêm ngặt có thể gây ra quá nhiều để được đánh giá.

Những cân nhắc này đặc biệt quan trọng khi viết các hàm đệ quy đuôi (tức là những người có bộ tích lũy); Và, trên lưu ý đó, tùy thuộc vào cách chức năng được sử dụng, một hàm đệ quy đuôi đôi khi kém hiệu quả hơn trong Haskell so với hàm không đệ quy tương đương, ngay cả với các chú thích nghiêm ngặt tối ưu.

Ngoài ra, như được minh họa bằng this recent question, việc chia sẻ có thể tạo sự khác biệt lớn về hiệu suất (trong nhiều trường hợp, điều này có thể được coi là một hình thức ghi nhớ).

Answer 2

Một gợi ý dễ dàng là sử dụng hlint là chương trình kiểm tra mã nguồn của bạn và đưa ra đề xuất cải thiện cú pháp khôn ngoan. Điều này có thể không tăng tốc độ bởi vì nhiều khả năng nó đã được thực hiện bởi trình biên dịch hoặc đánh giá lười biếng. Nhưng nó có thể giúp trình biên dịch trong một số trường hợp. Hơn nữa nó sẽ làm cho bạn một lập trình Haskell tốt hơn vì bạn sẽ học cách tốt hơn để làm việc, và nó có thể dễ dàng hơn để hiểu chương trình của bạn và phân tích nó.

ví dụ lấy từ http://community.haskell.org/~ndm/darcs/hlint/hlint.htm như:

darcs-2.1.2\src\CommandLine.lhs:94:1: Error: Use concatMap 
Found: 
    concat $ map escapeC s 
Why not: 
    concatMap escapeC s 

và

darcs-2.1.2\src\Darcs\Patch\Test.lhs:306:1: Error: Use a more efficient monadic variant 
Found: 
    mapM (delete_line (fn2fp f) line) old 
Why not: 
    mapM_ (delete_line (fn2fp f) line) old 

Tôi nghĩ rằng sự gia tăng lớn nhất bạn có thể làm trong vấn đề dự án Euler là để hiểu được vấn đề và loại bỏ tính toán không cần thiết. Ngay cả khi bạn không hiểu tất cả mọi thứ bạn có thể làm một số sửa chữa nhỏ mà sẽ làm cho chương trình của bạn chạy gấp đôi tốc độ. Giả sử bạn đang tìm kiếm số nguyên tố lên đến 1.000.000, thì tất nhiên bạn có thể làm filter isPrime [1..1000000]. Nhưng nếu bạn nghĩ một chút, thì bạn có thể nhận ra điều đó, thậm chí không có số nào ở trên là một số nguyên tố, ở đó bạn đã loại bỏ (khoảng) một nửa công việc. Thay vì làm [1,2] ++ filter isPrime [3,5..999999]

Answer 3

Dưới đây là một số slide tốt bởi Johan Tibell mà tôi thường xuyên tham khảo:

Haskell Performance Patterns

Answer 4

Dự án Euler là chủ yếu là về việc tìm kiếm các giải pháp thuật toán thông minh cho các vấn đề. Khi bạn có thuật toán đúng, tối ưu hóa vi mô hiếm khi là một vấn đề, vì ngay cả việc triển khai đơn giản hoặc diễn giải (ví dụ: Python hoặc Ruby) sẽ chạy tốt trong giới hạn tốc độ. Kỹ thuật chính mà bạn cần là hiểu được sự đánh giá lười biếng để bạn có thể tránh được việc xây dựng cơ bản.