Чем полезна ленивая оценка?

Учти это:

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

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

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

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

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

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

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

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

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

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

Предположим, мы МАЙ должны использовать для чего-то 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)

Я считаю, что ленивая оценка полезна для многих вещей.

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

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

foo x = x + 3

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

Во-вторых, многие вещи вроде «ограничения значений» в ML не нужны в ленивых языках вроде Haskell. Это приводит к значительному упрощению синтаксиса. ML-подобные языки должны использовать такие ключевые слова, как var или fun. В Haskell все это сводится к одному понятию.

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

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

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;
}

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

Полезным примером ленивого вычисления является использование quickSort:

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

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

minimum ls = head (quickSort ls)

Которая сначала сортирует список, а затем берет первый элемент списка. Однако из-за ленивого вычисления вычисляется только голова. Например, если мы возьмем минимум списка, [2, 1, 3,] quickSort сначала отфильтрует все элементы, которые меньше двух. Затем он выполняет 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

... тогда как обычная оценка порядка выполняет только текстовые расширения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ленивая оценка связана с процессором так же, как сборка мусора с оперативной памятью. GC позволяет вам делать вид, что у вас неограниченный объем памяти, и, таким образом, запрашивать столько объектов в памяти, сколько вам нужно. Среда выполнения автоматически восстановит непригодные для использования объекты. LE позволяет вам делать вид, что у вас неограниченные вычислительные ресурсы - вы можете выполнять столько вычислений, сколько вам нужно. Время выполнения просто не будет выполнять ненужные (в данном случае) вычисления.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отрывок из Функции высшего порядка

Let's find the largest number under 100,000 that's divisible by 3829. To do that, we'll just filter a set of possibilities in which we know the solution lies.

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

We first make a list of all numbers lower than 100,000, descending. Then we filter it by our predicate and because the numbers are sorted in a descending manner, the largest number that satisfies our predicate is the first element of the filtered list. We didn't even need to use a finite list for our starting set. That's laziness in action again. Because we only end up using the head of the filtered list, it doesn't matter if the filtered list is finite or infinite. The evaluation stops when the first adequate solution is found.