Войти
В теории языков программирования, ленивой оценке или по запросу -need - это стратегия оценки, которая откладывает вычисление выражения до тех пор, пока не потребуется его значение (нестрогая оценка ), а также позволяет избежать повторения оценки (совместное использование ). Совместное использование может сократить время работы определенных функций экспоненциально по сравнению с другими стратегиями нестрогого вычисления, такими как вызов по имени, которые многократно оценивают одну и ту же функцию вслепую, независимо от того, может ли функция быть мемоизированным.
Однако для длительных операций было бы более целесообразно выполнять их перед любыми чувствительными ко времени операциями, такими как обработка пользовательского ввода в видеоигре.
. Преимущества ленивого вычисления включают:
Ленивое вычисление часто сочетается с мемоизацией, поскольку описан в книге Джона Бентли «Написание эффективных программ». После того, как значение функции вычислено для этого параметра или набора параметров, результат сохраняется в таблице поиска, которая индексируется значениями этих параметров; при следующем вызове функции выполняется консультация с таблицей, чтобы определить, доступен ли уже результат для этой комбинации значений параметров. Если да, то просто возвращается сохраненный результат. Если нет, функция оценивается, и в таблицу поиска добавляется другая запись для повторного использования.
Ленивая оценка может привести к сокращению объема памяти, поскольку значения создаются по мере необходимости. Однако ленивое вычисление трудно сочетать с императивными функциями, такими как обработка исключений и ввод / вывод, потому что порядок операций становится неопределенным. Ленивое вычисление может привести к утечкам памяти.
Противоположностью ленивому вычислению является нетерпеливое вычисление, иногда называемое строгим вычислением. Активная оценка - это стратегия оценки, используемая в большинстве языков программирования.
Ленивое вычисление было введено для лямбда-исчисления Кристофером Уодсвортом и использовано в Plessey System 250 как критическая часть мета-метода лямбда-исчисления. Machine, уменьшая накладные расходы на разрешение для доступа к объектам в адресном пространстве с ограниченными возможностями. Для языков программирования он был независимо представлен Питером Хендерсоном и Джеймсом Х. Моррисом, а также Дэниелом П. Фридманом и Дэвидом С. Уайсом.
Отсроченная оценка используется, в частности, в языках функционального программирования. При использовании отложенного вычисления выражение оценивается не сразу после его привязки к переменной, а тогда, когда оценщик вынужден произвести значение выражения. То есть такой оператор, как x = expression;(то есть присвоение результата выражения переменной) явно требует, чтобы выражение было оценено, а результат помещен в x, но то, что на самом деле находится в x, не имеет значения до тех пор, пока не возникнет потребность в его значении через ссылку на xв каком-либо более позднем выражении, вычисление которого может быть отложено, хотя в конечном итоге растущее дерево зависимостей будет обрезано, чтобы создать какой-то символ, а не другой, который будет видеть внешний мир.
Отложенное вычисление имеет преимущество, заключающееся в возможности создавать вычисляемые бесконечные списки без бесконечных циклов или вопросов размера, мешающих вычислениям. Например, можно создать функцию, которая создает бесконечный список (часто называемый потоком ) из чисел Фибоначчи. Вычисление n-го числа Фибоначчи было бы просто извлечением этого элемента из бесконечного списка, заставляя вычислять только первые n членов списка.
Например, в Haskell язык программирования, список всех чисел Фибоначчи может быть записан как:
fibs = 0: 1: zipWith (+) fibs (tail fibs)
В синтаксисе Haskell: ":"добавляет элемент к списку, tailвозвращает список без его первого элемента, а zipWithиспользует указанную функцию (в данном случае сложение) для объединения соответствующих элементов двух списков для создания третий.
Если программист проявляет осторожность, оцениваются только те значения, которые требуются для получения конкретного результата. Однако некоторые вычисления могут привести к тому, что программа попытается оценить бесконечное количество элементов; например, запрос длины списка или попытка суммирования элементов списка с помощью операции сворачивания приведет к тому, что программа либо не завершит работу, либо запустит из памяти.
Практически во всех распространенных "нетерпеливых" языках операторы if вычисляются лениво.
if a then b else c
оценивает (a), тогда, если и только если (a) оценивается как истинное, он оценивает (b), иначе он оценивает (c). То есть ни (b), ни (c) не будут оцениваться. И наоборот, на нетерпеливом языке ожидаемое поведение таково, что
define f (x, y) = 2 * x set k = f (d, e)
по-прежнему будет оценивать (e), когда вычисление значения f (d, e), даже если (e) не используется в функции f. Однако определяемые пользователем управляющие структуры зависят от точного синтаксиса, поэтому, например,
определяют g (a, b, c) = if a then b else cl = g (h, i, j)
(i) и (j) оба будут оцениваться на нетерпеливом языке. В ленивом языке
l '= if h, то i else j
(i) или (j) будут оцениваться, но не оба сразу.
Ленивое вычисление позволяет определять управляющие структуры обычным образом, а не как примитивы или методы времени компиляции. Если (i) или (j) имеют побочные эффекты или вносят ошибки времени выполнения, тонкие различия между (l) и (l ') могут быть сложными. Обычно можно ввести определяемые пользователем структуры отложенного управления в энергичных языках в качестве функций, хотя они могут отклоняться от синтаксиса языка для энергичной оценки: часто задействованные тела кода (например, (i) и (j)) должны быть заключены в значение функции, поэтому они выполняются только при вызове.
Вычисление короткого замыкания логических управляющих структур иногда называют ленивым.
Многие языки предлагают понятие бесконечных структур данных. Это позволяет давать определения данных в терминах бесконечных диапазонов или бесконечной рекурсии, но фактические значения вычисляются только при необходимости. Возьмем, к примеру, эту тривиальную программу на Haskell:
numberFromInfiniteList :: Int ->Int numberFromInfiniteList n = бесконечность !! n - 1, где бесконечность = [1..] main = print $ numberFromInfiniteList 4
В функции numberFromInfiniteListзначение infinityявляется бесконечным диапазоном, но до фактического значение (или, точнее, конкретное значение по определенному индексу) необходимо, список не оценивается, и даже тогда он оценивается только по мере необходимости (то есть до желаемого индекса.)
Составное выражение может быть в форме EasilyComputed или LotsOfWork, так что если простая часть дает истина можно было бы избежать большой работы. Например, предположим, что нужно проверить большое число N, чтобы определить, является ли оно простым числом, и доступна ли функция IsPrime (N), но, увы, для ее оценки может потребоваться много вычислений. Возможно, N = 2 или [Mod (N, 2) ≠ 0 и IsPrime (N)] помогут, если будет много оценок с произвольными значениями для N.
Составное выражение может быть в форме SafeToTry и Expression, при этом, если SafeToTry имеет значение false, не должно быть попыток вычисления выражения во избежание появления сигнала об ошибке времени выполнения, такой как деление на ноль или выход индекса за границы и т. д. Например, следующий псевдокод находит последний ненулевой элемент массива:
L: = длина (A); Пока L>0 и A (L) = 0, делаем L: = L - 1;
Если все элементы массива равны нулю, цикл будет работать до L = 0, и в этом случае цикл должен быть завершен без попытки ссылаться на нулевой элемент массива, который не существует.
В компьютерных оконных системах отображение информации на экране осуществляется посредством событий раскрытия, которые запускают код отображения в последний возможный момент. Таким образом оконные системы избегают вычисления ненужных обновлений отображаемого содержимого.
Другим примером лени в современных компьютерных системах является копирование при записи выделение страниц или разбиение по страницам, где память выделяется только при изменении значения, хранящегося в этой памяти.
Ленивость может быть полезна для сценариев высокой производительности. Примером является функция Unix mmap, которая обеспечивает загрузку страниц с диска по требованию, так что в память загружаются только те страницы, к которым действительно прикоснулись, а ненужная память не выделяется.
MATLAB реализует копирование при редактировании, где массивы, которые копируются, имеют свое фактическое хранилище памяти, реплицируемое только при изменении их содержимого, что может привести к ошибке нехватки памяти при последующем обновлении элемента. во время операции копирования.
Некоторые языки программирования задерживают вычисление выражений по умолчанию, а некоторые другие предоставляют функции или специальный синтаксис для оценка задержки. В Miranda и Haskell оценка аргументов функции по умолчанию задерживается. Во многих других языках оценка может быть отложена путем явной приостановки вычислений с использованием специального синтаксиса (как в случае «delay» и «force» и схемы . OCaml "lazy" и "Lazy.force") или, в более общем смысле, заключая выражение в преобразователь. Объект, представляющий такую явно отложенную оценку, называется ленивым будущим. Raku использует ленивое вычисление списков, поэтому можно назначать бесконечные списки переменным и использовать их в качестве аргументов для функций, но в отличие от Haskell и Miranda, Raku по умолчанию не использует ленивое вычисление арифметических операторов и функций. 154>
В ленивых языках программирования, таких как Haskell, хотя по умолчанию выражения оцениваются только тогда, когда они требуются, это возможно в в некоторых случаях, чтобы сделать код более активным или, наоборот, снова сделать его более ленивым после того, как он стал более активным. Это может быть сделано путем явного кодирования чего-то, что требует оценки (что может сделать код более энергичным) или избегания такого кода (что может сделать код более ленивым). Строгая оценка обычно подразумевает рвение, но это технически разные концепции.
Однако в некоторых компиляторах реализована оптимизация, называемая анализ строгости, которая в некоторых случаях позволяет компилятору сделать вывод, что значение будет использоваться всегда. В таких случаях это может сделать выбор программиста, принудительно ли использовать это конкретное значение или нет, неуместным, потому что анализ строгости требует строгой оценки.
В Haskell маркировка полей конструктора строгими означает, что их значения всегда будут запрашиваться немедленно. Функцию seqтакже можно использовать для немедленного запроса значения и последующей его передачи, что полезно, если поле конструктора обычно должно быть ленивым. Однако ни один из этих методов не реализует рекурсивную строгость - для этого была изобретена функция с именем deepSeq.
Кроме того, сопоставление с образцом в Haskell 98 по умолчанию является строгим, поэтому необходимо использовать квалификатор ~ , чтобы сделать его ленивым.
В Java ленивая оценка может выполняться с помощью объектов, у которых есть метод для их оценки, когда необходимо значение. Тело этого метода должно содержать код, необходимый для выполнения этой оценки. С момента появления лямбда-выражений в Java SE8 Java поддерживает компактную нотацию для этого. В следующем примере общий интерфейс предоставляет структуру для отложенного вычисления:
interface Lazy{T eval (); }
Каждый класс, реализующий этот интерфейс, должен предоставлять метод eval, а экземпляры класса могут нести любые значения, необходимые методу для выполнения ленивой оценки. Например, рассмотрим следующий код для ленивого вычисления и вывода 2:
Ленивыйa = () ->1; for (int i = 1; i <= 10; i ++) {final Lazy b = a; a = () ->b.eval () + b.eval (); } System.out.println ("a =" + a.eval ());
В приведенном выше примере переменная aизначально относится к ленивому целочисленному объекту, созданному лямбда-выражением () ->1. Оценка этого лямбда-выражения эквивалентна созданию нового экземпляра анонимного класса, который реализует Lazy
Каждая итерация цикла связывает aк новому объекту, созданному путем вычисления лямбда-выражения внутри цикла. Каждый из этих объектов содержит ссылку на другой ленивый объект, b, и имеет метод eval, который дважды вызывает b.eval ()и возвращает сумму. Переменная bздесь необходима для удовлетворения требований Java, чтобы переменные, на которые ссылается лямбда-выражение, были окончательными.
Это неэффективная программа, потому что эта реализация ленивых целых чисел не запоминает результат предыдущих вызовов eval. Это также включает в себя значительную часть автоматической упаковки и распаковки. Что может быть неочевидным, так это то, что в конце цикла программа построила связанный список из 11 объектов и что все фактические добавления, участвующие в вычислении результата, выполняются в ответ на вызов на a.eval ()в последней строке кода. Этот вызов рекурсивно просматривает список для выполнения необходимых дополнений.
Обратите внимание, что лямбда-выражения Java - всего лишь синтаксический сахар. Все, что вы можете написать с помощью лямбда-выражения, можно переписать как вызов для создания экземпляра анонимного внутреннего класса, реализующего интерфейс, и любое использование анонимного внутреннего класса может быть переписано с использованием именованного внутреннего класса, и любой именованный внутренний класс можно переместить на самый внешний уровень вложенности.
В Python 2.x функция range ()вычисляет список целых чисел. При оценке первого оператора присваивания весь список сохраняется в памяти, так что это пример активного или немедленного вычисления:
>>>r = range (10)>>>print r [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>>>print r [3] 3
В Python 3.x функция range ()возвращает специальный объект диапазона, который вычисляет элементы списка по запросу. Элементы объекта диапазона генерируются только тогда, когда они необходимы (например, когда print (r [3])оценивается в следующем примере), поэтому это пример ленивого или отложенного вычисления:
>>>r = range (10)>>>print (r) range (0, 10)>>>print (r [3]) 3
В Python 2.x можно использовать функцию с именем xrange (), которая возвращает объект, который по запросу генерирует числа в диапазоне. Преимущество xrangeв том, что сгенерированный объект всегда будет занимать один и тот же объем памяти.
>>>r = xrange (10)>>>print (r) xrange (10)>>>lst = [x вместо x в r]>>>print (lst) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Начиная с версии 2.2, Python проявляет ленивую оценку, реализуя итераторы (ленивые последовательности) в отличие от последовательностей кортежей или списков. Например (Python 2):
>>>numbers = range (10)>>>iterator = iter (numbers)>>>print numbers [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>>>print iterator>>>print iterator.next () 0
В .NET Framework можно выполнять ленивую оценку с использованием класса System.Lazy. Класс можно легко использовать в F # с помощью ключевого слова lazy, тогда как метод forceпринудительно выполнит оценку. Существуют также специализированные коллекции, такие как Microsoft.FSharp.Collections.Seq, которые обеспечивают встроенную поддержку отложенного вычисления.
let fibonacci = Seq.unfold (fun (x, y) ->Some (x, (y, x + y))) (0I, 1I) fibonacci |>Seq.nth 1000
В C # и VB.NET, класс System.Lazyиспользуется напрямую.
общедоступный int Sum () {int a = 0; int b = 0; Ленивый x = новый Ленивый (() =>a + b); а = 3; b = 5; return x.Value; // возвращает 8} Или более практичный пример:
// рекурсивное вычисление n-го числа Фибоначчи public int Fib (int n) {return (n == 1)? 1: (n == 2)? 1: Фибрилляция (n-1) + Фибра (n-2); } public void Main () {Console.WriteLine ("Какое число Фибоначчи вы хотите вычислить?"); int n = Int32.Parse (Console.ReadLine ()); Ленивый fib = новый Lazy (() =>Fib (n)); // функция подготовлена, но не выполняется bool execute; if (n>100) {Console.WriteLine ("Это может занять некоторое время. Вы действительно хотите вычислить это большое число? [y / n]"); выполнить = (Console.ReadLine () == "y"); } иначе выполнить = false; если (выполнить) Console.WriteLine (fib.Value); // число вычисляется только при необходимости} Другой способ - использовать ключевое слово yield:
