6

私はオイラー問題78を解こうとしています。これは基本的に、分配関数p（n）が1000000で割り切れる最初の数を要求します。

私は五角数に基づくオイラーの再帰式を使用します（ここでpentsは適切な符号とともに計算されます）。これが私のコードです：

ps = 1 : map p [1..] where
  p n = sum $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

pents = zip (map (\n -> (3*n-1)*n `div` 2) $ [1..] >>= (\x -> [x,-x]))
            (cycle [1,1,-1,-1])

正しい結果が得られるようにps見えますが、遅すぎます。計算を高速化する方法はありますか、それとも完全に異なるアプローチが必要ですか？

4

4 に答える 4

4

xs !! n線形の複雑さを持っています。むしろ、対数または常時アクセスのデータ構造を使用してみてください。

編集：これは私が8月に似たようなものをコピーすることによって思いついた簡単な実装です：

psOpt x = psArr x
  where psCall 0 = 1
        psCall n = sum $ map getP $ takeWhile ((<= n).fst) pents where
          getP (pent,sign) = sign * (psArr (n-pent))
        psArr n = if n > ncache then psCall n else psCache ! n
        psCache = listArray (0,ncache) $ map psCall [0..ncache]

ghciでは、リストバージョンに比べて目覚ましいスピードアップは見られません。運が悪い！

編集： 確かに、-O2Chris Kuklewiczが提案したように、このソリューションはあなたのソリューションよりも8倍高速ですn=5000。10 ^ 6を法として合計を行うというHammarの洞察と組み合わせると、十分に高速なソリューションが得られます（私のマシンで約10秒で正しい答えを見つけてください）。

import Data.List (find)
import Data.Array 

ps = 1 : map p [1..] where
  p n = sum $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

summod li = foldl (\a b -> (a + b) `mod` 10^6) 0 li

ps' = 1 : map p [1..] where
  p n = summod $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

ncache = 1000000

psCall 0 = 1
psCall n = summod $ map getP $ takeWhile ((<= n).fst) pents
  where getP (pent,sign) = sign * (psArr (n-pent))
psArr n = if n > ncache then psCall n else psCache ! n
psCache = listArray (0,ncache) $ map psCall [0..ncache]

pents = zip (map (\n -> ((3*n-1)*n `div` 2) `mod` 10^6) $ [1..] >>= (\x -> [x,-x]))
            (cycle [1,1,-1,-1])

（psCacheの抽象化を破ったので、psArr代わりに使用する必要がありpsOptます。これにより、別の呼び出しpsArrで同じメモ化された配列が再利用されます。これは、作成するときに役立ちます...まあ、完全なソリューションfind ((== 0) . ...)を公開しない方がよいと思いました。 ）。

追加のアドバイスをありがとうございました。

于 2011-04-25T16:25:42.037 に答える
2

さて、1つの観察は、あなたが興味があるのは、だけmap (`mod` 10^6) psなので、膨大な数の計算をしなくても済むかもしれないということです。

于 2011-04-25T16:57:37.647 に答える
1

私はそのオイラー問題を実行していませんが、通常、オイラー問題では、計算を高速化するための巧妙なトリックがあります。

私がこれを見たとき：

sum $ map getP $ takeWhile ((<=n).fst) pents

sum . map getPの要素を計算するたびに呼び出すよりも賢い方法があるはずだと思わずにはいられませんps。

getP今私はそれを見て...すべての要素に対して乗算（の内部）を実行してから合計するよりも、最初に合計を実行してから乗算する方が速いのではないでしょうか？

通常、私はより深く調べて、機能するコードを提供します。しかし、それはオイラーの問題です（それを台無しにしたくないでしょう！）ので、これらのいくつかの考えでここで停止します。

于 2011-04-25T18:42:52.460 に答える
1

あなたの質問に触発されて、私はあなたのアプローチを使ってハスケルでオイラー78を解きました。だから私はあなたにいくつかのパフォーマンスのヒントを与えることができます。

キャッシュされたペントのリストは、そのままでよいはずです。

（pn）の検索を制限するために、いくつかの大きな数maxNを選択します。

計画では、（Array Int64 Integer）を使用して、下限0と上限maxNで（pn）の結果を記憶します。これには、配列を「p」で定義し、「p」を配列で定義する必要があります。これらは相互に再帰的に定義されます。

（pn）を（pArray n）に再定義して、配列Aの「p」への再帰呼び出しを検索します。

新しいpArrayとData.Array.IArray.listArrayを使用して、配列Aを作成します。

間違いなく'ghc-O2'でコンパイルします。ここでは13秒で実行されます。

于 2011-04-26T08:53:16.483 に答える