У меня есть простой пример игрушек, который, похоже, не согласен с сборщиком мусора о том, какие структуры данных могут быть восстановлены (иначе утечка памяти). Я не пытаюсь придумать более эффективные с точки зрения памяти версии этого алгоритма (здесь есть хорошая коллекция лучших алгоритмов: Haskell Wiki - Prime numbers, а скорее объяснение, почему сборщик мусора не идентифицирует старые, вне области видимости и неиспользуемые части списка, чтобы вернуть эту памятьHaskell сборщик мусора
код здесь:.
import Data.List (foldl')
erat' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat' (c,b) ((x,y):xs)
| c < x = (x,y) : erat' (c,b) xs
| c == x = (x+y,y) : erat' (c,True) xs
| c > x = (x+y,y) : erat' (c,b) xs
erat' (c,b) []
| b = []
| otherwise = [(c,c)]
erat :: [Integer] -> [(Integer,Integer)]
erat = foldl' (\a c -> erat' (c,False) a) []
primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]
по сути, вызов простых чисел с положительным целым числом будет возвращать список всех простых чисел до и включая этот номер списка пар простых чисел. и их кратная водяная метка передается в erat 'вместе с парой, включающей кандидата и логическое значение (False for prime и True для non-prime). Каждый нерекурсивный вызов эпохе t 'передаст новый список, и я ожидаю, что вывод будет содержать, в лучшем случае, определенные общие ячейки с самого начала списка до момента первого изменения.
Как только измененные ячейки в списке, переданные в erat, выходят из области видимости, память должна быть отмечена как подлежащая восстановлению, но, как вы можете видеть, когда вы пытаетесь вызвать простые числа с достаточно большим числом (1 000 000, для пример), использование памяти может быстро увеличиться до десятков гигабайт.
Теперь возникает вопрос: почему это происходит? Должен ли сборщик мусора генерации обнаруживать разыменованные ячейки списка, чтобы вернуть их? И не должно быть достаточно легко обнаружить, что у них нет ссылок, потому что:
a) Ничто не может иметь ссылки на структуры данных, более старые, чем они сами; b) не может быть более новых ссылок, потому что эти ячейки/фрагменты больше не являются частью ссылочной структуры данных, так как она выходит из области видимости?
Конечно, измененная структура данных позаботится об этом, но я чувствую, что прибегая к изменчивости в таком случае, это снижает некоторые теоретические принципы для Haskell на полу.
Благодаря людям, которые прокомментировали (в частности, Carl), я немного модифицировал алгоритм, чтобы добавить строгость (и оптимизацию начала пересечения квадрата нового штриха, поскольку более низкие кратные будут пересекаться также кратными младшими числами) ,
Это новая версия:
потреблениеimport Data.List (foldl')
erat' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat' (c,b) ((x,y):xs)
| c < x = x `seq` (x,y) : erat' (c,b) xs
| c == x = x `seq` (x+y,y) : erat' (c,True) xs
| c > x = x `seq` (x+y,y) : erat' (c,b) xs
erat' (c,b) []
| b = []
| otherwise = [(c*c,c)] -- lower multiples would be covered by multiples of lower primes
erat :: [Integer] -> [(Integer,Integer)]
erat = foldl' (\a c -> erat' (c,False) a) []
primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]
память, кажется, все еще быть весьма значительным. Существуют ли какие-либо другие изменения в этом алгоритме, которые могли бы помочь уменьшить общее использование памяти?
Поскольку Уилл отметил, что я не предоставил полную статистику, эти цифры для запуска обновленной версии простых чисел, перечисленных чуть выше, с 100000 в качестве параметра:
И после применения изменений, которые будут предложены, использование памяти теперь значительно сократилось.Смотрите, например, на пробеге простых чисел для 100000 раз:
И наконец, это окончательный код после того, как предложенные изменения были включены:
import Data.List (foldl')
erat'' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat'' (c,b) ((x,y):xs)
| c < x = (x, y) : if x==y*y then (if b then xs
else xs++[(c*c,c)])
else erat'' (c,b) xs
| c == x = (x+y,y) : if x==y*y then xs
else erat'' (c,True) xs
| c > x = (x+y,y) : erat'' (c,b) xs
erat'' (c,True) [] = []
erat'' (c,False) [] = [(c*c,c)]
primes'' :: Integer -> [Integer]
primes'' n = map snd $ foldl' (\a c -> (if null a then 0 else
case last a of (x,y) -> y) `seq` erat'' (c,False) a) [] [2..n]
И, наконец, бежать за 1000000 иметь чувство производительности в этой новой версии:
Ваш анализ был бы правильным, если бы Haskell был строгим языком, но это не так. – Carl
Я попытался изменить строгость, используя seq и deepseq, с аналогичными результатами. Я не думаю, что у нестричности есть игра здесь, но я могу ошибаться. Не могли бы вы уточнить? – fgv
Это кажется очень плохим использованием для 'foldl'' на первый взгляд. Вы попробовали 'foldr'? –