Trước hết, mod chậm nên sử dụng rem trong tình huống mà nó không quan trọng (khi bạn đang phải đối phó với âm, về cơ bản). Thứ hai, sử dụng Criterion để hiển thị (cho chính mình) những gì là nhanh hơn và những thay đổi thực sự tối ưu hóa. Tôi biết tôi không đưa ra một câu trả lời đầy đủ cho bạn đặt câu hỏi với điều này, nhưng một nơi tốt của mình cho bạn (và người trả lời tiềm năng khác) để bắt đầu, vì vậy đây là một số mã:
import List
import Criterion.Main
main = do
str <- getLine
let run f = length . f
input = read str :: Integer
defaultMain [ bench "primes" (nf (run primes) input)
, bench "primes'" (nf (run primes') input)
, bench "primes''" (nf (run primes'') input)
, bench "primesTMD" (nf (run primesTMD) input)
, bench "primes'TMD" (nf (run primes'TMD) input)
, bench "primes''TMD" (nf (run primes''TMD) input)
]
putStrLn . show . length . primes'' $ (read str :: Integer)
-- primeira implementação
primes n
| n < 2 = []
| n == 2 = [2]
| n `mod` 2 == 0 = primes'
| otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
n:primes'
else
primes'
where primes' = primes (n - 1)
primesTMD n
| n < 2 = []
| n == 2 = [2]
| n `mod` 2 == 0 = primes'
| otherwise = if (find (\x -> n `rem` x == 0) primes') == Nothing then
n:primes'
else
primes'
where primes' = primesTMD (n - 1)
-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
where sieve :: [Integer] -> [Integer]
sieve [] = []
sieve [email protected](x:xs)
| x*x >= n = l
| otherwise = x : sieve list'
where list' = filter (\y -> y `mod` x /= 0) xs
primes'TMD :: Integer -> [Integer]
primes'TMD n = sieve $ 2 : [3,5..n]
where sieve :: [Integer] -> [Integer]
sieve [] = []
sieve [email protected](x:xs)
| x*x >= n = l
| otherwise = x : sieve list'
where list' = filter (\y -> y `rem` x /= 0) xs
-- terceira implementação
primes'' :: Integer -> [Integer]
primes'' n = 2 : sieve 3 [3,5..n]
where sieve :: Integer -> [Integer] -> [Integer]
sieve _ [] = []
sieve m [email protected](x:xs)
| m*m >= n = l
| x < m*m = x : sieve m xs
| otherwise = sieve (m + 2) list'
where list'= filter (\y -> y `mod` m /= 0) l
primes''TMD :: Integer -> [Integer]
primes''TMD n = 2 : sieve 3 [3,5..n]
where sieve :: Integer -> [Integer] -> [Integer]
sieve _ [] = []
sieve m [email protected](x:xs)
| m*m >= n = l
| x < m*m = x : sieve m xs
| otherwise = sieve (m + 2) list'
where list'= filter (\y -> y `rem` m /= 0) l
Thông báo thời gian chạy cải tiến của biến thể sử dụng rem:
$ ghc --make -O2 sieve.hs
$./sieve
5000
...
benchmarking primes
mean: 23.88546 ms, lb 23.84035 ms, ub 23.95000 ms
benchmarking primes'
mean: 775.9981 us, lb 775.4639 us, ub 776.7081 us
benchmarking primes''
mean: 837.7901 us, lb 836.7824 us, ub 839.0260 us
benchmarking primesTMD
mean: 16.15421 ms, lb 16.11955 ms, ub 16.19202 ms
benchmarking primes'TMD
mean: 568.9857 us, lb 568.5819 us, ub 569.4641 us
benchmarking primes''TMD
mean: 642.5665 us, lb 642.0495 us, ub 643.4105 us
trong khi tôi thấy bạn đang làm điều này cho giáo dục của riêng bạn, giá trị của nó lưu ý các liên kết có liên quan của Primes on Haskell.org và nhanh Primes package trên hackage.
Nguồn
2010-10-04 04:39:43
1) Tiếng Anh của bạn vẫn ổn. 2) Tôi thực sự thích rằng bạn đính kèm mã runnable - vì vậy vài câu hỏi làm điều đó gần đây. 3) Bạn cũng có thể bao gồm lệnh biên dịch của bạn - một số người quên -O2 (và đã từng có một thử nghiệm -O3 tồn tại và làm chậm nhiều chương trình nhưng người mới không biết điều đó). –
Bạn có thể quan tâm đến [The Sàng chính hãng của Eratosthenes] (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) giấy. Nó bao gồm một số triển khai khác nhau (bao gồm cả sàng giả) và nói về các đặc tính hiệu suất cơ bản cũng như cung cấp một số cách để tăng tốc thuật toán. –
Một trong những thông điệp quan trọng từ bài báo “Sàng chính xác của Eratosthenes” là, mặc dù các mã như ba cái này thường được cung cấp dưới dạng “sự thực hiện rây của Eratosthenes”, hiệu suất của chúng gần với thuật toán phân chia thử nghiệm (chậm hơn so với rây của Eratosthenes (nhanh). –