Hi,
When I refactor my Segmented Seive of Eratosthenes, I'm puzzled by the performance of "foldr".
Here is my original code. I realized that "sieveWith"(Integral a => ([a], [a]) -> ([a], [a]), it takes a tuple with sieving primes and prime candidates, and remove all multiplies of sieving primes in candidates, at last return a tuple with blank sieving primes and a pure primes list) in "primesFromTo" is not much readable and can be replaced by "foldr".
But when I did, I find it would take about 5 seconds to sieve primes between 999900000 and 1000000000, whereas the original one just takes 1.6
seconds. The "sieveWith" function is the only place I change. I also have tried foldr', which does not much help. Is foldr slow? Or did I make any
mistake? Thanks.
=== Origin (./main < data1.txt 1.45s user 0.11s system 99% cpu 1.562 total) ===
{-# OPTIONS_GHC -O2 #-}
import Data.List
import System.IO
minus (x:xs) (y:ys) = case (compare x y) of
LT -> x : minus xs (y:ys)
EQ -> minus xs ys
GT -> minus (x:xs) ys
minus xs _ = xs
intSqrt :: Integral a => a -> a
intSqrt = floor . sqrt . fromIntegral
primesTo :: Integral a => a -> [a]
primesTo x = 2 : sieve [3, 5 .. x] where
sieve ns <at> (n : rs)
| n <= intSqrt x = n : sieve (rs `minus` [n * n, n * (n + 2) .. x])
| otherwise = ns
sieve [] = []
candidatesBetween :: Integral a => a -> a -> [a]
candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y]
primesFromTo :: Integral a => a -> a -> [a]
primesFromTo x y
| x < 2 = primesTo y
| otherwise = snd . sieveWith $ (primes, candidates) where
primes = tail . primesTo . intSqrt $ y
candidates = candidatesBetween x y
sieveWith (a : as, bs' <at> (b : bs)) = sieveWith (as, bs' `minus` multiplies a b) where
sieveWith ([], bs) = ([], bs)
multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y]
primesFromTo' [x, y] = primesFromTo x y
main :: IO ()
main = do
count <- fmap read getLine
inputLines <- fmap (take count . lines) getContents
let answers = map (primesFromTo' . map read . words) inputLines
putStr . unlines . map (unlines . map show) $ answers
=== Origin ===
=== New (./main < data1.txt 4.76s user 0.15s system 99% cpu 4.917 total) ===
{-# OPTIONS_GHC -O2 #-}
import Data.List
import System.IO
minus (x:xs) (y:ys) = case (compare x y) of
LT -> x : minus xs (y:ys)
EQ -> minus xs ys
GT -> minus (x:xs) ys
minus xs _ = xs
intSqrt :: Integral a => a -> a
intSqrt = floor . sqrt . fromIntegral
primesTo :: Integral a => a -> [a]
primesTo x = 2 : sieve [3, 5 .. x] where
sieve ns <at> (n : rs)
| n <= intSqrt x = n : sieve (rs `minus` [n * n, n * (n + 2) .. x])
| otherwise = ns
sieve [] = []
candidatesBetween :: Integral a => a -> a -> [a]
candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y]
primesFromTo :: Integral a => a -> a -> [a]
primesFromTo x y
| x < 2 = primesTo y
| otherwise = sieveWith primes candidates where
primes = tail . primesTo . intSqrt $ y
candidates = candidatesBetween x y
-- sieve a list of candidates with sieving primes
-- foldr version: ./main < data1.txt 4.76s user 0.15s system 99% cpu 4.917 total
sieveWith ps' <at> (p : ps) cs' <at> (c : cs) = foldr (\a b -> b `minus` (multiplies a c)) cs' ps'
sieveWith [] cs = cs
multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y]
primesFromTo' [x, y] = primesFromTo x y
main :: IO ()
main = do
count <- fmap read getLine
inputLines <- fmap (take count . lines) getContents
let answers = map (primesFromTo' . map read . words) inputLines
putStr . unlines . map (unlines . map show) $ answers
=== New ===
Best regards,
Zhi-Qiang Lei
RSS Feed