Памятная последовательность Коллатца
Я разместил тот же вопрос в CodeReview, но не смог получить ответ. поэтому я пытаюсь везти здесь, в SO.
Вот одна из моих программ, которые использовали мемоизацию и массив для улучшения производительности и использования памяти. Производительность кажется удовлетворительной, но использование памяти нелепо, и я не могу понять, в чем дело:
{-# LANGUAGE BangPatterns #-}
import Data.Functor
import Data.Array (Array)
import qualified Data.Array as Arr
import Control.DeepSeq
genColtzArr n = collatzArr
where collatzArr = Arr.array (1, n) $ take n $ map (\v -> (v, collatz v 0)) [1..]
collatz 1 !acc = 1 + acc
collatz !m !acc
| even m = go (m `div` 2) acc
| otherwise = go (3 * m + 1) acc
where go !l !acc
| l <= n = let !v = collatzArr Arr.! l in 1 + acc + v
| otherwise = collatz l $ 1 + acc
collatz здесь значит этот парень. Эта функция должна получить номер n, а затем вернуть индексирование массива от 1 до nи в котором каждая ячейка содержит длину ссылки от индекса до 1, применяя формулу Коллатца.
Но использование памяти этим методом очень высоко. Вот результат профилировщика (опция ghc -prof -fprof-auto -rtsopts, вариант времени выполнения +RTS -p, n == 500000):
total alloc = 730,636,136 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
genColtzArr.collatz Main 40.4 34.7
genColtzArr.collatz.go Main 25.5 14.4
COST CENTRE MODULE no. entries %time %alloc %time %alloc
genColtzArr Main 105 1 0.0 0.0 74.7 72.1
genColtzArr.collatzArr Main 106 1 8.0 20.8 74.7 72.1
genColtzArr.collatzArr.\ Main 107 500000 0.9 2.2 66.8 51.3
genColtzArr.collatz Main 109 1182582 40.4 34.7 65.9 49.1
genColtzArr.collatz.go Main 110 1182581 25.5 14.4 25.5 14.4
Обратите внимание, что -O2 не желаемый ответ. Я хочу выяснить, в чем проблема в этой программе и в целом, как я должен определить нехватку времени и памяти в коде на Haskell. В частности, я понятия не имею, почему этот код с хвостовой рекурсией и шаблоном взрыва может занимать так много памяти.
тот же код с -s производит это:
1,347,869,264 bytes allocated in the heap
595,901,528 bytes copied during GC
172,105,056 bytes maximum residency (7 sample(s))
897,704 bytes maximum slop
315 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 2408 colls, 0 par 0.412s 0.427s 0.0002s 0.0075s
Gen 1 7 colls, 0 par 0.440s 0.531s 0.0759s 0.1835s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.828s ( 0.816s elapsed)
GC time 0.852s ( 0.958s elapsed)
RP time 0.000s ( 0.000s elapsed)
PROF time 0.000s ( 0.000s elapsed)
EXIT time 0.004s ( 0.017s elapsed)
Total time 1.684s ( 1.791s elapsed)
%GC time 50.6% (53.5% elapsed)
Alloc rate 1,627,861,429 bytes per MUT second
Productivity 49.4% of total user, 46.4% of total elapsed
так что требуется 300 мег. это все еще слишком велико.
Update2полный код
{-# LANGUAGE BangPatterns #-}
import Data.Functor
import Data.Array (Array)
import qualified Data.Array as Arr
import Control.DeepSeq
genColtzArr n = collatzArr
where collatzArr = Arr.array (1, n) $ take n $ map (\v -> (v, collatz v 0)) [1..]
collatz 1 !acc = 1 + acc
collatz !m !acc
| even m = go (m `div` 2) acc
| otherwise = go (3 * m + 1) acc
where go !l !acc
| l <= n = let !v = collatzArr Arr.! l in 1 + acc + v
| otherwise = collatz l $ 1 + acc
genLongestArr n = Arr.array (1, n) llist
where colatz = genColtzArr n
llist = (1, 1):zipWith (\(n1, a1) l2 ->
let l1 = colatz Arr.! a1
in (n1 + 1, if l2 < l1 then a1 else n1 + 1))
llist (tail $ Arr.elems colatz)
main :: IO ()
main = getLine >> do
ns <- map read <$> lines <$> getContents
let m = maximum ns
let lar = genLongestArr m
let iter [] = return ()
iter (h:t) = (putStrLn $ show $ lar Arr.! h) >> iter t
iter ns
1 ответ
Как подсказывает другой ответ на CodeReview, для штучного массива из 500000 элементов вполне нормально использовать ~20 МБ памяти, однако это не только массив, но и много всего вместе:
Несмотря на то, что вы размещаете шаблоны взрыва везде, сама инициализация массива - это ленивый фолд:
-- from GHC.Arr
array (l,u) ies
= let n = safeRangeSize (l,u)
in unsafeArray' (l,u) n
[(safeIndex (l,u) n i, e) | (i, e) <- ies]
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
case newArray# n# arrEleBottom s1# of
(# s2#, marr# #) ->
foldr (fill marr#) (done l u n marr#) ies s2#)
Таким образом, если вы не оценили последний бит массива, он содержит ссылку на список, использованный при инициализации. Обычно список может быть собран GC на лету, когда вы оцениваете массив, но в вашем случае взаимные ссылки и собственные ссылки нарушают общий шаблон GC.
llistсамоссылка для создания каждого отдельного элемента, поэтому он не будет GC'd, пока вы не оценили последний элемент этого- он также содержит ссылку на
genColtzArrтакgenColtzArrне будет GC'd доllistполностью оценен - ты можешь подумать
collatzхвост рекурсивен, но это не так, он взаимно рекурсивен сcollatzArrтак что опять они оба не будут GC'd до полной оценки
Все вместе, ваша программа будет хранить три 500000-элементные структуры в виде списков в памяти и пиковый размер кучи ~80 МБ.
Решение
Очевидное решение состоит в том, чтобы привести каждый массив / список в нормальную форму, прежде чем он будет использован в другом, чтобы вы не хранили несколько копий одних и тех же данных в памяти.
genLongestArr :: Int -> Array Int Int
genLongestArr n =
let collatz = genColtzArr n
-- deepseq genColtzArr before mapping over it
-- this is equivalent to your recursive definition
in collatz `deepseq` (Arr.listArray (1,n) $ fmap fst $ scanl' (maxWith snd) (0, 0) $ Arr.assocs collatz)
maxWith :: Ord a => (b -> a) -> b -> b -> b
maxWith f b b' = case compare (f b) (f b') of
LT -> b'
_ -> b
И в main:
-- deepseq lar before mapping over it
-- this is equivalent to your iter loop
lar `deepseq` mapM_ (print . (lar Arr.!)) ns
С этим ничего не поделаешь genColtzArr он использует себя для запоминания, поэтому взаимная рекурсия необходима.
Теперь график кучи достигает пика в ~20 МБ, как и должно быть:
(Отказ от ответственности: все программы в этом ответе были скомпилированы с -O0 )