« Project Euler : Problem 57 ~ 漸化式 | トップページ | Haskell で「エラトステネスの篩」 その2 »

2010年12月29日 (水)

Haskell で「エラトステネスの篩」

 Haskell では通常の配列は書き換えのコストが高いので、 Ruby で Project Euler を解くときに作った"prime_list"のような、配列をバリバリ書き換えていくような「エラトステネスの篩」は使い物になりませんでした。
 たぶん STArray あたりを使えば、書き換えのコストが低くなるので実現できそうな気はしていましたが、モナドの知識が不足していて手が出せませんでした。

 そんな時、STArray を使った「エラトステネスの篩」を実際にコーディングしている記事を見つけました。
 STArray 以外にも unsafeRead や unsafeWrite なども使われていて、とてつもなく速いコードでした。
 ただ、よく見ると「sieve 関数」のアルゴリズムに若干改良の余地があったので、ちょっと手を加えてみました。

import Control.Monad import Data.Array.ST import Data.Array.Unboxed import Data.Array.Base(unsafeRead, unsafeWrite, unsafeAt) sieve :: Int -> UArray Int Bool sieve n = runSTUArray $ do arr <- newArray (0, n) True unsafeWrite arr 0 False unsafeWrite arr 1 False let end = floor $ sqrt (fromIntegral n) remove_multiples arr 1 4 loop arr end 3 return arr where loop arr end k | k > end = return () | otherwise = do v <- unsafeRead arr k when v $ remove_multiples arr k (k * k) loop arr end (k + 2) remove_multiples arr p k | k > n = return () | otherwise = do unsafeWrite arr k False remove_multiples arr p (k + p + p)

 ほんのちょっとの手直しなので、どこが変わったか分からないかもしれませんね。
 でも、このちょっとの改良でけっこう速くなったんですよ。家のパソコンで一億までの素数の和を求めたとき、改良前が 3.68s だったのが、改良後は 2.53s になりました。

 それから、この「sieve 関数」を使って素数のリストを返す関数も考えてみました。

primeList :: Int -> [Int] primeList n = [p | (p, bool) <- assocs $ sieve n, bool]

 素数の上限を指定しなければならないという制限はありますが、自作の「primes 関数」よりかなり高速です。

※追記 : 12/29 に書いた記事のコードが間違ってたため、 12/30 にコードの部分だ けを書き換えました。

« Project Euler : Problem 57 ~ 漸化式 | トップページ | Haskell で「エラトステネスの篩」 その2 »

Haskell」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Haskell で「エラトステネスの篩」:

« Project Euler : Problem 57 ~ 漸化式 | トップページ | Haskell で「エラトステネスの篩」 その2 »

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

最近のトラックバック

無料ブログはココログ