++，最后一个& amp;初始化比:，head& amp;更快尾巴? [英] ++, last & init faster than :, head & tail?

问题描述

考虑到以下两种编写函数的方法，该函数可以找到所有素数直至特定数字:

Given these two ways of writing a function that finds all primes up to a specific number:

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 & primesTo2 中使用的 tail .

Why is primesTo1 a lot faster than primesTo2, even though the different functions used; primesTo1 uses ++, last & init instead of :, head & tail used in primesTo2.

带有:set + s 的 ghci 的输出:

*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寻找最佳的质数生成器，我只是对两个函数的速度差异感到困惑.

---

Note: I'm not looking for an optimal prime number generator for Haskell, I'm just confused by the speed differences of the two functions.

推荐答案

"nm"指出，其原因是 primes2 首先尝试除以找到的最大质数，而 primes1 从最低的开始.

As pointed out by the "n.m.", the reason for this is that primes2 first tries to divide by the largest found primes, while primes1 starts with the lowest.

因此，首先反转当前素数的列表，然后在 all 中使用它们实际上比 primes1 和 primes2 都快:

So first reversing the list of current primes, before using them in all is actually faster than both primes1 and 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

以 10000 作为参数的

ghci 速度:

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

并使用 ghc -O2 进行编译:

$ time ./primes3
...
./primes  0.05s user 0.00s system 24% cpu 0.209 total

这篇关于++，最后一个& amp;初始化比:，head& amp;更快尾巴?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！