3

特定の数までのすべての素数を見つける関数を作成する次の 2 つの方法があるとします。

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が よりもはるかに高速なのはなぜですか。で使用される, &の代わりに, &を使用します。primesTo2primesTo1++lastinit:headtailprimesTo2

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 に最適な素数ジェネレーターを探しているわけではありません。2 つの関数の速度の違いに混乱しているだけです。

4

2 に答える 2

2

「nm」で指摘されているように、この理由は、primes2最初に見つかった最大の素数で除算を試みprimes1、最小のものから開始するためです。

したがって、最初に現在の素数のリストを逆にしてから、 でそれらを使用する方が、とallの両方よりも実際には高速です。primes1primes2

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に最適な素数ジェネレーターを探していない」と言ったことは知っていますが、「2つの関数の速度の違い」にはまだ興味がありました。したがって、修正された関数 の構文操作をさらにいくつか示します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 つだけ追加するのはなぜでしょうか? 素数の連続する正方形の間の部分で作業できます。フェッチされた素数リストは、これらのセグメントで同じ長さであり、その長さはセグメントごとに 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 に答える