素数滤波器的两种实现的性能比较

Question

我有两个程序来查找素数（只是一个练习，我正在学习Haskell）。"primes"比"primes2"快10倍，一旦使用ghc（带有标志-O）编译。但是，在"primes2"中，我认为它只会考虑除数测试的素数，这应该比考虑"isPrime"中的奇数更快，对吧？我错过了什么？

isqrt :: Integral a => a -> a  
isqrt = floor . sqrt . fromIntegral
isPrime :: Integral a => a -> Bool  
isPrime n = length [i | i <- [1,3..(isqrt n)], mod n i == 0] == 1
primes :: Integral a => a -> [a]  
primes n = [2,3,5,7,11,13] ++ (filter (isPrime) [15,17..n])
primes2 :: Integral a => a -> [a]  
primes2 n = 2 : [i | i <- [3,5..n], all ((/= 0) . mod i) (primes2 (isqrt i))]

Answer 1

我认为

这里发生的事情是isPrime是一个简单的循环，而primes2是递归地调用自己的——它的递归模式对我来说看起来是指数级的。

搜索我的旧源代码，我找到了以下代码：

primes :: [Integer]
primes = 2 : filter isPrime [3,5..]
isPrime :: Integer -> Bool
isPrime x = all (n -> x `mod` n /= 0) $
            takeWhile (n -> n * n <= x) primes

这只针对sqrt(x)以下的素数测试每个可能的素数x，使用已经生成的素数列表。 因此，它可能不会多次测试任何给定的素数。

哈斯克尔的记忆：

Haskell中的记忆通常是明确的，而不是隐含的。 编译器不会"做正确的事"，但它只会做你告诉它的事情。 当你打电话给primes2 ，

*Main> primes2 5
[2,3,5]
*Main> primes2 10
[2,3,5,7]

每次调用该函数时，它都会重新计算其所有结果。 它必须这样做。 为什么？ 因为 1） 你没有让它保存它的结果，2） 每次调用它时答案都不同。

在我上面给出的示例代码中，primes是一个常量（即它的 arity 为零），因此内存中只有一个副本，并且其部分只被评估一次。

如果你想要记忆，你需要在你的代码中的某个地方有一个 arity 为 0 的值。

Answer 2

我喜欢

迪特里希对记忆所做的工作，但我认为这里也存在数据结构问题。 列表不是理想的数据结构。它们必然是 lisp 风格的缺点单元，没有随机访问。 套装似乎更适合我。

import qualified Data.Set as S
sieve :: (Integral a) => a -> S.Set a
sieve top = let l = S.fromList (2:3:([5,11..top]++[7,13..top]))
                 iter s c
                    | cur > (div (S.findMax s) 2) = s
                    | otherwise = iter (s S.\ (S.fromList [2*cur,3*cur..top])) (S.deleteMin c)
                    where cur = S.findMin c
             in iter l (l S.\ (S.fromList [2,3]))

我知道它有点丑陋，而且不太声明，但它运行得相当快。 我正在寻找一种方法，使用复合材料上的Set.fold和Set.union使其看起来更好。 任何其他整理它的想法将不胜感激。

PS - 看看(2:3:([5,11..top]++[7,13..top]))如何避免不必要的 3 倍数，例如primes中的 15 . 不幸的是，如果您使用列表并注册排序，这会破坏您的排序，但对于集合来说，这不是问题。