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 のサイズであるのが惜しいけど、文句なしにこっちのほうが速い。


unwordsはO(n^2)?

14:34

unwords          :: [String] -> String
unwords []       =  ""
unwords ws       =  foldr1 (\w s -> w ++ ' ':s) ws

w は継ぎ足す度にどんどん大きくなっていく。単語の長さの平均を a とすると、w の大きさは最初が a、次が 2*a、次が 3*a、となる。全体のステップ数は

a + 2*a + 3*a + ... + n*a = a*n*(n+1)/2

で O(n^2) だと思うんだけど、print に繋げる場合などは、出来た部分から順に出力していけばいいのだから (実際そうなってる) 最適化されるのだろうか?

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