Int64を使用したhaskellでのメモリ消費

Question

問題は最後の要素を見つけることです。それはよく動作しますInteger型。 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でした。