Я знаю, что ленивые последовательности оценивают только те элементы в той последовательности, которая запрашивается, как она это делает?
Я думаю, что ранее опубликованные ответы уже хорошо объясняют эту часть. Я только добавлю, что «форсирование» ленивой последовательности является неявным - без паренов! :-) - вызов функции; возможно, такой способ мышления прояснит некоторые вещи. Также обратите внимание, что форсирование ленивой последовательности включает в себя скрытую мутацию - форсируемый преобразователь должен создать значение, сохранить его в кеше (мутация!) И выбросить его исполняемый код, который больше не потребуется (снова мутация!) .
Я знаю, что ленивые последовательности оценивают только те элементы в той последовательности, которая запрашивается, как она это делает?
Что делает ленивые последовательности настолько эффективными, что они не потребляют много стека?
Какие ресурсы потребляют ленивые последовательности для того, что они делают?
Они не потребляют стек, потому что вместо этого потребляют кучу. Ленивая последовательность - это структура данных, живущая в куче, которая содержит небольшой бит исполняемого кода, который может быть вызван для создания дополнительной структуры данных, если / когда это потребуется.
Как так получилось, что вы можете заключить рекурсивные вызовы в ленивую последовательность и больше не получать переполнение стека для больших вычислений?
Во-первых, как упоминал dbyrne, вы вполне можете получить SO при работе с ленивыми последовательностями, если сами преобразователи должны выполнять код с очень глубоко вложенной структурой вызовов.
Однако в определенном смысле вы можете использовать ленивые последовательности вместо хвостовой рекурсии, и в той степени, в которой это работает для вас, вы можете сказать, что они помогают избежать SO. Фактически, что довольно важно, функции, производящие ленивые последовательности, не должны быть хвостовой рекурсивной; сохранение пространства стека с помощью ленивых производителей последовательностей возникает из вышеупомянутой передачи стека -> кучи, и любые попытки записать их в хвостовой рекурсивной манере только нарушат работу.
Ключевым моментом является то, что ленивая последовательность - это объект, который при первом создании не содержит никаких элементов (как это всегда бывает в строгой последовательности); когда функция возвращает ленивую последовательность, вызывающей стороне возвращается только этот «объект ленивой последовательности» до того, как произойдет какое-либо форсирование. Таким образом, кадр стека, использованный вызовом, который вернул ленивую последовательность, выталкивается до того, как произойдет какое-либо форсирование. Давайте посмотрим на пример функции производителя:
(defn foo-producer [] ; not tail recursive...
(lazy-seq
(cons :foo ; because it returns the value of the cons call...
(foo-producer)))) ; which wraps a non-tail self-call
Это работает, потому что lazy-seq
возвращает немедленно, поэтому (cons :foo (foo-producer))
также возвращается немедленно, и кадр стека, использованный внешним вызовом foo-producer
, немедленно выталкивается. Внутренний вызов foo-producer
скрыт в rest
части последовательности, которая является преобразователем; если / когда этот преобразователь принудительно используется, он на короткое время израсходует свой собственный фрейм в стеке, но затем немедленно вернется, как описано выше, и т. д.
Разделение на части (упомянутое dbyrne) очень незначительно меняет эту картину, потому что на каждом шаге создается большее количество элементов, но принцип остается тем же: каждый шаг использует некоторый стек, когда создаются соответствующие элементы ленивой последовательности, затем этот стек восстанавливается до повторной форсировки.
В каких сценариях ленивые последовательности неэффективны?
В каких сценариях ленивые последовательности наиболее эффективны?
Нет смысла лениться, если вам все равно нужно держать все сразу. Ленивая последовательность выделяет кучу на каждом шаге, если она не разбита на фрагменты, или на каждом фрагменте - один раз через каждые 32 шага - при разбиении на фрагменты; избегание этого может привести к увеличению производительности в некоторых ситуациях.
Однако ленивые последовательности обеспечивают конвейерный режим обработки данных:
(->> (lazy-seq-producer) ; possibly (->> (range)
(a-lazy-seq-transformer-function) ; (filter even?)
(another-transformer-function)) ; (map inc))
Выполнение этого строгого метода в любом случае приведет к выделению большого количества кучи, потому что вам придется хранить промежуточные результаты, чтобы передать их на следующий этап обработки. Более того, вам нужно держать все это под рукой, что на самом деле невозможно в случае (range)
- бесконечной последовательности! - а когда это возможно, это обычно неэффективно.
person
Michał Marczyk
schedule
14.07.2010