В чем преимущества Lazy Evaluation?

Question

Какие преимущества существуют для ленивой оценки в отличие от Eager Evaluation?

Какие служебные накладные расходы существуют? Будет ли ленивая оценка медленнее или быстрее? Почему (или это зависит от реализации?)?

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

Answer 1

Это относится к оценке дерева синтаксиса. Если вы оцениваете дерево синтаксиса лениво (т. Е. Когда значение, которое оно представляет, необходимо), вы должны перенести его с помощью предыдущих шагов вычисления в целом. Это накладные расходы ленивой оценки. Однако есть два преимущества. 1) вы не будете излишне избегать дерева, если результат никогда не будет использован, и 2) вы можете выражать и использовать бесконечное синтаксическое дерево в некоторой рекурсивной форме, потому что вы будете когда-либо оценивать его до необходимой глубины, в отличие от оценки (с нетерпением) в полном объеме, что было бы невозможно.

Я не знаю haskel, но насколько я знаю, языки программирования, такие как python или ML, оценивают с нетерпением. Например, чтобы моделировать ленивую оценку в ML, вы должны создать фиктивную функцию, которая не принимает никаких параметров, но возвращает результат. Эта функция - это ваше синтаксическое дерево, которое вы можете лениво оценить в любое время, вызвав его пустым списком аргументов.

Answer 2

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

Одно использование (или неправильное использование) ленивой оценки заключается в том, чтобы сделать порядок инициализации объекта неявным, а не явным. Перед тем:

def initialize 
    setup_logging # Must come before setup_database 
    setup_database # Must come before get_addresses 
    setup_address_correction # Must come before get_addresses 
    get_addresses 
end 

def setup_logging 
    @log = Log.new 
end 

def setup_database 
    @db = Db.new(@log) 
end 

def setup_address_correction 
    @address_correction = AddressCorrection.new 
end 

def get_addresses 
    @log.puts ("Querying addresses") 
    @addresses = @address_correction.correct(query_addresses(@db)) 
end 

С ленивой оценкой:

def initialize 
    get_addresses 
end 

def log 
    Log.new 
end 
once :log 

def db 
    Db.new(log) 
end 
once :db 

def address_corrector 
    AddressCorrection.new 
end 
once :address_corrector 

def get_addresses 
    log.puts ("Querying addresses") 
    @addresses = address_corrector.correct(query_addresses(db)) 
end 

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

Answer 3

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

Просто чтобы дать пример, вот непреложный класс стека:

class Stack<T> 
{ 
    public static readonly Stack<T> Empty = new Stack<T>(); 
    public T Head { get; private set; } 
    public Stack<T> Tail { get; private set; } 
    public bool IsEmpty { get; private set; } 

    private Stack(T head, Stack<T> tail) 
    { 
     this.Head = head; 
     this.Tail = tail; 
     this.IsEmpty = false; 
    } 

    private Stack() 
    { 
     this.Head = default(T); 
     this.Tail = null; 
     this.IsEmpty = true; 
    } 

    public Stack<T> AddFront(T value) 
    { 
     return new Stack<T>(value, this); 
    } 

    public Stack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new Stack<T>(value, this) 
      : new Stack<T>(this.Head, this.Tail.AddRear(value)); 
    } 
} 

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

Вот тот же неизменны стек, но теперь его лениво оценивали:

class LazyStack<T> 
{ 
    public static readonly LazyStack<T> Empty = new LazyStack<T>(); 

    readonly Lazy<LazyStack<T>> innerTail; 
    public T Head { get; private set; } 
    public LazyStack<T> Tail { get { return innerTail.Value; } } 
    public bool IsEmpty { get; private set; } 

    private LazyStack(T head, Lazy<LazyStack<T>> tail) 
    { 
     this.Head = head; 
     this.innerTail = tail; 
     this.IsEmpty = false; 
    } 

    private LazyStack() 
    { 
     this.Head = default(T); 
     this.innerTail = null; 
     this.IsEmpty = true; 
    } 

    public LazyStack<T> AddFront(T value) 
    { 
     return new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)); 
    } 

    public LazyStack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)) 
      : new LazyStack<T>(this.Head, new Lazy<LazyStack<T>>(() => this.Tail.AddRear(value), true)); 
    } 
} 

Теперь функция AddRear явно работает в O(1) времени.Когда мы получим доступ к свойству Tail, он будет оценивать значение Lazy только, чтобы вернуть головной узел, затем он останавливается, поэтому его больше не монолитная функция.

Answer 4

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

if x == 1 then x + 3 else x + 2 

В строгом (жадным) оценки, если х действительно равно двум, то х + 3 вычисляется и возвращается, иначе х + 2, в Haskell, ничего подобного не происходит, х + 3 только состоит к выражению, к примеру, у меня есть:

let x = if x == 1 then x + 3 else x + 2 

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

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

Другим интересным побочным эффектом является то, что if-then-else в Haskell действительно является функцией типа Bool -> a -> a -> a. В Haskell это означает, что он принимает один аргумент типа Boolean, другого из любого типа, другого типа того же типа, что и первый, и снова возвращает этот тип. Вы не сталкиваетесь с бесконечной оценкой различных ветвей управления, потому что значения оцениваются только тогда, когда они необходимы, что обычно находится в самом конце программы, когда огромное выражение составлено и затем оценивается для окончательного результата, отбрасывая все, что, по мнению компилятора, не требуется для конечного результата. Например, если я делю исключительно сложное выражение, его можно просто заменить на «1» без оценки обеих частей.

Разница видна на схеме, которая традиционно строго оценивается, но ленивый вариант называется Ленивый схема, на схеме (display (apply if (> x y) "x is larger than y" "x is not larger than y")) является ошибкой, поскольку if не является функцией, это специализированный синтаксис (хотя некоторые говорят, что синтаксис не является особенным в Scheme вообще), поскольку он не обязательно оценивает все его аргументы, иначе у нас не хватит памяти, если мы попытались вычислить факториал, например. В Lazy Scheme это работает отлично, потому что ни один из этих аргументов не оценивается вообще, пока функция действительно не нуждается в результатах для продолжения оценки, например дисплее.