Как выполняются ленивые последовательности в Clojure?

Ответ 1

Сделайте это.

• Я знаю, что ленивые последовательности оценивают только элементы в запрошенной последовательности, как это делается?

Ленивые последовательности (отныне LS, потому что я LP, или Lazy Person) состоят из частей. Головка или часть (как, по сути, 32 элемента оцениваются за раз, как из Clojure 1.1, и я думаю, 1.2) последовательности, которая была оценена, за ней следует что-то, называемое thunk, который в основном представляет собой фрагмент информации (подумайте об этом как о остальной части вашей функции, которая создает последовательность, неоценимую), ожидая, что ее назовем. Когда он вызывается, thunk оценивает, как много просят об этом, и создается новый thunk, с необходимым контекстом (сколько уже было вызвано, поэтому он может возобновиться с того места, где он был раньше).

Итак, вы (take 10 (whole-numbers)) - предположим, что whole-numbers - ленивая последовательность целых чисел. Это означает, что вы заставляете оценивать thunks 10 раз (хотя внутри это может быть небольшая разница в зависимости от оптимизации.

• Что делает ленивые последовательности настолько эффективными, что они не потребляют много стека?

Это становится понятным после того, как вы прочтете предыдущий ответ (я надеюсь): если вы не вызываете что-то в частности, ничего не оценивается. Когда вы вызываете что-то, каждый элемент последовательности можно оценивать индивидуально, а затем отбрасывать.

Если последовательность не является ленивой, часто она держится на голове, которая потребляет кучу пространства. Если он ленив, он вычисляется, а затем отбрасывается, поскольку он не требуется для последующих вычислений.

• Как вы можете обернуть рекурсивные вызовы в ленивой последовательности и больше не получать стек над потоком для больших вычислений?

См. предыдущий ответ и рассмотрите: макрос lazy-seq (из документации) будет

will invoke the body only the first time seq
is called, and will cache the result and return it on all subsequent
seq calls.

Проверьте функцию filter для классного LS, который использует рекурсию:

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

• Какие ресурсы используют ленивые последовательности, чтобы делать то, что они делают?

Я не совсем уверен, что вы спрашиваете здесь. LSs требуют циклов памяти и процессора. Они просто не перестают бить стек и заполняют его результатами вычислений, необходимых для получения элементов последовательности.

• В каких сценариях ленивые последовательности неэффективны?

Когда вы используете небольшие seqs, которые быстро вычисляются и не будут использоваться много, что делает его LS неэффективным, поскольку для его создания требуется еще несколько символов.

При всей серьезности , если вы не пытаетесь сделать что-то чрезвычайно результативное, LSs - путь.

• В каких сценариях наиболее ленивые последовательности наиболее эффективны?

Когда вы имеете дело с seqs, которые огромны, и вы используете только их кусочки, то есть когда вы получаете максимальную выгоду от их использования.

В самом деле, почти всегда лучше использовать LSs по сравнению с не-LS, с точки зрения удобства, простоты понимания (как только вы их повесите), и рассуждения о вашем коде и скорости.

Ответ 2

Я знаю, что ленивые последовательности только оценивают элементы в запрошенной последовательности, как это делается?

Я думаю, что ранее опубликованные ответы уже хорошо отражают эту часть. Я только добавлю, что "форсирование" ленивой последовательности является неявным - без пар!:-) - вызов функции; возможно, этот способ думать об этом сделает некоторые вещи более ясными. Также обратите внимание, что принудительная ленивая последовательность включает в себя скрытую мутацию - принудительный вызов должен производить значение, хранить его в кеше (мутация!) И выкидывать его исполняемый код, который больше не понадобится (мутация снова!).

Я знаю, что ленивые последовательности только оценивают элементы в запрошенной последовательности, как это делается?

Что делает ленивые последовательности настолько эффективными, что они не потребляют много стека?

Какие ресурсы используют ленивые последовательности, чтобы делать то, что они делают?

Они не потребляют стек, потому что вместо этого они потребляют кучу. Ленивая последовательность - это структура данных, живущая в куче, которая содержит небольшой бит исполняемого кода, который можно вызвать для создания большей части структуры данных, если/когда это необходимо.

Как вы можете обернуть рекурсивные вызовы в ленивой последовательности и больше не получать стек за поток для больших вычислений?

Во-первых, как упоминалось dbyrne, вы можете очень хорошо получить SO при работе с ленивыми последовательностями, если сами thunks должны выполнить код с очень глубоко вложенной структурой вызова.

Однако в определенном смысле вы можете использовать ленивые seqs вместо рекурсии хвоста, и в той степени, в которой это работает для вас, вы можете сказать, что они помогают избежать SO. На самом деле, что немаловажно, функции, генерирующие ленивые последовательности, не должны быть хвостовыми рекурсивными; сохранение пространства стека с ленивыми производителями seq возникает из вышеупомянутого стека → передача кучи, и любые попытки записать их хвостовым рекурсивным способом будут только нарушать вещи.

Ключевым понятием является то, что ленивая последовательность - это объект, который при первом создании не содержит никаких элементов (как всегда выполняется строгая последовательность); когда функция возвращает ленивую последовательность, только этот "ленивый объект последовательности" возвращается вызывающему, прежде чем произойдет какое-либо форсирование. Таким образом, кадр стека, используемый для вызова, который возвращает ленивую последовательность, выскочит до того, как произойдет какое-либо форсирование. Давайте посмотрим на примерную функцию производителя:

(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 последовательности, которая является thunk; если/когда этот thunk принудительно, он ненадолго будет использовать свой собственный фрейм в стеке, но затем немедленно вернется, как описано выше и т.д.

Chunking (упомянутый dbyrne) очень мало меняет эту картину, потому что на каждом шаге получается большее количество элементов, но принцип остается тем же: каждый шаг использовал некоторый стек, когда соответствующие элементы ленивого seq, то этот стек будет восстановлен до того, как произойдет большее форсирование.

В каких сценариях ленивые последовательности неэффективны?

В каких сценариях используются ленивые последовательности?

Нет смысла лениться, если вам нужно все время держать все подряд. Ленивая последовательность делает распределение кучи на каждом шаге, когда не кланяется или на каждый кусок - один раз каждые 32 шага - при разделении; избегая того, что может привести к увеличению производительности в некоторых ситуациях.

Однако ленивые последовательности позволяют конвейерный режим обработки данных:

(->> (lazy-seq-producer)               ; possibly (->> (range)
     (a-lazy-seq-transformer-function) ;               (filter even?)
     (another-transformer-function))   ;               (map inc))

Выполнение этого в строгом режиме в любом случае выделило бы множество кучи, потому что вам нужно было бы сохранить промежуточные результаты, чтобы передать их на следующий этап обработки. Более того, вам нужно будет держать все это, что на самом деле невозможно в случае (range) - бесконечной последовательности! - и когда это возможно, оно обычно неэффективно.

Ответ 3

Первоначально, ленивые последовательности в Clojure оценивались по отдельности, поскольку они были необходимы. В целях повышения производительности в Clojure 1.1 были добавлены последовательности каналов. Вместо оценки по каждому элементу "куски" из 32 элементов оцениваются одновременно. Это уменьшает накладные расходы, которые несет ленивая оценка. Кроме того, он позволяет Clojure использовать базовые структуры данных. Например, PersistentVector реализуется как дерево из 32 массивов элементов. Это означает, что для доступа к элементу вы должны пройти дерево до тех пор, пока не будет найден соответствующий массив. С чередующимися последовательностями целые массивы захватываются одновременно. Это означает, что каждый из 32 элементов может быть извлечен до того, как дерево должно пройти повторное пересечение.

Обсуждалось предоставление способа принудительной оценки предметов в деталях в ситуациях, когда требуется полная лень. Тем не менее, я не думаю, что он был добавлен на язык.

Как вы можете обернуть рекурсивные вызовы в ленивой последовательности и больше не получать стек за поток для больших вычислений?

Есть ли у вас пример того, что вы имеете в виду? Если у вас есть рекурсивная привязка к lazy-seq, это может привести к переполнению стека.