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

https://stackoverflow.com/questions/265392

06-07-2019
|

Вопрос

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

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

Решение

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

Он также позволяет создавать такие интересные вещи, как бесконечные списки. У меня не может быть бесконечного списка на языке, подобном C, но в Haskell это не проблема. Бесконечные списки используются довольно часто в определенных областях математики, поэтому может быть полезно иметь возможность манипулировать ими.

Другие советы

Полезным примером ленивой оценки является использование quickSort :

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Если мы теперь хотим найти минимум списка, мы можем определить

minimum ls = head (quickSort ls)

Который сначала сортирует список, а затем берет первый элемент списка. Однако из-за ленивых вычислений вычисляется только голова. Например, если мы возьмем минимум из списка [2, 1, 3,] , то quickSort сначала отфильтрует все элементы, которые меньше двух. Затем он выполняет быструю сортировку по этому (возвращая одноэлементный список [1]), чего уже достаточно. Из-за ленивых вычислений остальное никогда не сортируется, что экономит много вычислительного времени.

Это, конечно, очень простой пример, но лень работает так же для очень больших программ.

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

Я нахожу ленивую оценку полезной для многих вещей.

Во-первых, все существующие ленивые языки чистые, потому что очень сложно рассуждать о побочных эффектах в ленивом языке.

Чистые языки позволяют рассуждать об определениях функций, используя эквациональные рассуждения.

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. (Вы можете определить монаду на строгом языке, но, к сожалению, вы часто будете нарушать закон монады или два из-за отсутствия лени и рабочих процессов, для сравнения заберите тонну строгого багажа.)

Существует разница между обычной оценкой заказа и ленивой оценкой (как в 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 позволяет вам делать вид, что у вас неограниченный объем памяти и, таким образом, запрашивать столько объектов в памяти, сколько вам нужно. Среда выполнения автоматически восстанавливает непригодные для использования объекты. LE позволяет вам делать вид, что у вас есть неограниченные вычислительные ресурсы - вы можете делать столько вычислений, сколько вам нужно. Среда выполнения просто не будет выполнять ненужные (для данного случая) вычисления.

Каково практическое преимущество этих «притворств»? модели? Это освобождает разработчика (в некоторой степени) от управления ресурсами и удаляет некоторый шаблонный код из ваших источников. Но более важно то, что вы можете эффективно использовать свое решение в более широком контексте.

Представьте, что у вас есть список чисел S и числа N. Вам нужно найти ближайший к номеру N номер M из списка S. У вас может быть два контекста: один N и несколько списков L из N (например, для каждого N в L вы смотрите ближайший M в S). Если вы используете ленивую оценку, вы можете отсортировать S и применить бинарный поиск, чтобы найти ближайший M к N. Для хорошей ленивой сортировки потребуется O (размер (S)) шагов для одиночных N и O (ln (размер (S)) * * (размер (S) + размер (L))) шаги для равномерно распределенных L. Если у вас нет ленивых вычислений для достижения оптимальной эффективности, вам нужно реализовать алгоритм для каждого контекста.

Если вы верите Саймону Пейтону Джонсу, ленивая оценка не важна как таковая , а лишь как «рубашка для волос», которая заставляла дизайнеров поддерживать язык в чистоте. Я сочувствую этой точке зрения.

Ричард Берд, Джон Хьюз и, в меньшей степени, Ральф Хинце способны делать удивительные вещи с ленивой оценкой. Чтение их работ поможет вам оценить их. Хорошей отправной точкой являются великолепная птица Судоку и программа Хьюза. Почему функциональное программирование имеет значение .

Рассмотрим программу "крестики-нолики".Это имеет четыре функции:

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

Это создает хорошее четкое разделение проблем.В частности, функция генерации ходов и функции оценки игрового поля - единственные, которые необходимы для понимания правил игры:функции дерева перемещения и минимакса полностью пригодны для повторного использования.

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

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

Вот еще два момента, которые, я не думаю, были затронуты в ходе обсуждения.

<Ол>

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

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

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

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

<Ол>

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

Он позволяет вам определять конструкции управления потоком в обычном коде пользовательского уровня, а не жестко кодировать его в языке. (Например, в Java есть циклы for ; в Haskell есть функция for . Java имеет обработку исключений; в Haskell есть различные типы монад исключений. C # имеет goto ; Haskell имеет монаду продолжения ...)

Позволяет отделить алгоритм для генерации данных от алгоритма для определения количества данных для генерации. Вы можете написать одну функцию, которая генерирует условно-бесконечный список результатов, и другую функцию, которая обрабатывает столько же этого списка, сколько решает. Более того, вы можете иметь пять функций генератора и пять пользовательских функций, и вы можете эффективно создавать любую комбинацию - вместо ручного кодирования 5 x 5 = 25 функций, которые объединяют оба действия одновременно. (!) Мы все знаем, что разделение - это хорошо.

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

Подумайте об этом:

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

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

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

Одним из огромных преимуществ лени является возможность писать неизменяемые структуры данных с разумными амортизированными границами. Простой пример - неизменный стек (с использованием 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.

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

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

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

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

Предположим, нам МОЖЕТ использовать 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)

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

В 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)

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

Я имею в виду, что на строгих языках я могу реализовать ленивую оценку, построив несколько структур данных, а на ленивых языках (по крайней мере, на 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 и т. д. допускают одномерные бесконечные структуры данных с потоками, вы можете перемещаться только по одному измерению.

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

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

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

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

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

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

Если по "ленивой оценке" ты имеешь в виду, как в 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, требуется доступ к данным супервизора ... это делает процесс создания экземпляра Сотрудник работает быстрее, и все же, когда вам нужен супервизор, первый вызов свойства супервизора вызовет вызов базы данных, и данные будут получены и доступны ...

Выдержка из функций высшего порядка

Давайте найдем наибольшее число меньше 100 000, которое делится на 3829. Для этого мы просто отфильтруем набор возможностей, в которых мы знаем решение лежит.

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0

Сначала мы составим список всех чисел, меньших 100 000, по убыванию. Затем мы фильтруем его по нашему предикату и потому, что числа отсортированы в порядке убывания, наибольшее число, которое удовлетворяет нашему Предикат - это первый элемент отфильтрованного списка. Мы даже не нужно использовать конечный список для нашего начального набора. Это лень в действие снова Потому что мы только в конечном итоге использовать голову отфильтрованного список, не имеет значения, является ли отфильтрованный список конечным или бесконечным. Оценка останавливается, когда найдено первое адекватное решение.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow