3

私は Haskell が初めてで、オイラー プロジェクトの問題をいじっています。問題 3 に対する私の解決策は遅すぎます。最初に私はこれを試しました：

-- Problem 3
-- The prime factors of 13195 are 5, 7, 13 and 29.
-- What is the largest prime factor of the number 600851475143 ?

problem3 = max [ x | x <- [1..n], (mod n x) == 0, n /= x]
    where n = 600851475143

x次に、最大のものだけでなくすべてを返すように変更しました。

problem3 = [ x | x <- [1..n], (mod n x) == 0, n /= x]
        where n = 600851475143

30 分後、リストはまだ処理されており、出力は次のようになります。

[1,71,839,1471,6857,59569,104441,486847,1234169,5753023,10086647,87625999,408464633,716151937

なぜそんなに遅いのですか？私はひどく間違ったことをしていますか、それともこの種のタスクでは正常ですか?

4

5 に答える 5

10

あなたのソリューションでは、約 6,000 億通りの数字が考えられます。delnan が指摘したように、すべての数のチェックを高速化しても大きな違いはありません。候補の数を制限する必要があります。

あなたの解決策も正しくないようです。59569 = 71 * 839ではない？質問は素因数のみを求めます。71とがリストにあることに注意して839ください。正しいことをしているのです。実際、すべての要因を見つけようとしています。

続行する前に要素を分割するだけで、最も劇的な効果が得られると思います.

euler3 = go 2 600851475143
  where
    go cand num
      | cand == num           = [num]
      | cand `isFactorOf` num = cand : go cand       (num `div` cand)
      | otherwise             =        go (cand + 1) num

isFactorOf a b = b `mod` a == 0

これは明らかな最適化のように思えるかもしれませんが、 if bothaとでb割り切れるcとがthenaで割り切れるという事実に依存しています。bac/b

もっとやりたい場合は、一般的な「平方根までのみチェックする」トリックがここに記載されています。この問題にも同じトリックを適用できますが、残念ながら、この例ではパフォーマンスの向上は見られません。

euler3 = go 2 600851475143
  where
    go cand num
      | cand*cand > num       = [num]
      | cand `isFactorOf` num = cand : go cand       (num `div` cand)
      | otherwise             =        go (cand + 1) num

isFactorOf a b = b `mod` a == 0

ここで、候補が残りの数 ( ) の平方根よりも大きい場合、それは素数である必要があり、したがって元の数 ( ) の素因数であることがnumわかります。num600851475143

素数のみを考慮してさらに多くの候補を削除することは可能ですが、素数を生成する適切なパフォーマンスの方法を作成する必要があるため、これは少し高度です。その方法については、このページを参照してください。

于 2013-07-30T12:13:24.687 に答える
3

それはたくさんの仕事をしています！（それはまたあなたに間違った答えを与えるでしょうが、それは別の問題です！）

最初に問題について少し考えることで、速度を上げることができる非常に簡単な方法がいくつかあります。

  • すべての数値1..nに関数を適用し、それらのそれぞれをチェックして、そうでないことを確認しnます。代わりに、すべての数値1..n-1を調べて、さまざまなチェックをスキップすることができnます (小さいですが)。
  • 答えは奇数なので、 の代わりに を1..(n-1)/2チェックすることで、偶数をすばやく除外できます。2xx
  • 考えてみると、すべての要因はペアで発生するため、実際には、各ステップで数字のペアから検索して1..sqrt(n)(または1..sqrt(n)/2偶数を無視する場合)、出力することができます。

この関数のパフォーマンスとは関係ありませんが、ここで実装したものは数値のすべての因数を見つけますが、必要なのは最大の素因数だけであることに注意してください。したがって、素数性について各除数をテストする必要があります (これも遅くなります)、または 2 つを 1 つのステップで実装できます。あなたはおそらく「ふるい」を見たいと思うでしょう。最も単純なものはエラトステネスのふるいであり、それらをどのように実装できるかです。

于 2013-07-30T11:30:57.583 に答える
0

TL;DR : あなたが行っていた最適化されていない 2 つのことは、平方根で停止しないことと、見つかった最小の要素を分割しないことです。

これは、 HaskellElephant による回答に示されている (2 番目の) 因数分解コードの少しの派生です。私たちはあなたのコードから始めます:

f1 n = [ x | x <- [2..n], rem n x == 0]
n3 = 600851475143

Prelude> f1 n3
[71,839,1471,6857,59569,104441,486847Interrupted.

したがって、妥当な時間内に終了せず、生成される数の一部は素数ではありません... しかし、リスト内包表記に素数チェックを追加する代わりに、71が素数であることに注意してください。によって生成される最初の数値f1 nはの最小の約数でありn、素数です。そうでない場合は、その最小の約数を最初に見つけます。これは矛盾です。

したがって、それを分割して、新たに簡約された数の素因数を検索し続けることができます。

f2 n = tail $ iterate (\(_,m)-> (\f->(f, quot m f)) . head $ f1 m) (1,n) 

Prelude> f2 n3
[(71,8462696833),(839,10086647),(1471,6857),(6857,1),(*** Exception: Prelude.hea
d: empty list

（エラー、理由f1 1 == []）。終わったね！（6857が答えです、ここでは...）。まとめましょう:

takeUntil p xs = foldr (\x r -> if p x then [x] else x:r) [] xs
pfactors1 n = map fst . takeUntil ((==1).snd) . f2 $ n   -- prime factors of n

新たに開発されたソリューションを試してみると、

Prelude> map pfactors1 [n3..]
[[71,839,1471,6857],[2,2,2,3,3,1259Interrupted.

小さな約数のない数では、突然、新しい非効率の壁にぶつかります。しかし、もしn = a*bそしてなら1 < a <= b、その最小の除数を見つけるために、数の平方根a*a <= a*b == nまでテストするだけで十分です。

f12 n = [ x | x <- takeWhile ((<= n).(^2)) [2..n], rem n x == 0] ++ [n]
f22 n = tail $ iterate (\(_,m)-> (\f->(f, quot m f)) . head $ f12 m) (1,n) 
pfactors2 n = map fst . takeUntil ((==1).snd) . f22 $ n

30 分で終了できなかったものが、1 秒未満で終了するようになりました (典型的な高性能ボックスで):

Prelude> f12 n3
[71,839,1471,6857,59569,104441,486847,600851475143]

上記のすべての除数sqrt n3はまったく必要ありませんでした。素数を処理できるようにn、最後の除数として無条件に自分自身を追加します。f12

Prelude> f12 (n3+6)
[600851475149]

以来n3 / sqrt n3 = sqrt n3 ~= 775146、最初の の試みは終了するまでに約 1 週間かかるf1 n3はずでした。平方根で停止するという、この最適化がいかに重要かということです。

Prelude> f22 n3
[(71,8462696833),(839,10086647),(1471,6857),(6857,1),(1,1),(1,1),(1,1),(1,1),(1,
1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1)Interrupted

どうやら「Prelude.head: empty list」エラーを、終了しないが生産的な動作と交換したようです。

最後に、f222 つの部分に分割し、それぞれを他の関数に融合して、やや単純化したコードにします。また、常に2から最小の除数を検索するように、 を最初からやり直すことはもうありません。f12

-- smallest factor of n, starting from d. directly jump from sqrt n to n.
smf (d,n) = head $ [ (x, quot n x) | x <- takeWhile ((<=n).(^2)) [d..]
                                   , rem n x == 0] ++ [(n,1)]

pfactors n = map fst . takeUntil ((==1).snd) . tail . iterate smf $ (2,n)

これは、高階関数による保護された (共) 再帰を表し、機能的には上記のコードと同等です。以下はスムーズに実行されるようになり、ボーナスとして双子の素数のペアを見つけることさえできます。 iterate

Prelude Saga> map pfactors [n3..]
[[71,839,1471,6857],[2,2,2,3,3,1259,6628403],[5,120170295029],[2,13,37,227,27514]
79]、[3,7,7,11,163,2279657]、[2,2,41,3663728507]、[600851475149]、[ 2,3,5,5,19,31,680]
0809]、[600851475151]、[2,2,2,2,37553217197]、[3,3,3,211,105468049]、[2,7,11161,3845
351]、[5,67,881,2035853]、[2,2,3中断されました。
于 2013-07-30T23:28:13.423 に答える
0

これが Euler Project #3 の私のソリューションです。私の Macbook Air ではわずか 1.22 秒しかかかりません。

まず、与えられた数の因数をすべて見つける必要があります。しかし、偶数を素数にすることはできません (2 を除く)。したがって、オイラー プロジェクト #3 を解くには、すべてではなく、奇妙な要素だけが必要です。

    getOddFactors num = [ x | x <- [3,5..num], num `rem` x == 0 ]

しかし、この機能を最適化することができます。sqrt numより大きいnumの因数を見つけようとする場合は、 sqrt numより小さい別の因数が必要です。これらの可能な因数は既に見つかっています。したがって、可能性のある要因のリストをsqrt numで制限できます。

    getOddFactors num = [ x | x <- [3, 5..(floor.sqrt.fromIntegral) num], 
                          num `rem` x == 0 ]

次に、 numの奇数要素のどれが素数であるかを知りたいです。

    isPrime number = [ x | x <- [3..(floor.sqrt.fromIntegral) number], 
                       number `rem` x == 0] == []

次に、関数isPrimeを使用してnumの奇数因子をフィルタリングして、 numのすべての素因子を見つけることができます。しかし、Haskell の遅延性を使用してソリューションを最適化するには、関数フィルター isPrimeをnum の奇数要素の反転リストに適用します。関数が素数である最初の値を見つけるとすぐに、Haskell は計算を停止し、解を返します。

    largestPrimeFactor = head . filter isPrime . reverse . getOddDivisors

したがって、解決策は次のとおりです。

    ghci> largestPrimeFactor 600851475143
    6857
    (1.22 secs, 110646064 bytes)
于 2014-07-08T13:33:37.300 に答える