Потребление памяти в haskell с использованием Int64

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

Из размера чисел ясно, что вы будете переполнены 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 выделяется 173 ГБ памяти, но самый высокий пик, который я наблюдал за один раз, составлял около 900 МБ.

Answer 2

Вам нужна строка

import Data.Int

в вашем коде.