6

私は現在、ProjetEulerで問題14の解決策を最適化しようとしています。私はHaskellを本当に楽しんでおり、この種の問題に非常に適していると思います。これが私が試した3つの異なる解決策です。

import Data.List (unfoldr, maximumBy)
import Data.Maybe (fromJust, isNothing)
import Data.Ord (comparing)
import Control.Parallel

next :: Integer -> Maybe (Integer)
next 1 = Nothing
next n
  | even n = Just (div n 2)
  | odd n  = Just (3 * n + 1)

get_sequence :: Integer -> [Integer]
get_sequence n = n : unfoldr (pack . next) n
  where pack n = if isNothing n then Nothing else Just (fromJust n, fromJust n)

get_sequence_length :: Integer -> Integer
get_sequence_length n
    | isNothing (next n) = 1
    | otherwise = 1 + (get_sequence_length $ fromJust (next n))

-- 8 seconds
main1 = print $ maximumBy (comparing length) $ map get_sequence [1..1000000]

-- 5 seconds
main2 = print $ maximum $ map (\n -> (get_sequence_length n, n)) [1..1000000]

-- Never finishes
main3 = print solution
  where
    s1 = maximumBy (comparing length) $ map get_sequence [1..500000]
    s2 = maximumBy (comparing length) $ map get_sequence [500001..10000000]
    solution = (s1 `par` s2) `pseq` max s1 s2

ここで、実際の問題を見ると、ほとんどの新しいシーケンスには以前に計算されたサブシーケンスが含まれるため、キャッシュの可能性がたくさんあります。

比較のために、私もCでバージョンを作成しました。キャッシュありの
実行時間：0.03秒
キャッシュなしの実行時間：0.3秒

それは正気じゃない！確かに、キャッシュは時間を10分の1に短縮しましたが、キャッシュしなくても、私のHaskellコードよりも少なくとも17倍高速です。

私のコードの何が問題になっていますか？Haskellが関数呼び出しをキャッシュしないのはなぜですか？関数は純粋なキャッシングであるため、キャッシングは些細なことではなく、使用可能なメモリの問題だけですか？

私の3番目の並列バージョンの問題は何ですか？どうして終わらないの？

Haskellを言語として、コンパイラーはいくつかのコード（フォールド、マップなど）を自動的に並列化しますか、それともControl.Parallelを使用して常に明示的に実行する必要がありますか？

編集：私はこの同様の質問に出くわしました。彼らは、彼の機能は末尾再帰ではないと述べました。get_sequence_lengthの末尾再帰は再帰的ですか？そうでない場合、どうすればそうすることができますか？

Edit2：
ダニエルへ：
返信ありがとうございます。本当に素晴らしいです。私はあなたの改善をいじってみました、そして私はいくつかの本当に悪い落とし穴を見つけました。

Windws 7（64ビット）、8GBRAMを搭載した3.3GHZクアッドコアでテストを実行しています。
私が最初にしたことは、あなたが言うように、すべてのIntegerをIntに置き換えることでしたが、メインのいずれかを実行するたびに、+ RTS kSize -RTSが途方もなく高く設定されていても、メモリが不足しました。

最終的に私はこれを見つけました（stackoverflowは素晴らしいです...）、これはWindows上のすべてのHaskellプログラムが32ビットとして実行されているため、Intがオーバーフローして無限の再帰を引き起こしていたことを意味します...

代わりに、Linux仮想マシン（64ビットghcを使用）でテストを実行したところ、同様の結果が得られました。

4

2 に答える 2

20

さて、上から始めましょう。最初に重要なことは、コンパイルと実行に使用している正確なコマンドラインを提供することです。私の答えとして、すべてのプログラムのタイミングにこの行を使用します。

ghc -O2 -threaded -rtsopts test && time ./test +RTS -N

次は、タイミングはマシンごとに大きく異なるため、私のマシンとプログラムのベースラインタイミングをいくつか示します。uname -aこれが私のコンピューターの出力です。

Linux sorghum 3.4.4-2-ARCH #1 SMP PREEMPT Sun Jun 24 18:59:47 CEST 2012 x86_64 Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz GenuineIntel GNU/Linux

ハイライトは、クアッドコア、2.4GHz、64ビットです。

使用中main1：30.42s user 2.61s system 149% cpu 22.025 total
使用中main2：21.42s user 1.18s system 129% cpu 17.416 total
使用中main3：22.71s user 2.02s system 220% cpu 11.237 total

実際、私main3は2つの方法で変更しました。1つは、の範囲の終わりからゼロの1つを削除すること、もう1つは、s2に変更max s1 s2することmaximumBy (comparing length) [s1, s2]です。前者は誤って正しい答えを計算するだけだからです。=）

次に、シリアル速度に焦点を当てます。（直接の質問の1つに答える：いいえ、GHCはプログラムを自動的に並列化またはメモ化しません。どちらもオーバーヘッドが非常に高く、その結果、いつ実行するかを決定するのが非常に困難です。この回答のシリアルソリューションでさえ100％を超えるCPU使用率を取得している理由はわかりません。おそらく、別のスレッドなどでガベージコレクションが発生しています。）main22つのシリアル実装の中で高速だったため、から始めます。少しブーストする最も安価な方法は、すべての型アノテーションをからに変更するIntegerことIntです。

使用Int:(11.17s user 0.50s system 129% cpu 8.986 total約2倍の速さ）

次のブーストは、内側のループでの割り当てを減らすこと（中間Maybe値を削除すること）から来ます。

import Data.List
import Data.Ord

get_sequence_length :: Int -> Int
get_sequence_length 1 = 1
get_sequence_length n
    | even n = 1 + get_sequence_length (n `div` 2)
    | odd  n = 1 + get_sequence_length (3 * n + 1)

lengths :: [(Int,Int)]
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000]

main = print (maximumBy (comparing fst) lengths)

これを使用する：4.84s user 0.03s system 101% cpu 4.777 total

even次のブーストは、およびよりも高速な操作を使用することから得られますdiv。

import Data.Bits
import Data.List
import Data.Ord

even' n = n .&. 1 == 0

get_sequence_length :: Int -> Int
get_sequence_length 1 = 1
get_sequence_length n = 1 + get_sequence_length next where
    next = if even' n then n `quot` 2 else 3 * n + 1

lengths :: [(Int,Int)]
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000]

main = print (maximumBy (comparing fst) lengths)

これを使用する：1.27s user 0.03s system 105% cpu 1.232 total

自宅でフォローしている人にとって、これは私たちが始めたものよりも約17倍速く、main2Cに切り替えることで競争力が向上します。

メモ化には、いくつかの選択肢があります。最も簡単なのは、 data-memocombinatorsのような既存のパッケージを使用して不変の配列を作成し、そこから読み取ることです。タイミングは、この配列に適切なサイズを選択することにかなり敏感です。この問題については、私50000はかなり良い上限であることがわかりました。

import Data.Bits
import Data.MemoCombinators
import Data.List
import Data.Ord

even' n = n .&. 1 == 0

pre_length :: (Int -> Int) -> (Int -> Int)
pre_length f 1 = 1
pre_length f n = 1 + f next where
    next = if even' n then n `quot` 2 else 3 * n + 1

get_sequence_length :: Int -> Int
get_sequence_length = arrayRange (1,50000) (pre_length get_sequence_length)

lengths :: [(Int,Int)]
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000]

main = print (maximumBy (comparing fst) lengths)

これとともに：0.53s user 0.10s system 149% cpu 0.421 total

すべての中で最も速いのは、メモ化ビットに可変のボックス化されていない配列を使用することです。慣用的ではありませんが、ベアメタル速度です。配列が答えを求めている最大のものとほぼ同じ大きさである限り、速度はこの配列のサイズにそれほど敏感ではありません。

import Control.Monad
import Control.Monad.ST
import Data.Array.Base
import Data.Array.ST
import Data.Bits
import Data.List
import Data.Ord

even' n = n .&. 1 == 0
next  n = if even' n then n `quot` 2 else 3 * n + 1

get_sequence_length :: STUArray s Int Int -> Int -> ST s Int
get_sequence_length arr n = do
    bounds@(lo,hi) <- getBounds arr
    if not (inRange bounds n) then (+1) `fmap` get_sequence_length arr (next n) else do
        let ix = n-lo
        v <- unsafeRead arr ix
        if v > 0 then return v else do
            v' <- get_sequence_length arr (next n)
            unsafeWrite arr ix (v'+1)
            return (v'+1)

maxLength :: (Int,Int)
maxLength = runST $ do
    arr <- newArray (1,1000000) 0
    writeArray arr 1 1
    loop arr 1 1 1000000
    where
    loop arr n len 1  = return (n,len)
    loop arr n len n' = do
        len' <- get_sequence_length arr n'
        if len' > len then loop arr n' len' (n'-1) else loop arr n len (n'-1)

main = print maxLength

これで:(0.16s user 0.02s system 138% cpu 0.130 totalメモ化されたCバージョンと競合します）

于 2012-08-15T02:43:09.227 に答える
0

GHCは、自動的に何も並列化することはありません。そして、あなたが推測するようget_sequence_lengthに、末尾再帰ではありません。ここを参照してください。そして、コンパイラーが（それがあなたのためにいくつかの素晴らしい最適化を行っていない限り）どのようにあなたが最後に到達するまでそれらすべての再帰的追加を評価できないかを考えてください。あなたは「サンクを積み上げる」のですが、これは通常は良いことではありません。

代わりに、再帰ヘルパー関数を呼び出してアキュムレータを渡すか、。で定義してみてくださいfoldr。

于 2012-08-15T01:08:57.513 に答える