공간이 부족한 Haskell 스크립트

StackOverflow https://stackoverflow.com/questions/736495

  •  09-09-2019
  •  | 
  •  

문제

나는 Project Euler를 사용하여 Haskell을 가르치고 있으며 Haskell이 내 코드를 어떻게 실행하는지에 대해 추론하는 데 어려움을 겪고 있습니다. 두 번째 문제는 모든 피보나치 숫자의 합을 최대 4 백만으로 계산하는 것입니다. 내 스크립트는 다음과 같습니다.

fibs :: [Integer]
fibs =  1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]

evens  :: Integer -> Integer -> Integer
evens x sum | (even x)   = x + sum
            | otherwise  = sum

main = do
  print (foldr evens 0 (take 4000000 fibs))

Hugs는 "가비지 컬렉션이 충분한 공간을 되 찾는 데 실패합니다"라는 오류를 제공합니다. foldr.

이 문제를 해결하려면 어떻게해야합니까? 나는 Accumulators를 사용한 Tail Recursive (생각) 버전을 작성하려고했지만 그것을 작동시킬 수 없었습니다.

도움이 되었습니까?

해결책

많은 관찰 / 힌트 :

  • 그만큼 x + sumS에서 S는 끝까지 평가되지 않습니다.
  • 최대 4,000,000의 FIB가 아닌 처음 4,000,000 개의 FIB를 복용하고 있습니다.
  • 더 쉬운 방법이 있습니다

댓글에 대한 응답으로 편집

프로젝트 오일러 문제의 재미이기 때문에 더 쉬운 방법을 말하지 않을 것입니다. 그러나 나는 당신에게 많은 질문을 할 것입니다.

  • 당신은 얼마나 많은 FIB를 연속으로 가질 수 있습니까?
  • 균일 한 FIB없이 얼마나 오래 갈 수 있습니까?
  • 모든 짝수 FIB와 모든 이상한 FIB (손 으로이 작업)를 요약하면 합에 대해 무엇을 주목하십니까?

다른 팁

첫째, 포옹을 사용해서는 안됩니다. 그것은 가르치는 목적으로 만 장난감입니다.

그러나 GHC는 Haskell을위한 빠른 멀티 코어 준비 최적화 컴파일러입니다. 여기에 가져 가십시오. 특히 엄격한 분석을 수행하고 기본 코드로 컴파일합니다.

코드에서 눈에 띄는 가장 중요한 것은 매우 큰 목록에서 Foldr를 사용하는 것입니다. 아마도 당신은 꼬리 재귀 루프를 원할 것입니다. 그렇게 :

import Data.List

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

evens x sum | even x    = x + sum
            | otherwise = sum

-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))

이 모든 것 외에도, 처음 4m조차도 FIB는 상당한 양의 공간을 사용하므로 시간이 걸립니다.

여기에 있습니다 처음 400k의 합계는 심지어 FIB입니다, 시간을 절약하기 위해 (21s). :-)

당신은 문제를 잘못 이해했습니다. 그만큼 실제 문제 Fibonacci 숫자 자체가 4 백만을 초과하지 않도록 모든 Fibonacci 번호를 모두 요약하기를 원합니다 (이는 처음 33 개의 Fibonacci 번호 일뿐입니다).

당신은 4 백만의 요소를 평가하고 있습니다 fibs. 그 숫자는 기하 급수적으로 증가합니다. 백만 번째 Fibonacci 번호를 나타내는 데 얼마나 많은 바이트가 필요한지 모르겠습니다. 1 천명의 피보나치 번호는 211 자리 숫자를 가지고 있으므로 숫자를 잡기 위해 22 개의 32 비트 단어를 가져갈 것입니다. gmp 부과합니다. 그리고 이것들은 기하 급수적으로 자랍니다.

운동 : 4 백만 개의 피보나치 수를 보유하는 데 필요한 메모리의 양을 계산하십시오.

Prelude 기능, 필터 및 합계를 살펴보십시오.

(<40) [0 ..
필터 $ $ take while (<40) [0 ..

함께 모으기 :

ans = sum $ 필터 짝수 $ take while (<4* 10^6) fibs

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top