埃拉托色尼在Haskell的筛

Question

我解决哈斯克尔一些经典的问题，发展我的功能 技能，我有一个问题，以实现在此“实践编程能力”提出的优化网站：

我有三种解决这个问题，第三个是太慢 相比于第二溶液。有人建议可以给一些改进 我的代码？

我的实现方式是：

-- 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)

-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `mod` 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 l@(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

Answer 1

在我看来像你的第三次修改的问题是，你如何选择下一个元素进行筛选的。 你胡乱按2递增的问题是，你再上不必要的号码筛选。 例如，在这个版本中你最终要通过9米，你会做一个额外的递归滤波月9日，即使它甚至不是在列表中，这样的话你应该从来没有把它在首位（因为这将在3中的第一个过滤器已被移除）

即使第二版本不启动过去它进行筛选，对数的平方的滤波，它从未选择的不必要的筛选值。

在换句话说，我想你最终3和n之间过筛上的每个奇数。相反，你应该筛选对尚未由先前的通去除每个奇数。

我认为正确实现在当前筛值的平方开始筛的优化，则必须保留列表的前面，而在那里回来包含的元素后筛选> =该筛值的平方。我认为这将迫使你使用串连，我不那么肯定的优化是不够好，以抵消使用++引起的开销。

Answer 2

首先，mod是缓慢，在情况下使用rem它并不重要（当你不使用底片处理，基本上）。其次，使用标准显示（自己）什么是速度更快，什么样的变化实际上是优化。我知道我不给一个完整的答案，你有这个问题，但它是一个好地方，你（和其他潜在的应答者）来启动，所以这里的一些代码：

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 l@(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 l@(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 l@(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 l@(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

注意的改进的运行时使用的变体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

当我看到你在做这个为自己的教育，其值得一提的素数对Haskell的相关链接.ORG 和上hackage快速素数包。