计算素数时堆栈空间溢出 [英] Stack space overflow when computing primes

问题描述

我正在通过真实世界Haskell（我在第4章）努力工作，并且练习了一下我已经创建了以下程序来计算第n个素数的书。

  import System.Environment 
 
 isPrime primes test = loop primes test 
其中
 loop（p：primes）测试
 |测试`mod` p == 0 = False 
 | p * p> test = True 
 |否则=循环素数测试
 
 
素数= [2,3] ++循环[2,3] 5 
其中
循环素数测试
 | isPrime primes test = test：（loop primes'test'）
 |否则= test'`seq`（loop primes test'）
其中
 test'= test + 2 
 primes'=素数++ [测试] 
 
 main :: IO（）
 main = do 
 args<  -  getArgs 
 print（last（take（read（head args）:: Int）primes））
  

显然，由于我保存了素数列表，这不是一个恒定的空间解决方案。问题是当我尝试获得一个非常大的素数时，说 ./ primes 1000000 我收到错误：

 堆栈空间溢出：当前大小8388608字节。 
使用`+ RTS -Ksize -RTS'来增加
  

我很确定我得到了正确的尾递归;阅读 http://www.haskell.org/haskellwiki/Stack_overflow 以及这里的各种回复引导我相信它是懒惰评价的副产品，而且它正在不断膨胀直到它溢出，但到目前为止，我一直未能解决它。我试过在不同的地方使用 seq 来强制评估，但它没有产生任何效果。我在正确的轨道上吗？还有什么我没有得到？

解决方案

正如我在我的评论中所说的，你不应该建立一个列表通过在一个非常长的列表（你的行 primes'= primes ++ [test] ）结尾添加一个元素列表。最好定义无限列表， primes ，并让懒惰评估做它的事情。类似下面的代码：

  primes = [2,3] ++循环5 
其中。 
循环测试
 | isPrime primes test = test：（loop test'）
 |否则= test'`seq`（循环测试）
其中
 test'= test + 2 
  

显然你不需要通过 primes 来参数化 isPrime 函数，但这只是一个尼特。另外，当你知道所有的数字都是正数时，你应该使用 rem 而不是 mod - 这会导致30％我的机器性能提升（找到第一百万个素数时）。

I'm working my way through Real World Haskell (I'm in chapter 4) and to practice a bit off-book I've created the following program to calculate the nth prime.

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))

Obviously since I'm saving a list of primes this is not a constant space solution. The problem is when I try to get a very large prime say ./primes 1000000 I receive the error:

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

I'm fairly sure that I got the tail recursion right; reading http://www.haskell.org/haskellwiki/Stack_overflow and the various responses here lead me to believe that it's a byproduct of lazy evaluation, and thunks are building up until it overflows, but so far I've been unsuccessful in fixing it. I've tried using seq in various places to force evaluation, but it hasn't had an effect. Am I on the right track? Is there something else I'm not getting?

解决方案

As I said in my comment, you shouldn't be building a list by appending a single element list to the end of a really long list (your line primes' = primes ++ [test]). It is better to just define the infinite list, primes, and let lazy evaluation do it's thing. Something like the below code:

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

Obviously you don't need to parameterize the isPrime function by primes either, but that's just a nit. Also, when you know all the numbers are positive you should use rem instead of mod - this results in a 30% performance increase on my machine (when finding the millionth prime).

这篇关于计算素数时堆栈空间溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！