Каковы преимущества Lazy Evaluation?

Question

Какие преимущества есть у Lazy Evaluation по сравнению с Eager Evaluation?

Какие накладные расходы есть? Ленивая Оценка будет медленнее или быстрее? Почему (или это зависит от реализации?)?

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

Answer 1

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

Для примера приведу класс неизменяемых стеков:

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 2

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

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

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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