<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi,<div><br></div><div>When I refactor my Segmented Seive of Eratosthenes, I'm puzzled by the performance of "foldr".</div><div>Here is my original code. I realized that "sieveWith"(<font class="Apple-style-span" color="#7a7a7a"><i>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</i></font>) in "primesFromTo" is not much readable and can be replaced by "foldr".</div><div><div><br></div><div>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 </div><div>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 </div><div>mistake? Thanks.</div></div><div><br></div><div>=== Origin (./main < data1.txt 1.45s user 0.11s system 99% cpu 1.562 total) ===</div><div><div>{-# OPTIONS_GHC -O2 #-}</div><div><br></div><div>import Data.List</div><div>import System.IO</div><div><br></div><div>minus (x:xs) (y:ys) = case (compare x y) of </div><div> LT -> x : minus xs (y:ys)</div><div> EQ -> minus xs ys </div><div> GT -> minus (x:xs) ys</div><div>minus xs _ = xs</div><div><br></div><div>intSqrt :: Integral a => a -> a</div><div>intSqrt = floor . sqrt . fromIntegral</div><div><br></div><div>primesTo :: Integral a => a -> [a]</div><div>primesTo x = 2 : sieve [3, 5 .. x] where</div><div> sieve ns@(n : rs)</div><div> | n <= intSqrt x = n : sieve (rs `minus` [n * n, n * (n + 2) .. x])</div><div> | otherwise = ns</div><div> sieve [] = []</div><div><br></div><div>candidatesBetween :: Integral a => a -> a -> [a]</div><div>candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y]</div><div><br></div><div>primesFromTo :: Integral a => a -> a -> [a]</div><div>primesFromTo x y</div><div> | x < 2 = primesTo y</div><div> | otherwise = snd . sieveWith $ (primes, candidates) where</div><div> primes = tail . primesTo . intSqrt $ y</div><div> candidates = candidatesBetween x y</div><div><b> sieveWith (a : as, bs'@(b : bs)) = sieveWith (as, bs' `minus` multiplies a b) where</b></div><div><b> sieveWith ([], bs) = ([], bs)</b></div><div> multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y]</div><div><br></div><div>primesFromTo' [x, y] = primesFromTo x y</div><div><br></div><div>main :: IO ()</div><div>main = do</div><div> count <- fmap read getLine</div><div> inputLines <- fmap (take count . lines) getContents</div><div> let answers = map (primesFromTo' . map read . words) inputLines</div><div> putStr . unlines . map (unlines . map show) $ answers</div></div><div><br></div><div>=== Origin ===</div><div><br></div><div>=== New (./main < data1.txt 4.76s user 0.15s system 99% cpu 4.917 total) ===</div><div><div>{-# OPTIONS_GHC -O2 #-}</div><div><br></div><div>import Data.List</div><div>import System.IO</div><div><br></div><div>minus (x:xs) (y:ys) = case (compare x y) of </div><div> LT -> x : minus xs (y:ys)</div><div> EQ -> minus xs ys </div><div> GT -> minus (x:xs) ys</div><div>minus xs _ = xs</div><div><br></div><div>intSqrt :: Integral a => a -> a</div><div>intSqrt = floor . sqrt . fromIntegral</div><div><br></div><div>primesTo :: Integral a => a -> [a]</div><div>primesTo x = 2 : sieve [3, 5 .. x] where</div><div> sieve ns@(n : rs)</div><div> | n <= intSqrt x = n : sieve (rs `minus` [n * n, n * (n + 2) .. x])</div><div> | otherwise = ns</div><div> sieve [] = []</div><div><br></div><div>candidatesBetween :: Integral a => a -> a -> [a]</div><div>candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y]</div><div><br></div><div>primesFromTo :: Integral a => a -> a -> [a]</div><div>primesFromTo x y</div><div> | x < 2 = primesTo y</div><div> | otherwise = sieveWith primes candidates where</div><div> primes = tail . primesTo . intSqrt $ y</div><div> candidates = candidatesBetween x y</div><div><b> -- sieve a list of candidates with sieving primes</b></div><div><b> -- foldr version: ./main < data1.txt 4.76s user 0.15s system 99% cpu 4.917 total</b></div><div><b> sieveWith ps'@(p : ps) cs'@(c : cs) = foldr (\a b -> b `minus` (multiplies a c)) cs' ps'</b></div><div><b> sieveWith [] cs = cs</b></div><div> multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y]</div><div><br></div><div>primesFromTo' [x, y] = primesFromTo x y</div><div><br></div><div>main :: IO ()</div><div>main = do</div><div> count <- fmap read getLine</div><div> inputLines <- fmap (take count . lines) getContents</div><div> let answers = map (primesFromTo' . map read . words) inputLines</div><div> putStr . unlines . map (unlines . map show) $ answers</div></div><div><br></div><div>=== New ===</div><div><div apple-content-edited="true">
<div><br class="Apple-interchange-newline">Best regards,<br class="Apple-interchange-newline">Zhi-Qiang Lei</div><div><a href="mailto:zhiqiang.lei@gmail.com">zhiqiang.lei@gmail.com</a></div>
</div>
<br></div></body></html>