Почему ленивая оценка полезна?
Я долго задавался вопросом, почему ленивая оценка полезна. Мне еще предстоит, чтобы кто-нибудь объяснил мне так, чтобы это имело смысл; в основном это сводится к тому, чтобы "доверять мне".
Примечание: я не имею в виду памятки.
22 ответа
Главным образом потому, что это может быть более эффективным - значения не нужно вычислять, если они не будут использоваться. Например, я могу передать три значения в функцию, но в зависимости от последовательности условных выражений фактически может использоваться только подмножество. В таком языке, как C, все три значения будут вычислены в любом случае; но в Haskell вычисляются только необходимые значения.
Это также учитывает классные вещи как бесконечные списки. У меня не может быть бесконечного списка на языке, подобном C, но в Haskell это не проблема. Бесконечные списки используются довольно часто в определенных областях математики, поэтому может быть полезно иметь возможность манипулировать ими.
Я нахожу ленивую оценку полезной для многих вещей.
Во-первых, все существующие ленивые языки чисты, потому что очень сложно рассуждать о побочных эффектах в ленивом языке.
Чистые языки позволяют рассуждать об определениях функций с использованием эквациональных рассуждений.
foo x = x + 3
К сожалению, в не ленивых настройках больше операторов не возвращаются, чем в ленивых, поэтому это менее полезно в таких языках, как ML. Но на ленивом языке вы можете смело рассуждать о равенстве.
Во-вторых, многие вещи, такие как "ограничение значения" в ML, не нужны в ленивых языках, таких как Haskell. Это приводит к значительному снижению синтаксиса. В языках, подобных ML, необходимо использовать такие ключевые слова, как var или fun. В Хаскеле эти вещи сводятся к одному понятию.
В-третьих, лень позволяет вам писать очень функциональный код, который можно понять по частям. В Haskell принято писать тело функции, например:
foo x y = if condition1
then some (complicated set of combinators) (involving bigscaryexpression)
else if condition2
then bigscaryexpression
else Nothing
where some x y = ...
bigscaryexpression = ...
condition1 = ...
condition2 = ...
Это позволяет вам работать "сверху вниз" через понимание тела функции. ML-подобные языки вынуждают вас использовать let, которая оценивается строго. Следовательно, вы не осмеливаетесь "поднять" предложение let до основной части функции, потому что, если это дорого (или имеет побочные эффекты), вы не хотите, чтобы оно всегда оценивалось. Haskell может явно "вытолкнуть" детали к предложению where, поскольку он знает, что содержимое этого предложения будет оцениваться только по мере необходимости.
На практике мы склонны использовать охрану и разрушать ее, чтобы:
foo x y
| condition1 = some (complicated set of combinators) (involving bigscaryexpression)
| condition2 = bigscaryexpression
| otherwise = Nothing
where some x y = ...
bigscaryexpression = ...
condition1 = ...
condition2 = ...
В-четвертых, лень иногда предлагает гораздо более элегантное выражение определенных алгоритмов. Ленивая "быстрая сортировка" в Haskell является однострочной и имеет то преимущество, что если вы смотрите только на первые несколько предметов, вы платите только расходы, пропорциональные стоимости выбора только этих предметов. Ничто не мешает вам делать это строго, но вам, вероятно, придется каждый раз перекодировать алгоритм для достижения той же асимптотической производительности.
В-пятых, лень позволяет вам определять новые управляющие структуры в языке. Вы не можете написать новую конструкцию типа "если.. тогда.. еще.." на строгом языке. Если вы попытаетесь определить функцию как:
if' True x y = x
if' False x y = y
на строгом языке обе ветви будут оцениваться независимо от значения условия. Это ухудшается, когда вы рассматриваете петли. Все строгие решения требуют, чтобы язык предоставил вам какую-то цитату или явную лямбда-конструкцию.
Наконец, в том же духе, некоторые из лучших механизмов борьбы с побочными эффектами в системе типов, таких как монады, действительно могут быть эффективно выражены только в ленивых условиях. Это можно увидеть, сравнив сложность рабочих процессов F# с Haskell Monads. (Вы можете определить монаду на строгом языке, но, к сожалению, вы часто будете нарушать закон монады или два из-за отсутствия лени и рабочих процессов, для сравнения заберите тонну строгого багажа.)
Полезным примером ленивой оценки является использование quickSort:
quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)
Если мы теперь хотим найти минимум списка, мы можем определить
minimum ls = head (quickSort ls)
Который сначала сортирует список, а затем занимает первый элемент списка. Однако из-за ленивых вычислений вычисляется только голова. Например, если мы возьмем минимум из списка [2, 1, 3,] quickSort сначала отфильтрует все элементы, которые меньше двух. Затем он выполняет быструю сортировку по этому (возвращая одноэлементный список [1]), чего уже достаточно. Из-за ленивых вычислений остальное никогда не сортируется, что экономит много вычислительного времени.
Это, конечно, очень простой пример, но лень работает для очень больших программ одинаково.
Однако у этого есть обратная сторона: становится все труднее прогнозировать скорость выполнения и использование памяти вашей программой. Это не значит, что ленивые программы работают медленнее или занимают больше памяти, но это полезно знать.
Есть разница между обычной оценкой заказа и ленивой оценкой (как в Haskell).
square x = x * x
Оценивая следующее выражение...
square (square (square 2))
... с нетерпением
> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256
... с обычной оценкой заказа:
> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256
... с ленивой оценкой:
> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256
Это потому, что ленивая оценка смотрит на синтаксическое дерево и выполняет преобразования дерева...
square (square (square 2))
||
\/
*
/ \
\ /
square (square 2)
||
\/
*
/ \
\ /
*
/ \
\ /
square 2
||
\/
*
/ \
\ /
*
/ \
\ /
*
/ \
\ /
2
... тогда как нормальная оценка порядка делает только текстовые расширения.
Вот почему мы, используя ленивую оценку, становимся более мощными (оценка завершается чаще, чем другие стратегии), а производительность эквивалентна активной оценке (по крайней мере, в О-записи).
Ленивая оценка связана с процессором так же, как сборка мусора, связанная с оперативной памятью. GC позволяет вам делать вид, что у вас неограниченный объем памяти и, таким образом, запрашивать столько объектов в памяти, сколько вам нужно. Runtime автоматически восстановит непригодные для использования объекты. LE позволяет вам делать вид, что у вас неограниченные вычислительные ресурсы - вы можете делать столько вычислений, сколько вам нужно. Время выполнения просто не будет выполнять ненужные (для данного случая) вычисления.
В чем практическое преимущество этих "притворных" моделей? Это освобождает разработчика (в некоторой степени) от управления ресурсами и удаляет некоторый шаблонный код из ваших источников. Но более важно то, что вы можете эффективно использовать свое решение в более широком контексте.
Представьте, что у вас есть список чисел S и числа N. Вам нужно найти ближайший к номеру N номер M из списка S. У вас может быть два контекста: один N и некоторый список L из Ns (например, для каждого N в L Вы ищите ближайший M в S). Если вы используете ленивую оценку, вы можете отсортировать S и применить бинарный поиск, чтобы найти ближайший M к N. Для хорошей ленивой сортировки потребуется O(размер (S)) шагов для одиночных N и O(ln(размер (S))*(размер (S) + размер (L))) шаги для равномерно распределенного L. Если у вас нет ленивых вычислений для достижения оптимальной эффективности, вам нужно реализовать алгоритм для каждого контекста.
Если вы верите Саймону Пейтону Джонсу, ленивая оценка сама по себе не важна, а лишь как "рубашка для волос", которая заставляла дизайнеров поддерживать язык в чистоте. Я сочувствую этой точке зрения.
Ричард Берд, Джон Хьюз и, в меньшей степени, Ральф Хинце способны делать удивительные вещи с ленивой оценкой. Чтение их работ поможет вам оценить их. Хорошей отправной точкой являются великолепный решатель судоку от Bird и статья Хьюза " Почему функциональное программирование имеет значение".
Рассмотрим программу крестики-нолики. Это имеет четыре функции:
- Функция генерации ходов, которая берет текущую доску и генерирует список новых досок, каждое из которых применено одним ходом.
- Затем есть функция "дерево ходов", которая применяет функцию генерации ходов для получения всех возможных позиций доски, которые могут следовать из этого.
- Существует минимаксная функция, которая обходит дерево (или, возможно, только его часть), чтобы найти лучший следующий ход.
- Существует функция оценки доски, которая определяет, выиграл ли один из игроков.
Это создает хорошее четкое разделение проблем. В частности, функция генерации ходов и функции оценки доски - единственные, которые должны понимать правила игры: дерево ходов и минимаксные функции могут использоваться повторно.
Теперь давайте попробуем реализовать шахматы вместо крестики-нолики. На "нетерпеливом" (то есть обычном) языке это не сработает, потому что дерево перемещения не помещается в памяти. Таким образом, теперь функции оценки доски и генерации ходов необходимо смешивать с деревом ходов и минимаксной логикой, потому что минимаксная логика должна использоваться для определения того, какие ходы генерировать. Наша хорошая чистая модульная структура исчезает.
Однако в ленивом языке элементы дерева ходов генерируются только в ответ на требования минимаксной функции: не нужно генерировать все дерево ходов, прежде чем мы выпустим минимакс на верхнем элементе. Таким образом, наша чистая модульная структура все еще работает в реальной игре.
Вот еще два момента, которые, я не думаю, были затронуты в ходе обсуждения.
Лень - это механизм синхронизации в параллельной среде. Это легкий и простой способ создания ссылки на некоторые вычисления и обмена результатами среди множества потоков. Если несколько потоков пытаются получить доступ к неоцененному значению, только один из них выполнит его, а другие будут блокироваться соответствующим образом, получая значение, как только оно станет доступным.
Лень имеет основополагающее значение для амортизации структур данных в чистом виде. Это подробно описано Окасаки в " Чисто функциональных структурах данных", но основная идея заключается в том, что ленивая оценка - это контролируемая форма мутации, критически важная для эффективного внедрения определенных типов структур данных. В то время как мы часто говорим о лени, заставляющей нас носить чистую прическу, применяется и другой способ: они представляют собой пару синергетических языковых особенностей.
Когда вы включаете компьютер и Windows воздерживается от открытия каждой отдельной директории на жестком диске в Windows Explorer и воздерживается от запуска каждой отдельной программы, установленной на вашем компьютере, до тех пор, пока вы не укажете, что необходим определенный каталог или определенная программа, что это "ленивая" оценка.
"Ленивая" оценка - это выполнение операций, когда и когда они необходимы. Это полезно, когда это особенность языка программирования или библиотеки, потому что, как правило, сложнее реализовать ленивую оценку самостоятельно, чем просто предварительно рассчитать все заранее.
Это может повысить эффективность. Это выглядит очевидным, но на самом деле это не самое главное. (Обратите также внимание, что лень тоже может убивать эффективность - этот факт не сразу очевиден. Однако, сохраняя множество временных результатов, а не вычисляя их сразу, вы можете использовать огромное количество оперативной памяти.)
Это позволяет вам определять конструкции управления потоком в обычном пользовательском коде, а не жестко кодировать его в языке. (Например, Java имеет
forпетли; Haskell имеетforфункция. Java имеет обработку исключений; У Haskell есть различные типы монад исключений. C# имеетgoto; У Haskell есть монада продолжения...)Это позволяет вам отделить алгоритм генерации данных от алгоритма принятия решения, сколько данных генерировать. Вы можете написать одну функцию, которая генерирует условно-бесконечный список результатов, и другую функцию, которая обрабатывает столько же этого списка, сколько решает. Более того, у вас может быть пять функций генератора и пять пользовательских функций, и вы можете эффективно создавать любую комбинацию - вместо того, чтобы вручную кодировать 5 x 5 = 25 функций, которые объединяют оба действия одновременно. (!) Мы все знаем, что разделение - это хорошо.
Это более или менее заставляет вас создавать чистый функциональный язык. Всегда соблазнительно использовать короткие пути, но на ленивом языке малейшая нечистота делает ваш код дико непредсказуемым, что сильно препятствует использованию быстрых клавиш.
Учти это:
if (conditionOne && conditionTwo) {
doSomething();
}
Метод doSomething() будет выполняться только в том случае, если conditionOne имеет значение true, а conditionTwo имеет значение true. В случае, когда conditionOne имеет значение false, зачем вам нужно вычислять результат условия два? В этом случае оценка условия два будет пустой тратой времени, особенно если ваше состояние является результатом какого-то метода.
Это один из примеров ленивого интереса к оценке...
Одним из огромных преимуществ лени является возможность писать неизменяемые структуры данных с разумными амортизированными границами. Простой пример - неизменный стек (с использованием 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.
Этот фрагмент показывает разницу между ленивой и не ленивой оценкой. Конечно, эту функцию Фибоначчи можно было бы оптимизировать и использовать ленивую оценку вместо рекурсии, но это испортило бы пример.
Давайте предположим, что мы МОЖЕМ использовать 20 первых чисел для чего-то, без не ленивой оценки все 20 чисел должны быть сгенерированы заранее, но при ленивой оценке они будут сгенерированы только по мере необходимости. Таким образом, вы будете платить только расчетную цену, когда это необходимо.
Образец вывода
Не ленивое поколение: 0.023373 Ленивое поколение: 0.000009 Не ленивый выход: 0.000921 Ленивый вывод: 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)
Ленивая оценка наиболее полезна для структур данных. Вы можете определить массив или вектор индуктивно, указав только определенные точки в структуре и выразив все остальные через весь массив. Это позволяет создавать структуры данных очень кратко и с высокой производительностью во время выполнения.
Чтобы увидеть это в действии, вы можете взглянуть на мою библиотеку нейронных сетей под названием инстинкт. Это делает интенсивное использование ленивых оценок для элегантности и высокой производительности. Например я полностью избавился от традиционно обязательного расчета активации. Простое ленивое выражение делает все для меня.
Это используется, например, в функции активации, а также в алгоритме обучения обратного распространения (я могу опубликовать только две ссылки, так что вам нужно поискать learnPat функция в AI.Instinct.Train.Delta модуль сам). Традиционно оба требуют гораздо более сложных итерационных алгоритмов.
Другие люди уже привели все веские причины, но я думаю, что полезное упражнение, чтобы помочь понять, почему лень имеет значение, - попытаться написать функцию с фиксированной запятой на строгом языке.
В Haskell функция с фиксированной точкой очень проста:
fix f = f (fix f)
это расширяется до
f (f (f ....
но поскольку Haskell ленив, эта бесконечная цепочка вычислений не проблема; оценка выполняется "снаружи внутрь", и все прекрасно работает:
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 аргумент по требованию:
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)
Ленивая оценка - это эквациональное рассуждение бедняка (в идеале можно ожидать, что свойства кода будут выведены из свойств типов и задействованных операций).
Пример, где это работает довольно хорошо: sum . take 10 $ [1..10000000000], Которые мы не против того, чтобы их сводили к сумме из 10 чисел вместо одного простого и простого численного расчета. Без ленивой оценки, конечно, это создаст гигантский список в памяти только для использования его первых 10 элементов. Это, безусловно, будет очень медленно и может вызвать ошибку нехватки памяти.
Пример, где это не так здорово, как хотелось бы: sum . take 1000000 . drop 500 $ cycle [1..20], Который на самом деле будет суммировать 1 000 000 чисел, даже если в цикле, а не в списке; все же это должно быть уменьшено до одного прямого числового вычисления, с несколькими условными выражениями и несколькими формулами. Что было бы намного лучше, чем суммировать 1 000 000 чисел. Даже если в цикле, а не в списке (т.е. после оптимизации обезлесения).
Другое дело, что это позволяет кодировать в стиле хвостовой рекурсии по модулю минусов, и это просто работает.
ср связанный ответ.
Я не знаю, как вы в настоящее время думаете о вещах, но я считаю полезным думать о ленивой оценке как о проблеме с библиотекой, а не как о языковой функции.
Я имею в виду, что на строгих языках я могу реализовать ленивую оценку, создав несколько структур данных, а на ленивых языках (по крайней мере, на Haskell) я могу попросить строгости, когда захочу. Поэтому выбор языка не делает ваши программы ленивыми или не ленивыми, а просто влияет на то, что вы получаете по умолчанию.
Как только вы подумали об этом, подумайте обо всех местах, где вы пишете структуру данных, которую вы позже сможете использовать для генерации данных (не рассматривая ее слишком много раньше), и вы увидите множество применений для ленивых. оценка.
Самая полезная эксплуатация ленивых вычислений, которую я использовал, была функция, которая вызывала ряд подфункций в определенном порядке. Если любая из этих подфункций завершилась неудачно (вернула 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;
}
Как только вы начнете использовать его, вы увидите возможности использовать его все чаще и чаще.
Без ленивой оценки вам не разрешат написать что-то вроде этого:
if( obj != null && obj.Value == correctValue )
{
// do smth
}
Среди прочего, ленивые языки допускают многомерные бесконечные структуры данных.
Хотя схема, Python и т. Д. Допускают одномерные бесконечные структуры данных с потоками, вы можете перемещаться только по одному измерению.
Лень полезна для той же дополнительной проблемы, но стоит отметить соединение сопрограмм, упомянутое в этой ссылке.
Если под "ленивой оценкой" вы подразумеваете как в combound booleans, как в
if (ConditionA && ConditionB) ...
тогда ответ прост: чем меньше процессорных циклов потребляет программа, тем быстрее она будет работать... и если часть инструкций по обработке не окажет влияния на результат программы, то это не нужно (и, следовательно, трата времени) выполнять их в любом случае...
если otoh, вы имеете в виду то, что я знал как "ленивые инициализаторы", как в:
class Employee
{
private int supervisorId;
private Employee supervisor;
public Employee(int employeeId)
{
// code to call database and fetch employee record, and
// populate all private data fields, EXCEPT supervisor
}
public Employee Supervisor
{
get
{
return supervisor?? (supervisor = new Employee(supervisorId));
}
}
}
Эта методика позволяет клиентскому коду, использующему класс, избежать необходимости вызывать базу данных для записи данных супервизора, за исключением случаев, когда клиенту, использующему объект Employee, требуется доступ к данным супервизора... это ускоряет процесс создания экземпляра Employee, и все же, когда вам нужен супервизор, первый вызов свойства супервизора вызовет вызов базы данных, и данные будут извлечены и доступны...
Выдержка из функций высшего порядка
Давайте найдем наибольшее число меньше 100 000, которое делится на 3829. Для этого мы просто отфильтруем набор возможностей, в которых, как мы знаем, лежит решение.
largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
where p x = x `mod` 3829 == 0
Сначала мы составим список всех чисел ниже 100 000 по убыванию. Затем мы фильтруем его по нашему предикату, и поскольку числа отсортированы по убыванию, наибольшее число, которое удовлетворяет нашему предикату, является первым элементом отфильтрованного списка. Нам даже не нужно было использовать конечный список для нашего начального набора. Это снова лень в действии. Поскольку мы используем только заголовок отфильтрованного списка, не имеет значения, является ли отфильтрованный список конечным или бесконечным. Оценка останавливается, когда найдено первое адекватное решение.