Почему отложенные вычисления полезны?

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

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

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

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

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

поэтому взятие заголовка списка - это операция O (1).

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

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

поэтому взятие заголовка списка - это операция O (1).

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

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

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

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

Представьте, что у вас есть список чисел S и номер N. Вам необходимо найти ближайший к номеру N номер m из списка S. Вы можете иметь два контекста: один n и некоторый список l ns (ei для каждого N в я вы смотрите на ближайшие м в s). Если вы используете ленивую оценку, вы можете сортировать S и применять двоичные поиски, чтобы найти ближайший M до N. Для хорошей ленивой сортировки потребуется o (размеры (ы)) шаги для одного N и O (LN (S)) * (Размер (ы) + размер (L))) Шаги для одинаково распределенного L. Если у вас нет ленивых оценок для достижения оптимальной эффективности, вы должны реализовать алгоритм для каждого контекста.

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

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

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