Подтвердить что ты не робот

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

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

Примечание. Я не имею в виду memoization.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Ответ 2

Полезным примером ленивой оценки является использование 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]), который уже достаточно. Из-за ленивой оценки остальное никогда не сортируется, экономя много вычислительного времени.

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

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

Ответ 9

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

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

Ответ 10

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

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

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

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

Ответ 11

Рассмотрим это:

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

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

Вот один пример ленивой оценки...

Ответ 12

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

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

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

Ответ 13

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

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

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

Ответ 14

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

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

Ответ 15

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

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

Ответ 16

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

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

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

Ответ 17

Наиболее полезной эксплуатацией ленивой оценки, которую я использовал, была функция, которая называла серию подфункций в определенном порядке. Если какая-либо из этих подфункций не выполнена (возвращается 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;
}

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

Ответ 18

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

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

Ответ 19

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

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

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

Ответ 20

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

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

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

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

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

Ответ 21

Если под "ленивой оценкой" вы имеете в виду как в combound boolean, например, в

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

Ну, этот метод позволяет клиентскому коду с использованием класса избегать необходимости вызывать базу данных для записи данных Supervisor, за исключением случаев, когда клиент, использующий объект Employee, требует доступа к данным супервизора... это делает процесс создания экземпляра Сотрудник быстрее, и все же, когда вам нужен Супервизор, первый вызов свойства Supervisor вызовет вызов базы данных, и данные будут извлечены и доступны...

Ответ 22

Выдержка из Функции более высокого порядка

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

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

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