« 2010年2月 | トップページ | 2010年4月 »

2010年3月

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 の違いでこんなにも差が出るんですねぇ……。うちのパソコンもそろそろ買い換えたいなぁ……。

2010年3月 5日 (金)

Haskell でいろいろな「ソート」を考えてみた

 Haskell 関連の記事をネットで探していたら、ここここにソートに関する記事がありました。自分ならどうコーディングするかな?と思って、Haskell の練習のためにいろいろなソートを書いてみました。

 まずは、Haskell といえば「クイックソート」ですね。

import Data.List quickSort :: Ord a => [a] -> [a] quickSort [] = [] quickSort (x : xs) = quickSort as ++ [x] ++ quickSort bs where (as, bs) = partition (< x) xs
 ところがこのアルゴリズムは、リストの先頭の値をピボットにしているため、リストの大部分が既にソート済みの場合、極端にスピードが落ちます。
 そこで、リストの中央の位置にある値をピボットにするようにしてみました。
import Data.List quickSort :: Ord a => [a] -> [a] quickSort [] = [] quickSort ns = quickSort as' ++ [b] ++ quickSort bs' where (as, b : bs) = splitAt (div (length ns) 2) ns (as', bs') = partition (< b) (as ++ bs)
 こちらは完全にランダムなリストを与えた場合、前のコードより少し遅くなりますが、ソート済みのリストを与えてもまったく遅くなりません。

 次は「挿入ソート」を考えてみましょう……と思ったら、Haskell の Data.List モジュールにそのものずばり "insert" という関数がありました。

import Data.List insertionSort :: Ord a => [a] -> [a] insertionSort = foldr insert []
 おかげでこんなに簡単に書けてしまいました。

 アルゴリズム的に簡単と言われている「バブルソート」も考えてみました。
 このアルゴリズムは、隣り合う要素を入れ替える操作を頻繁に行うので、配列と繰り返しの組み合わせでは簡単にコーディングできます。例えば Ruby であれば次のようなコードになります。

# Ruby 版 バブルソート class Array def bubble_sort arr = Array.new(self) len = arr.size - 2 0.upto(len) do |i| 0.upto(len - i) do |j| arr[j], arr[j + 1] = arr[j + 1], arr[j] if arr[j] > arr[j + 1] end end return arr end end
 ところが Haskell では配列は使いにくいので、代わりにリストを使おうとすると結構面倒くさいことになりました。
bubbleSort :: Ord a => [a] -> [a] bubbleSort ns = iter ns [] [] True where iter (x1 : x2 : xs) tmp prd flag | x1 <= x2 = iter (x2 : xs) (x1 : tmp) prd flag | otherwise = iter (x1 : xs) (x2 : tmp) prd False iter [x] tmp prd flag | flag = reverse tmp ++ (x : prd) | otherwise = iter (reverse tmp) [] (x : prd) True iter [] _ prd _ = prd
 "reverse" を頻繁に使う割には結構速いかな?ネットで見つけた他のバブルソートよりは速いです(とはいえ、クイックソートとは比べ物にならないくらい遅いです)。
 結論としては、「バブルソートを Haskell でしてはいけない」ということでしょうか?

 続いては「マージソート」です。これは「クイックソート」と同じくらい速いです。

mergeSort :: Ord a => [a] -> [a] mergeSort xs = ms (length xs) xs where ms _ [] = [] ms _ [x] = [x] ms n xs = merge (ms m as) (ms (n - m) bs) where m = div n 2 (as, bs) = splitAt m xs merge xs [] = xs merge [] ys = ys merge xs@(x : xs') ys@(y : ys') | x <= y = x : merge xs' ys | otherwise = y : merge xs ys'

 

 

※追記 2010/11/25 : Ruby 版バブルソートのコードが、あまり Ruby っぽくなかったのと、破壊的なメソッドになっていたのが気に入らなかったので、書き換えました。

« 2010年2月 | トップページ | 2010年4月 »

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            
フォト

最近のトラックバック

無料ブログはココログ