懒惰评估有哪些优势？

Question

与急切评估相比,懒惰评估有哪些优势？

有什么性能开销？懒惰评估会变得更慢还是更快？为什么(或者它取决于实施？)？

在大多数实现中,懒惰评估实际上如何工作？对我来说,它似乎会慢很多并且内存密集,因为变量必须存储操作以及数字.那么它如何在像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确实等于2,则在Haskell中评估并返回x + 3,否则返回x + 2,没有这样的事情发生,例如,x + 3只是由表达式组成的,说我有:

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

好吧,然后我把它存储在一个变量中,但是如果我从来没有使用过那个变量因为其他一些条件嗯？我在CPU上浪费了一个非常昂贵的整数.(好吧,在实践中你没有赢得这个,但你得到更大的表达的想法)

然后问题是,为什么不是所有的语言都是懒惰的？嗯,简单的原因是在纯函数式语言中,表达式保证根本没有副作用.如果他们有,我们将不得不以正确的顺序评估它们.这就是为什么在大多数语言中他们都受到热切的评价.在表达式没有副作用的语言中,懒惰评估没有风险,所以它是一个合理的选择,以赢回他们往往会失去其他区域的表现.

另一个有趣的副作用是,Haskell中的if-then-else实际上是该类型的函数Bool -> a -> a -> a.在Haskell中,这意味着它接受一个类型为Boolean的参数,另一个类型为any,另一个类型与第一个相同,并再次返回该类型.您不会对不同的控制分支进行无限评估,因为只有在需要时才会对值进行求值,这通常是在编写了一个庞大的表达式时在程序的最后,然后对最终结果进行评估,丢弃编译器认为最终结果不需要的所有东西.例如,如果我自己划分一个非常复杂的表达式,它可以在不评估两个部分的情况下代替'1'.

区别在Scheme中是可见的,传统上是严格评估的,但是有一个叫做Lazy Scheme的惰性变体,在Scheme中(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)你可以用某种递归形式表达和使用无限语法树,因为你只会将它评估到你需要的深度,而不是评估(急切地)全部,这是不可能的.

我不知道哈克尔,但据我所知,编程语言如python或ML急切地评估.例如,要在ML中模拟延迟评估,您必须创建一个不带参数但返回结果的虚函数.这个函数是您的语法树,您可以随时通过使用空参数列表调用它来懒惰地评估它.