Int64를 사용하는 haskell에서의 메모리 사용

Question

마지막 요소를 찾는 것이 문제입니다. 그것은 잘 작동 정수 유형. Int 형식으로 오버플로하지만 Int64를 시도 할 때 가비지 수집기가 작동하지 않는 것으로 보입니다.

module Main (main) where 
import Data.Int 
import System.Environment 

getNum :: Int -> Int64 

merge [] s2 = s2 
merge s1 [] = s1 
merge (s1:s1s) (s2:s2s) 
     | s1 < s2 = s1 : (merge s1s (s2:s2s)) 
     | s1 > s2 = s2 : (merge (s1:s1s) s2s) 
     | otherwise = s1 : (merge s1s s2s) 

scaleStreams scale = map $ (*) scale  

getNum n = s_3_56!!n 
    where s_3_56 = 1:(merge (scaleStreams 2 s_3_56) 
        (merge (scaleStreams 3 s_3_56) 
        (scaleStreams 5 s_3_56))) 

main = do 
    snum:_ <- getArgs 
    putStrLn $ show $ getNum (read snum) 

UPD. 수입 한 Data.Int. 그리고 100,000,000 개의 요소가 필요합니다. Int64를 사용하면 응답을 멈추거나 프로세서 사용을 중지합니다.

어쩌면 내가 ghc에 필요한 키를 필요로하므로 요소를 정리할 필요가 없습니다.

이 모두가 벤치마킹에 관한 것이므로 Integer라는 것이 더 명확해야합니다.

Answer 1

당신은 당신의 코드 라인

import Data.Int 

이 필요합니다.

Answer 2

숫자의 크기에서 Int 또는 Int64으로 오버플로 할 것입니다. 이것은 merge의 비교를 망칠 것입니다.

임의의 크기의 Integer을 사용하도록 변경하면 알고리즘이 대략 선형의 시간 및 공간 복잡성을 나타내는 것으로 나타납니다.

*Main> :set +s 
*Main> getNum 10 
15 
(0.05 secs, 15791376 bytes) 
*Main> getNum 100 
1600 
(0.04 secs, 15805848 bytes) 
*Main> getNum 1000 
51840000 
(0.05 secs, 16849584 bytes) 
*Main> getNum 10000 
288555831593533440 
(0.10 secs, 26238720 bytes) 
*Main> getNum 100000 
290237644800000000000000000000000000000 
(0.39 secs, 149698872 bytes) 
*Main> getNum 1000000 
519381797917090766274082018159448243742493816603938969600000000000000000000000000000 
(3.57 secs, 1440858488 bytes) 
*Main> getNum 10000000 
16244249195502759967226308067328000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 
(36.49 secs, 15318940632 bytes) 
*Main> getNum 100000000 
18140183964781799067475734441903054103752590419562119585784549199072397211943448001454797147212334274622985787416351057209969867746413217762757199393702760885526212114105820164278263467669252072928640885180135225440700708077201852574944496154785156250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 
(398.26 secs, 173628505536 bytes) 

내가 알 수있는 한 가비지 수집기가 올바르게 작동하는 것 같습니다. 100,000,000의 실행은 총 173GB의 메모리를 할당하지만, 한 번에 관찰 된 최고 피크는 약 900MB였습니다.