4

私は実世界の Haskell (私は第 4 章にいます) に取り組んでおり、本から少し外れた練習をするために、n 番目の素数を計算する次のプログラムを作成しました。

import System.Environment

isPrime primes test = loop primes test
    where
        loop (p:primes) test
            | test `mod` p == 0 = False
            | p * p > test = True
            | otherwise = loop primes test


primes = [2, 3] ++ loop [2, 3] 5
    where 
        loop primes test
            | isPrime primes test = test:(loop primes' test')
            | otherwise = test' `seq` (loop primes test')
            where
               test' = test + 2
               primes' = primes ++ [test]

main :: IO()
main = do
    args <- getArgs
    print(last  (take (read (head args) :: Int) primes))

明らかに、素数のリストを保存しているので、これは一定の空間ソリューションではありません。問題は、非常に大きな素数を取得しようとすると./primes 1000000、エラーが発生することです。

    Stack space overflow: current size 8388608 bytes.
    Use `+RTS -Ksize -RTS' to increase

テール再帰が正しく行われたことはかなり確信しています。http://www.haskell.org/haskellwiki/Stack_overflowを読んで、ここのさまざまな応答から、それは遅延評価の副産物であると信じるようになり、サンクはオーバーフローするまで蓄積されますが、これまでのところ修正に失敗していますそれ。いろいろなところに使っseqて評価を強制してみましたが、効果がありませんでした。私は正しい軌道に乗っていますか？私が得ていないものは他にありますか？

4

3 に答える 3

6

コメントで述べたように、非常に長いリスト (あなたの行primes' = primes ++ [test]) の最後に単一の要素リストを追加してリストを作成するべきではありません。無限リスト を定義して、primes遅延評価に任せたほうがよいでしょう。以下のコードのようなもの：

primes = [2, 3] ++ loop 5
    where.
        loop test
            | isPrime primes test = test:(loop test')
            | otherwise = test' `seq` (loop test')
            where
                test' = test + 2

isPrime明らかに、関数をパラメーター化する必要はありませんがprimes、それは単なるニッチです。また、すべての数値が正であることがわかっている場合は、rem代わりにmod- を使用する必要があります。これにより、マシンのパフォーマンスが 30% 向上します (100 万番目の素数を見つける場合)。

于 2012-08-13T00:19:02.897 に答える
2

まず、ここには末尾再帰はありませんが、保護された再帰、別名末尾再帰 modulo consがあります。

スタックオーバーフローが発生する理由は、他の人がコメントしたように、サンクの山積みです。しかしここで？提案された原因の 1 つは、(++). 最適ではありませんが、 を使用すると(++)必ずしもサンク パイルアップとスタック オーバーフローが発生するわけではありません。たとえば、

take 2 $ filter (isPrime primes) [15485860..]

すぐに生成され、スタックオーバーフローも発生[15485863,15485867]しません。しかし、それは を使用するコードと同じ(++)ですよね?

問題は、呼び出すリストが2 つprimesあることです。1 つ (トップ レベル) は無限であり、保護された (テールではない) 再帰によって再帰的に生成されます。もう 1 つの ( への引数loop) は有限リストであり、新しく見つかった各素数をその末尾に追加することによって作成され、テストに使用されます。

ただし、テストに使用する場合は、強制的に最後まで実行することはありません。それが起こった場合、SOの問題はありません。試験番号の に強制的に通すだけsqrtです。そのため、(++)サンクはその時点を過ぎて山積みになります。

がisPrime primes 15485863呼び出されると、トップレベルを強制的に までprimes上げ3935ます。これは 547 個の素数です。内部の testing-primes リストも 547 個の素数で構成され、最初の 19 個だけが強制されます。

しかし、 を呼び出すとprimes !! 1000000、重複する内部リストの 1,000,000 個の素数のうち、547 個だけが強制されます。残りはすべてサンクです。

リストの最後に新しい素数を追加するのはtesting-primes、それらの正方形が候補の中にある場合のみである場合、testing-primesリストは常に完全に、またはほぼ最後まで強制的に実行され、SO の原因となるサンク パイルアップは発生しません。また、強制(++)リストの最後にwith を追加することは、次のアクセスがそのリストの最後に強制され、サンクが残らない場合はそれほど悪くありません。(それでもリストはコピーされます。)

もちろん、primesThomas M. DuBuisson が回答で示しているように、トップレベルのリストを直接使用できます。

しかし、内部リストには用途があります。正しく実装され、候補の中に正方形が見られる場合にのみ新しい素数を追加すると、最適化してコンパイルすると、プログラムをO(sqrt(n))spaceで実行できる場合があります。

于 2012-08-13T11:10:48.547 に答える
0

おそらく次の2つの質問を確認する必要があります。

  1. runhaskellでスタックサイズを増やすにはどうすればよいですか？
  2. スタックスペースのオーバーフローを回避する方法は？
于 2012-08-12T22:28:49.870 に答える