Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-25

エラトステネスのふるいをちょっぴり速く

14:33

primes = sieve [2..]
    where
        sieve (x:xs) = x : sieve ([y| y <- xs, y `mod` x /= 0])

こう書いてたところを、こうしてみた。

primes = sieve (2:[3,5..])

速さ変わらず。(hugs)

こうしてみた。

primes = 2 : (sieve [3,5..])

速さ変わらず。(hugs)


発想を変えて、こうしてみた。

primes = sieve [2..]
    where
        sieve (x:xs) = x : sieve ([y| y <- xs, x*x > y || y `mod` x /= 0])

約3倍に速くなった。(hugs,GHCi,GHC コンパイル)

sqrt(n) までの数で割り切れなければ n は素数決定というやつ。x*x > y である場合は y `mod` x /= 0 を計算しなくていい。


しかし、一般的に速くなるとは限らないらしい。昨日の Goldbach 問題↓で試すと、hugs で実行したり GHC でコンパイルした場合は確かに速くなるのに、GHCi では逆に若干遅くなってしまう。(気にするところじゃないかもしれないけど)


まだ気になるのは、例えば7を素数と断定するときに、

  • 2の自乗より大きいかチェック -- True
  • 2で割れるかチェック -- False
  • 3の自乗より大きいかチェック -- False
  • 5の自乗より大きいかチェック -- False

という手順を踏んでいるのだけど、3の自乗より大きくない時点で5の自乗より大きくないのは分かっているので、そこを省略するにはどうしたらいいのだろう?


答えがあった

primes' :: [Integer]
primes' = 2:sieve' [3] [5,7..]

sieve' :: [Integer] -> [Integer] -> [Integer]
sieve' (p:ps) xs = p:sieve' (ps++ps') [x | x <- qs, mod x p /= 0]
  where (ps', qs) = span (<(p*p)) xs

ちょうど考えてたやつと同じような感じだった。ps++ps' のオーダーが ps のサイズであるのが惜しいけど、文句なしにこっちのほうが速い。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090625
 |