++，last& init比：，head&尾巴？ [英] ++, last & init faster than :, head & tail?

问题描述

给出这两种写函数的方法，可以找到所有素数达到特定数字的元素：

  primes1 = iterate 
（\ ps  - > ps ++ [（[x | 
x<  -  [last ps + 1 ..]，
 all（\p  - > x`mod` p / = 0）ps] !! 0）]）
 [2] 
 
 primesTo1 :: Integer  - > [整数] 
 primesTo1 N = INIT $ $头dropWhile（\p  - >最后P< = N）primes1 
 
 primes2 =迭代
（\ps  - >（[x | 
x<  -  [head ps + 1 ..]，
 all（\ p  - > x` mod` p / = 0）ps] !! 0）
：ps）
 [2] 
 
 primesTo2 ::整数 - > [Integer] 
 primesTo2 n = tail $ head $ dropWhile（\ p  - > head p <= n）primes2 
  

为什么 primesTo1 比 primesTo2 快很多，即使使用了不同的函数; primesTo1 使用 ++ ，上次& init 而不是：，头& $ 。 c $ c> ghci with ：set + s ：



  *主> primesTo1 10000 
 ... 
（0.51秒，124779776字节）
 * Main> primesTo20000 
 ... 
（3.30秒，570648032字节）
  

编译 ghc -O2 ：



  $ time ./primes1 
 ... 
 ./primes1 0.06s用户0.00s系统68％cpu 0.089 total 
 $ time ./primes2 
 ... 
 ./primes2 0.28s用户0.00s系统98％cpu 0.283总计
  

---


注意：我不想为Haskell寻找一个最佳的素数生成器，我只是因为这两个函数的速度差异而感到困惑。 解决方案

正如nm所指出的，其原因是 primes2 首先尝试除以最大的找到的素数，而因此，首先在当前素数列表中反转，然后在 all 中使用它们， code>实际上快于 primes1 和 primes2 ：

  primes3 =迭代
 （\ps  - > （[x | 
x<  -  [head ps + 1 ..]，
 all（\ p  - > x`mod` p / = 0）$ reverse ps] !! 0）
：ps）
 [2] 
 
 primesTo3 ::整数 - > primes3 
  

ghci 以 10000 作为参数的速度：

  * Main> primesTo30000 
 ... 
（0.41秒，241128512字节）
  

和用 ghc -O2 编译：



  $ time ./primes3 
 ... 
 ./primes 0.05s用户0.00s系统24％cpu 0.209总额
  




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

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.

Output of ghci with :set +s:

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

Compiled with 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

---

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.

解决方案

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.

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

ghci speed with 10000 as argument:

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

and compiled with ghc -O2:

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

这篇关于++，last& init比：，head&尾巴？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！