haskell - haskell 的埃拉托斯特尼筛法

Question

我正在解决 Haskell 中的一些经典问题来开发我的函数 技能，我在实现此建议的优化时遇到问题"Programming Praxis"站点:

这个问题我有三种解决方案，第三种太慢了 与第二种解决方案相比。有人可以建议一些改进吗 我的代码？

我的实现是:

-- 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 作为 m 传递，并且您将执行额外的递归来过滤 9，即使它甚至不在列表中，因此您不应该在第一名(因为它会在 3 的第一个过滤器中被删除)

尽管第二个版本不会开始过滤超过其筛选数字的平方，但它永远不会选择不必要的筛选值。

换句话说，我认为你最终会筛选 3 到 n 之间的每个奇数。相反，您应该筛选上一次传递中尚未删除的每个奇数。

我认为要正确实现在当前 sift 值的平方处启动筛选的优化，您必须保留列表的前面，同时在后面进行筛选，其中后面包含的元素 >= sift 值的平方。我认为这会迫使您使用串联，而且我不太确定优化是否足以抵消使用++ 引起的开销。