3

给定这两种编写函数的方法，该函数可以找到直到特定数字的所有素数：

primes1 = iterate
    (\ps -> ps ++ [([x |
        x <- [last ps + 1..],
        all (\p -> x `mod` p /= 0) ps] !! 0)])
    [2]

primesTo1 :: Integer -> [Integer]
primesTo1 n = init $ head $ dropWhile (\p -> last p <= n) primes1

primes2 = iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) ps] !! 0)
        : ps)
    [2]

primesTo2 :: Integer -> [Integer]
primesTo2 n = tail $ head $ dropWhile (\p -> head p <= n) primes2

为什么primesTo1比 快很多primesTo2，即使使用了不同的功能；primesTo1使用++, last&init代替:, head&tail用于primesTo2.

ghci的输出:set +s：

*Main> primesTo1 10000
...
(0.51 secs, 124779776 bytes)
*Main> primesTo2 10000
...
(3.30 secs, 570648032 bytes)

编译ghc -O2：

$ time ./primes1
...
./primes1  0.06s user 0.00s system 68% cpu 0.089 total
$ time ./primes2
...
./primes2  0.28s user 0.00s system 98% cpu 0.283 total

注意：我不是在为 Haskell 寻找最佳素数生成器，我只是对这两个函数的速度差异感到困惑。

4

2 回答 2

2

正如“nm”所指出的，这样做的原因是primes2首先尝试除以最大的找到的素数，而primes1从最低的开始。

因此，首先反转当前素数列表，然后再使用它们all实际上比两者都快primes1和primes2：

primes3 = iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) $ reverse ps] !! 0)
        : ps)
    [2]

primesTo3 :: Integer -> [Integer]
primesTo3 n = tail $ head $ dropWhile (\p -> head p <= n) primes3

ghci10000作为参数的速度：

*Main> primesTo3 10000
...
(0.41 secs, 241128512 bytes)

并编译ghc -O2：

$ time ./primes3
...
./primes  0.05s user 0.00s system 24% cpu 0.209 total
于 2013-05-15T17:15:01.723 回答
1

我知道您说您“不是在为 Haskell 寻找最佳素数生成器”，但您仍然对“两个函数的速度差异”感兴趣。所以这里对你的更正函数进行了更多的句法操作primes3，它以相反的顺序添加素数(:)，并且每次都将它们反转以进行测试，

primes3 :: [[Integer]]
primes3 = iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) $
                takeWhile (\p-> p*p <= x) $ reverse ps] !! 0)
        : ps)                            -- ^^^^^^^^^^
    [2]

这段代码可以修改（虽然这不会改变效率）：

primes3b :: [[Integer]]
primes3b = iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) $
                takeWhile (\p-> p*p <= x) $ map head $ primes3b ] !! 0)
        : ps)                            -- ^^^^^^^^^^^^^^^^^^^
    [2]

不是吗？这相当于（注意类型更改）

primes4 :: [Integer]
primes4 = map head $ iterate
    (\ps -> ([x |
            x <- [head ps + 1..],
            all (\p -> x `mod` p /= 0) $
                takeWhile (\p-> p*p <= x) primes4 ] !! 0)
        : ps)                          -- ^^^^^^^
    [2]

这与

primes5 :: [Integer]
primes5 = iterate
    (\p -> head [x | x <- [p + 1..],
                 all (\p -> x `mod` p /= 0) $
                   takeWhile (\p-> p*p <= x) primes5 ] 
           ) -- nothing!
    2

或者，快一点，

primes6 :: [Integer]
primes6 = 2 : iterate
    (\p -> head [x | x <- [p + 2, p + 4..],
                 all (\p -> x `mod` p /= 0) $ tail $
                   takeWhile (\p-> p*p <= x) primes6 ] )
    3           -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

最后，（事实证明，速度和经验增长顺序有相当大的提高） - 为什么每次迭代只添加一个数字，花费工作来获取要测试的素数？我们可以通过连续素数平方之间的部分来工作。对于这些段，获取的素数列表具有相同的长度，并且该长度从段到段增加 1：

primes7 :: [Integer]
primes7 = concatMap snd $ iterate 
              (\((n,p:ps@(q:_)),_) -> ((n+1,ps),
                       [x | let lst = take n $ tail primes7,
                            x <- [p*p + 2, p*p + 4..q*q-2],
                            all ((/= 0).rem x) lst]))
              ((1,tail primes7),[2,3,5,7])

这实际上表达了最优的试划分筛。

于 2013-05-16T22:47:05.240 回答