« Haskell で「順列」と「組み合わせ」 | トップページ | Project Euler : Problem 15 ~ 組み合わせ »

2010年2月21日 (日)

Project Euler : Problem 14 ~ Collatz 問題とメモ化

 問題はこちらをご覧ください。

 

 お馴染みの「Collatz 問題」ですね。
 まずは、Brute force 版です。

import Data.List (maximumBy) import Data.Ord (comparing) collatz :: Integral a => a -> Int -> Int collatz 1 c = c collatz n c | even n = collatz (div n 2) (c + 1) | otherwise = collatz (n * 3 + 1) (c + 1) problem014 :: Integral a => a -> (a, Int) problem014 n = maximumBy (comparing snd) xs where xs = [(x, collatz x 1) | x <- [2 .. n]] main = print $ problem014 1000000
 単純に定義どおりにステップ数を数えただけです。最後に "maximumBy" でステップ数の一番多いものを探しました。
 何の工夫もしていないので約 14 秒もかかってしまいました。

 そこで Ruby 1.9 で解いたときと同じように、配列によるメモ化の手法を使ってみました。
 Haskell の配列は書き換えにコストがかかるという話を聞いたことがあったのですが、今回コードでは書き換えは行われないので大丈夫だと思います。

import Data.Array import Data.List (maximumBy) import Data.Ord (comparing) problem014 :: Integer -> (Integer, Int) problem014 n = maximumBy (comparing snd) (assocs arr) where arr = listArray (1, n) (1 : [collatz i i 0 | i <- [2 .. n]]) collatz n m c | m < n = (arr ! m) + c | even m = collatz n (div m 2) (c + 1) | otherwise = collatz n (m * 3 + 1) (c + 1) main = print $ problem014 1000000
 今回は約 2.7 秒で答えが出ました。やはり、かなりのスピードアップになりました。
 Haskell の配列はリストと違っていろいろと制約があったりして、使いこなすにはまだまだ勉強が必要そうです。

« Haskell で「順列」と「組み合わせ」 | トップページ | Project Euler : Problem 15 ~ 組み合わせ »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

すいません教えてください。
私の環境Intel(R) Core(TM)2 Duo CPU @ 2.53GHz ではこのコードが14秒でうごないんですが特別な方法があるのでしょうか?

$ ghc -rtsopt 14.hs
$ ./14 +RTS -K100M

としないとスタックオーバフローになります。

すみません。説明が少し足りなかったようです。

ghc には「最適化オプション(-O)」というのがあって、コンパイル時に ghc が自動的にいろいろな最適化をしてくれるみたいです。
私のコードは全て「最適化オプション」をつけてコンパイルした上で時間を測定しています。

今回のコードは、ソースコードのファイル名が "14.hs" だった場合、
$ ghc -O -o 14 14.hs
とすることで「最適化」されたコードが出来上がります。
Linux の場合、
$ time ./14
とすることで実行時間が測定できます。

もし、コンパイル後に "compilation IS NOT required" と表示されたら、以前コンパイルした "14" というファイルが残っていて、新にコンパイルされなかった可能性がありますので、その場合には
$ ghc -O -o 14 14.hs -fforce-recomp
と打ち込んでみてください。

ありがとうございます。
本当ですね。私はData.Listのfoldl'で正格化させて計算するしか方法が無いと思ってましたが

$ touch 14-4.hs ; ghc -O 14-4.hs ; sleep 1 ; time ./14-4
[1 of 1] Compiling Main ( 14-4.hs, 14-4.o )
Linking 14-4 ...
(837799,525)

real:0m0.721s,user:0m0.704s,sys:0m0.016s

なぜ-Oをつけるだけで正格化の問題から開放されるのでしょうか?

なぜでしょうねぇ……。
私も Haskell や GHC の細かい所は良く知らないんです。どなたか詳しい方、私にも教えてください。

そうですか。

$ echo "main=print $ foldl (+) 0 [1..10^6]" > a.hs; ghc -v0 -O a.hs -prof ; sleep 1; time ./a
500000500000

real:0m0.168s,user:0m0.164s,sys:0m0.000s

でもすごいですね。ありがとうございます。大変参考になりました。

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 14 ~ Collatz 問題とメモ化:

« Haskell で「順列」と「組み合わせ」 | トップページ | Project Euler : Problem 15 ~ 組み合わせ »

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

最近のトラックバック

無料ブログはココログ