21

与急切评估相比，惰性评估有什么优势？

有什么性能开销？惰性评估会变慢还是变快？为什么（或者它取决于实现？）？

在大多数实现中，惰性求值实际上是如何工作的？对我来说，这似乎会慢得多并且占用大量内存，因为变量必须存储操作和数字。那么在 Haskell 这样的语言中它是如何工作的（注意，我实际上并不知道那种语言）？惰性是如何实现和完成的，以便它不会非常慢/消耗更多空间？

4

4 回答 4

14

惰性评估在创建具有有效摊销边界的数据结构时非常有用。

举个例子，这是一个不可变的堆栈类：

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 值，然后它会停止，因此它不再是一个单一的函数。

于 2010-01-28T01:49:22.373 回答
11

惰性求值是纯函数式编程语言“赢回性能”的共同属性，它的工作原理非常简单，您只需在需要时评估表达式。例如，考虑在 Haskell

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

在严格（急切）评估中，如果 x 确实等于 2，则评估并返回 x + 3，否则 x + 2，在 Haskell 中，不会发生这种情况，x + 3 只是组成表达式，例如，说我有：

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

好吧，然后我将它存储在一个变量中，但是如果由于其他一些条件，我从未使用过该变量怎么办？我在我的 CPU 上浪费了一个非常昂贵的整数加法。（好吧，在实践中你不会在这方面获胜，但你会通过更大的表达来理解这个想法）

那么问题来了，为什么不是所有的语言都懒惰呢？嗯，原因很简单，在纯函数式语言中，表达式保证完全没有副作用。如果他们有，我们将不得不以正确的顺序评估它们。这就是为什么在大多数语言中它们都被热切地评估。在表达式没有副作用的语言中，惰性求值没有风险，因此赢回它们在其他领域往往会失去的性能是一个合乎逻辑的选择。

另一个有趣的副作用是 Haskell 中的 if-then-else 实际上是 type 的函数Bool -> a -> a -> a。在 Haskell 中，这意味着它接受一个布尔类型的参数，另一个是任何类型的参数，另一个与第一个类型相同的参数，然后再次返回该类型。您不会遇到对不同控制分支的无限求值，因为值仅在需要时才求值，这通常是在程序的最后，当一个巨大的表达式已经组成，然后为最终结果求值，丢弃编译器认为最终结果不需要的所有东西。例如，如果我将一个非常复杂的表达式自己分开，它可以直接替换为 '1' 而无需评估这两个部分。

区别在 Scheme 中是可见的，它传统上是严格评估的，但是有一个叫做 Lazy Scheme 的惰性变体，在 Scheme(display (apply if (> x y) "x is larger than y" "x is not larger than y"))中是一个错误，因为if它不是一个函数，它是一种特殊的语法（尽管有人说语法在 Scheme 中根本没有特殊) 因为它不一定会评估它的所有参数，否则如果我们尝试计算阶乘，我们就会耗尽内存。在惰性方案中，它工作得很好，因为在函数真正需要评估结果才能继续之前，根本不会评估这些参数，比如显示。

于 2010-05-19T18:24:26.610 回答
9

这是指对语法树的评估。如果您懒惰地评估语法树（即，当需要它表示的值时），您必须将其完整地通过前面的计算步骤。这是惰性求值的开销。但是，有两个优点。1）如果从未使用过结果，您将不会不必要地评估树，并且 2）您可以以某种递归形式表达和使用无限语法树，因为您只会将其评估到您需要的深度，而不是评估（急切地）完整地，这是不可能的。

我不知道 haskel，但据我所知，python 或 ML 等编程语言会热切地评估。例如，要在 ML 中模拟惰性求值，您必须创建一个不带参数但返回结果的虚拟函数。然后，此函数就是您的语法树，您可以随时通过使用空参数列表调用它来懒惰地评估它。

于 2010-01-27T23:50:52.537 回答
1

在 ruby​​ 中，我们使用函数修饰符（通常称为“once”）来包装一个方法，以便它进行惰性求值。这样的方法只会被评估一次，缓存的值，随后的调用返回该值。

惰性求值的一种用途（或误用）是使对象初始化的顺序隐式而不是显式。前：

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) 自动的。不利的一面是，如果过于依赖这个技巧，控制流程可能会变得不透明。

于 2010-01-28T00:38:13.597 回答