Реализация бесконечного списка с последовательностью для улучшения временной сложности в Haskell
Я не совсем понимаю, как именно работает seq и как реализовать функцию с помощью seq. Итак, в качестве упражнения, если я хочу реализовать функцию, которая генерирует список, начинающийся с числа a.
Например, я использую следующую функцию
countup n = n : countup (n+1)
И пытаюсь получить [1, 2, 3, 4...] (начиная с 1, просто увеличивая 1 и добавляя в список) как бесконечный ленивый список. Как мне это сделать?
ОБНОВЛЕНО:
Я пытаюсь заставить (взять k (счетчик 0)) использовать пространство O (1). Здесь функция взятия выглядит следующим образом:
take k (x:xl) =
if k==0
then x
else take (k-1) xl
Что касается изучения того, как работает seq, вот несколько полезных статей, которые вы, возможно, захотите прочитать: wiki.haskell.org/Seq stackoverflow.com/questions/11046590/…
@bradrn Я хочу минимизировать использование пространства с помощью seq. Поэтому я реализовал функцию, которая принимает число (индекс) и список (бесконечный список), который находит элемент индекса бесконечного списка. И я слышал, что я могу каким-то образом минимизировать пространственную сложность до O (1), если я использую seq для реализации списка?
В общем, в Haskell очень сложно рассуждать о пространственной сложности. Если ваша функция использует больше места, чем ожидалось, seq может помочь уменьшить его, но только если вы используете его правильно. С какой функцией вы пытаетесь его использовать?
@James: ленивые функции часто также могут сокращать пространство. Действительно, [1..n] занимает, если он остается невычисленным, только O (1) пространства, и только если вы «потребляете» список, он расширяется, но даже тогда не сам по себе до n элементов, поэтому ленивое вычисление часто может сэкономить память как хорошо.
@bradrn Я обновил код, чтобы свести к минимуму космическую сложность
Ответы 1
countup n = n : countup (n+1)
Каждый элемент списка создается как преобразователь previousElement + 1. Итак, если вы take 1000000-й или какой-то другой элемент, это будет очень большой преобразователь (...(n + 1)... + 1), содержащий ~ 1000000 приостановок. Несмотря на то, что :-ячейки могут быть GC'ированы, как только они будут созданы (поэтому обход самого корешка списка занимает O(1) места), сами элементы дублируют структуру списка и поэтому take k (countup n) по-прежнему занимают O(k) место.
Нам бы хотелось, чтобы при оценке ячеек : также оценивались элементы. Мы можем сделать это с
countup n = seq n $ n : countup (n + 1)
Теперь, при оценке seq n $ n : countup (n + 1), seq вызовет оценку как n, так и n : countup (n + 1). Вычисление последнего ничего не делает (оно уже вычислено), а вычисление первого выполняет любое thunked добавление, так что + 1s никогда не накапливаются. С этим определением take k (countup n) занимает O(1) место (или, на самом деле, O(log(n + k))).
Мы также можем записать улучшенную функцию как
countup !n = n : countup (n + 1)
Я попытался профилировать обе версии countup в качестве эксперимента, но не вижу разницы между ними ни в использовании памяти, ни в скорости. Вы уверены, что реализация с seq занимает меньше места, чем без?
Да, совершенно уверен. Скомпилируйте {-# LANGUAGE BangPatterns #-} module Main where import Prelude hiding (take); countUp !x = x : countUp (x + 1); take 0 (x : _) = x; take n (_ : xs) = take (n - 1) xs; main = print =<< (flip take (countUp 0) <$> readLn) с ghc -O. Затем запустите его с помощью ./Main +RTS -s. Дайте входные данные 1000, 1000000, 10000000: вывод (для меня) показывает использование кучи 2 МБ. Теперь удалите ! и перекомпилируйте. Передача 1000 по-прежнему использует ~ 2 МБ. Прохождение 1000000 занимает ~67 МБ, а 10000000 ~670 МБ. Ой! Не знаю, что вы сделали, но обратите внимание, что «профилирование» может дать неправильные результаты и не является необходимым.
Еще один способ написать это: (!:) :: a -> [a] -> [a]; a !: as = a `seq` a : as, затем countup n = n !: countup (n + 1).
Хорошо @HTNW, я попробую и посмотрю, сработает ли это. (Хм… может быть, наша разница в результатах была из-за того, что мы использовали разные параметры GHC? Я скомпилировал с -prof, а не -O, чтобы я мог создать профиль кучи.)
Спасибо! Я получил первую версию countup countup как countup n = n seq n : countup (n + 1), но я не был уверен. И спасибо за дополнительную информацию о том, как проверить использование кучи :) мило. @HTNW.
@HTNW Нет, я не могу повторить ваши результаты: я получаю 0,2 МБ за 1000, 80 МБ за 1000000, 800 МБ за 10000000. (См. pastebin.com/DBNiQMZK для вывода.)
@bradrn Вы смотрите не на тот номер. «Общее количество выделений» не является мерой использования памяти; это мера работы. Он подсчитывает каждый выделенный объект, но не отсчитывает освобождение. Максимальное фактическое использование памяти в данный момент времени — это «общая используемая память», которая, как вы видите, не меняется (показывает 0, ха!). т.е. да, улучшенный countup строит и прожигает много-много объектов, но эти объекты разделены во времени; они не занимают 800 МБ фактической памяти (в этом и есть смысл: поведение O(1) связано с тем, что «пропущенные» ячейки GC сразу после создания).
@bradrn если я прохожу 1 000 000 000, я получаю ~ 80 ГБ «Общих выделений» ... у картофеля, на котором я его запускаю, 4 ГБ ОЗУ. Если вы попробуете нестрогий вариант, он на самом деле попытается израсходовать все эти куски и куски памяти... Забавно, но кажется, что общее количество выделений примерно в два раза превышает максимальное использование памяти в этом случае, что, я думаю, может соответствовать на наличие одного сохраненного объекта (преобразователь n + 1) на два объекта (ячейка : и преобразователь).
@HTNW Спасибо за исправление! Очевидно, я понятия не имел, как читать этот вывод… это действительно поможет в следующий раз, когда мне нужно будет выяснить, как программа использует кучу.
Для этого не нужно seq. Особенно, если вы хотите, чтобы ваш список был ленивым! Просто сделай countup n = [n..].