Почему ленивая оценка полезна?

Question

Мне давно интересно, почему ленивая оценка полезна. Мне еще предстоит, чтобы кто-нибудь объяснил мне так, чтобы это имело смысл; в основном это сводится к тому, чтобы «поверить мне».

Примечание: я не имею в виду запоминание.

Answer 1

Учтите это:

if (conditionOne && conditionTwo) {
  doSomething();
}

Метод doSomething () будет выполняться, только если для conditionOne установлено значение true , а для conditionTwo - значение true. В случае, когда conditionOne имеет значение false, зачем вам нужно вычислять результат условия два? В этом случае оценка conditionTwo будет пустой тратой времени, особенно если ваше состояние является результатом какого-либо метода.

Это один из примеров ленивого интереса к оценке ...

Answer 2

Одним из огромных преимуществ лени является возможность писать неизменяемые структуры данных с разумными амортизированными границами. Простой пример - неизменный стек (с использованием F #):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

Код разумный, но добавление двух стеков x и y занимает O (длину x) времени в лучшем, худшем и среднем случаях. Добавление двух стеков является монолитной операцией, она затрагивает все узлы в стеке x.

Мы можем переписать структуру данных как ленивый стек:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazy работает, приостанавливая оценку кода в его конструкторе. После оценки с использованием .Force() возвращаемое значение кэшируется и повторно используется в каждом последующем .Force().

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

Итак, наш ленивый список находится в постоянном состоянии восстановления, вы не оплачиваете стоимость восстановления этого списка, пока не пройдете все его элементы. Используя лень, этот список поддерживает O (1) согласование и добавление. Интересно, что, поскольку мы не оцениваем узлы до тех пор, пока к ним не будет получен доступ, вполне возможно построить список с потенциально бесконечными элементами.

Приведенная выше структура данных не требует пересчета узлов при каждом обходе, поэтому они заметно отличаются от ванильных IEnumerables в .NET.

Answer 3

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

Чтобы увидеть это в действии, вы можете взглянуть на мою библиотеку нейронных сетей, которая называется instinct . Это делает интенсивное использование ленивой оценки для элегантности и высокой производительности. Например я полностью избавился от традиционно обязательного расчета активации. Простое ленивое выражение делает все для меня.

Это используется, например, в функции активации , а также в алгоритме обучения обратного распространения (я могу опубликовать только две ссылки, поэтому вам нужно найти функцию learnPat в AI.Instinct.Train.Delta модуль самостоятельно). Традиционно оба требуют гораздо более сложных итерационных алгоритмов.

Answer 4

Другие люди уже привели все веские причины, но я думаю, что полезное упражнение, чтобы помочь понять, почему лень имеет значение, это попытаться написать фиксированную функцию на строгом языке.

В Haskell функция с фиксированной точкой очень проста:

fix f = f (fix f)

это расширяется до

f (f (f ....

но поскольку Хаскель ленив, эта бесконечная цепочка вычислений не представляет проблемы; оценка выполняется "снаружи внутрь", и все прекрасно работает:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

Важно отметить, что не fix быть ленивым, а f ленивым. Как только вы уже получили строгий f, вы можете либо поднять руки в воздух и сдаться, либо это расширить его и загромождать вещи. (Это очень похоже на то, что Ной говорил о том, что библиотека строгая / ленивая, а не язык).

Теперь представьте, что вы пишете ту же функцию в строгом Scala:

def fix[A](f: A => A): A = f(fix(f))

val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

Вы, конечно, получаете переполнение стека. Если вы хотите, чтобы он работал, вам нужно сделать аргумент f call-by-need:

def fix[A](f: (=>A) => A): A = f(fix(f))

def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)

val fact = fix(fact1)

Answer 5

Этот фрагмент показывает разницу между ленивой и не ленивой оценкой. Конечно, эту функцию Фибоначчи можно было бы оптимизировать и использовать ленивую оценку вместо рекурсии, но это испортило бы пример.

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

Пример вывода

Not lazy generation: 0.023373
Lazy generation: 0.000009
Not lazy output: 0.000921
Lazy output: 0.024205

import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)

Answer 6

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

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

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

Answer 7

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

Пример, где он работает довольно хорошо: sum . take 10 $ [1..10000000000]. Которые мы не против того, чтобы их сводили к сумме из 10 чисел вместо одного простого и простого численного расчета. Конечно, без ленивых вычислений это создаст гигантский список в памяти только для использования его первых 10 элементов. Это, безусловно, будет очень медленно и может вызвать ошибку нехватки памяти.

Пример, где это не так здорово, как хотелось бы: sum . take 1000000 . drop 500 $ cycle [1..20]. Который на самом деле будет суммировать 1 000 000 чисел, даже если в цикле, а не в списке; все же это должно быть сокращено до одного прямого числового вычисления, с несколькими условными выражениями и несколькими формулами. Что будет намного лучше, чем суммирование 1 000 000 чисел. Даже если в цикле, а не в списке (т.е. после оптимизации обезлесения).

---

Другое дело, что это позволяет кодировать в хвостовую рекурсию по модулю cons , и это просто работает .

ср. связанный ответ .

Answer 8

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

bool Function(void) {
  if (!SubFunction1())
    return false;
  if (!SubFunction2())
    return false;
  if (!SubFunction3())
    return false;

(etc)

  return true;
}

или, более элегантное решение:

bool Function(void) {
  if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
    return false;
  return true;
}

Как только вы начнете использовать его, вы увидите возможности использовать его все чаще и чаще.

Answer 9

Без ленивых вычислений вам не разрешат написать что-то вроде этого:

  if( obj != null  &&  obj.Value == correctValue )
  {
    // do smth
  }

Answer 10

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

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

Laziness полезно для той же самой проблемы , но стоит отметить соединение сопрограмм, упомянутое в этой ссылке.