« Haskell でいろいろな「ソート」を考えてみた | トップページ | Project Euler : Problem 17 »

2010年3月30日 (火)

Haskell で素数列 : 1000000 個目の素数が 3.5 秒で表示されました。

 以前、こちらの記事を参考にした、「Haskell で素数を列挙するコード」に関する記事をアップしましたが、その後も、ちょこちょことコードをいじって改良を加えてきました。
 ある程度納得のいくコードができたので、現在使っているコードの紹介をしてみたいと思います。

primes :: Integral a => [a] primes = map fromIntegral ([2, 3] ++ primes' :: [Int]) where primes' = 5 : sieve [] primes' 7 sieve divs (x : xs) n = ps ++ sieve (divs ++ [x]) xs (x * x) where isPrime m = and [rem m x /= 0 | x <- divs] ps = filter isPrime ns ns = [y + z | y <- [n, n + 6 .. x * x - 2], z <- [0, 4]]
 このコードに "main = print $ primes !! (1000000 - 1)" を付け加えて 1000000 個目の素数を表示させると、
Pentium M, 1500MHz Ubuntu 9.10
と言う環境で、最適化オプションを付けてコンパイルした場合、
real 0m12.961s user 0m12.857s sys 0m0.060s
という結果がでました。

 では、実際にどこを改良したかというと……

1. 型を工夫して式を一つにまとめた

 以前はコードが二つに分かれていました。
 そこで今回は、型の指定方法を工夫して、内部的には [Int] で計算していますが、最終的な結果は必要に応じて [Int] と [Integer] のどちらでも取り出せるようにしました。

2. and + map でコードを簡略化した

 以前、「素数の判定を行う関数で "all" を使うと遅くなる」ということを書きました。
 その後もいろいろ試した結果、and と map を組み合わせて使った場合は、ほとんどスピードが落ちないことが分かりました。そこで素数の判定をする関数 "isPrime" を and と map (実際にはリスト内包表記)を使って書くことで式を簡略化しました。
 ちなみに "all" を使って "isPrime" を書き直した場合、上記と同じ条件で実行すると、
real 0m19.350s user 0m19.233s sys 0m0.068s
という結果になりました。
 "The Haskell 98 Report" を見る限り、定義上は all と and map は同じはずなのですが、実際にコードを書いて比べてみると、かなりの差が出てしまいます。
 こちらの記事にも素数を列挙するコードがありますが、このコードも "all" の部分を "and $ map" に書き換えるだけでさらにスピードアップするようです。

3.素数の候補をさらにしぼった

 以前のコードでは素数の候補は奇数でした。
 今回は「素数は必ず、6n+1 または 6n+5 の形になる」と言う事実を利用して、素数の候補から偶数と 3 の倍数を予め除去しました。


 これまでの経験から、素数判定が速ければそれだけでかなり速く素数列を作れそうな気がしたので、試しにひたすら素数判定をしていくコードをもうひとつ作ってみました。

primes2 :: Integral a => [a] primes2 = map fromIntegral ([2, 3] ++ primes' :: [Int]) where isPrime m (x : xs) | x * x > m = True | rem m x == 0 = False | otherwise = isPrime m xs primes' = 5 : sieve 1 sieve n = filter (`isPrime` primes') ns ++ sieve (n + 1000) where ns = [6 * x + y | x <- [n .. n + 999], y <- [1, 5]]
 このコードを使って上記の条件で 1000000 個目の素数を表示させると
real 0m12.753s user 0m12.629s sys 0m0.048s
という結果になりました。
 本当にただひたすら素数判定を繰り返すだけのコードなのに、いろいろとリスト操作を工夫した最初のコードとスピード的にほとんど同じという結果になりました。


 ちなみに表題の「3.5 秒」というは、会社のコンピュータ(Core Duo 2.8GHz, Windows XP) にこっそり Haskell(GHC) をインストールして primes2 を実行したら、1000000 個目の素数が表示されるのに 3.5 秒しかかからなかったということなんです。
 CPU の違いでこんなにも差が出るんですねぇ……。うちのパソコンもそろそろ買い換えたいなぁ……。

« Haskell でいろいろな「ソート」を考えてみた | トップページ | Project Euler : Problem 17 »

Haskell」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47952220

この記事へのトラックバック一覧です: Haskell で素数列 : 1000000 個目の素数が 3.5 秒で表示されました。:

« Haskell でいろいろな「ソート」を考えてみた | トップページ | Project Euler : Problem 17 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ