소수를 계산할 때 스택 공간 오버플로

Question

저는 Real World 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을 사용하여 평가를 시도했지만 효과가 없습니다. 나는 올바른 길을 가고 있는가? 내가 얻지 못하는 다른 것이 있습니까?

Answer 1

내 의견에 말했듯이, 당신은 하나의 요소 목록을 추가하여 목록을 작성해서는 안 정말 긴 목록의 끝에 (당신의 줄 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 

은 분명히 당신도 primes하여 isPrime 기능을 매개 변수화 할 필요가 없습니다,하지만 그냥 니트입니다. 또한 모든 숫자가 양수인 경우 mod 대신 rem을 사용해야합니다. 이로 인해 내 컴퓨터에서 성능이 30 % 증가합니다 (백만 번째 소수를 찾을 때).

Answer 2

당신은 아마이 두 가지 질문을 확인해야합니다 :

1. How can I increase the stack size with runhaskell?
2. How to avoid stack space overflows?

Answer 3

먼저 여기에 꼬리 재귀가 없지만 은 재귀를 나타냅니다. tail recursion modulo cons입니다.

스택 오버플로가 발생하는 이유는 다른 사람이 주석을 달았을 때 쌓인 쌓기 때문입니다. 그러나 어디에서? 하나의 제안자는 (++)을 사용하는 것입니다. 최적이 아닌 동안 (++)을 사용하면 반드시 뚝뚝 끊김과 스택 오버플로가 발생할 필요는 없습니다. 예를 들어, 시간에 [15485863,15485867]을 생산한다

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

를 호출하고 스택 오버 플로우없이. 그러나 그것은 여전히 ​​ (++)을 사용하는 코드와 동일합니다.

문제는, 당신은 이 목록이 primes를 호출 할 수 있습니다. 하나 (최상위 레벨에서)는 무한하며, 보호 된 (꼬리가 아닌) 재귀를 통해 공동 재귀 적으로 생성됩니다. 또 하나의 인수 (loop에 대한 인수)는 새로 발견 된 소수를 끝에 추가하여 작성된 유한 목록으로, 테스트에 사용됩니다.

그러나 테스트 용으로 사용되면 강제 종료되지 않습니다. 그런 일이 일어난다면 SO 문제는 없을 것입니다. 테스트 번호가 인 sqrt까지만 적용됩니다.따라서 (++) 썽크가 그 지점을 지나쳐 버립니다.

isPrime primes 15485863을 호출하면 최상위 레벨 primes을(547 소수)까지 만듭니다. 내부 테스트 - 소수 목록은 547 개의 소수로 이루어져 있으며 그 중 첫 19 개만 강제됩니다.

그러나 primes !! 1000000을 호출하면 중복 내부 목록에서 1,000,000 개의 소수 중에서 547 개만 강제 적용됩니다. 나머지는 모두 썽크가 있습니다.

당신이 그들의 평방이 후보자들 사이에서 볼에만 testing-primes 목록의 끝에 새로운 소수를 추가 한 경우는 testing-primes 목록은 항상 완벽을 통해 강제로, 또는 거의 끝, 그리고 없을 것이다 것 그 원인이 된 쓰레기 더미. (++)을 의 끝에 추가하면 강제로 목록이 표시됩니다. 다음 액세스가 그 목록을 강제 종료하고 아무런 썽크도 남기지 않을 때 나쁘지 않습니다. (그래도 여전히 목록을 복사합니다.)

물론 대답은 Thomas M. DuBuisson이 답변 한대로 primes의 최상위 수준을 직접 사용할 수 있습니다.

그러나 내부 목록에는 용도가 있습니다. 올바르게 구현되면, 후보들 중에서 사각형이 보일 때만 새로운 소수를 추가하면 최적화를 통해 컴파일 할 때 프로그램이 O(sqrt(n)) 공간에서 실행될 수 있습니다.