为什么惰性评估是有用的？

我一直想知道为什么懒惰的评估是有用的。我还没有听到任何人以一种合理的方式向我解释; 大多数情况下，这种解释最终会归结为“相信我”。

注意: 我不是说记忆。

33356 次浏览
小开

想想这个:

if (conditionOne && conditionTwo) {
doSomething();
}

方法 doSomething ()将只有条件一为真 还有条件二为真时才会执行。 如果條 tionOne 为 false，为什么需要计算條 tionTwo 的结果？在这种情况下，条件2的评估将是浪费时间，特别是如果您的条件是某个方法过程的结果。

这是懒惰评估兴趣的一个例子。

小开
最佳答案

主要是因为它可以更有效率-- 如果不使用它们，则不需要计算它们的值。例如，我可以将三个值传递给一个函数，但是根据条件表达式的顺序，实际上只能使用一个子集。在像 c 这样的语言中，这三个值都会被计算出来，但在哈斯克尔，只有必要的值才会被计算出来。

它还允许像无限列表这样的很酷的东西。我不能在 c 语言中使用无限列表，但在哈斯克尔，这没有问题。无穷列表在数学的某些领域中使用得相当频繁，因此，拥有操纵它们的能力是很有用的。

小开

当你打开你的电脑，Windows 不再打开硬盘上的每一个文件资源管理器，不再启动安装在你电脑上的每一个程序，直到你指出某一个目录或某一个程序是必要的，这就是“懒惰”评估。

“惰性”评估是在需要时执行操作。当它是编程语言或库的一个特性时，它是非常有用的，因为单独实现惰性计算通常比预先计算所有内容更困难。

小开

如果你说的“惰性评估”是指像在复合布尔值中，像在

   if (ConditionA && ConditionB) ...

那么答案很简单，程序消耗的 CPU 周期越少，它运行的速度就越快... ... 如果一大块处理指令对程序的结果没有影响，那么就没有必要(因此是浪费时间)无论如何都要执行它们... ..。

如果 otoh，你指的是我所知道的“懒惰初始化器”，比如:

class Employee
{
private int supervisorId;
private Employee supervisor;


public Employee(int employeeId)
{
// code to call database and fetch employee record, and
//  populate all private data fields, EXCEPT supervisor
}
public Employee Supervisor
{
get
{
return supervisor?? (supervisor = new Employee(supervisorId));
}
}
}

这种技术允许使用类的客户端代码避免调用数据库以获取主管的数据记录，除非使用 Employee 对象的客户端需要访问主管的数据... 这使得实例化一个雇员的过程更快，但是当你需要主管时，第一次调用主管属性将触发数据库调用，数据将被获取并可用..。

小开

此代码片段显示了惰性计算和非惰性计算之间的区别。当然，这个 fibonacci 函数本身可以进行优化，并使用惰性计算代替递归，但这会破坏示例。

让我们假设 五月必须使用前20个数字来表示某些内容，不使用惰性计算，所有这20个数字都必须在前面生成，但是，使用惰性计算，它们只会在需要时生成。因此，您将只支付计算价格时需要。

样本输出

Not lazy generation: 0.023373
Lazy generation: 0.000009
Not lazy output: 0.000921
Lazy output: 0.024205

import time


def now(): return time.time()


def fibonacci(n): #Recursion for fibonacci (not-lazy)
if n < 2:
return n
else:
return fibonacci(n-1)+fibonacci(n-2)


before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()




before3 = now()
for i in notlazy:
print i
after3 = now()


before4 = now()
for i in lazy:
print i
after4 = now()


print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)
小开

我发现惰性评估对很多事情都有用。

首先 ，所有现有的惰性语言都是纯粹的，因为很难推断惰性语言的副作用。

纯语言允许您使用等式推理对函数定义进行推理。

foo x = x + 3

不幸的是，在非惰性设置中，比在惰性设置中更多的语句无法返回，因此这在 ML 等语言中没有多大用处。但是用一种懒惰的语言，你可以安全地推理平等。

其次 ，像 ML 中的“值限制”这样的东西在像 Haskell 这样的懒人语言中是不需要的。这导致了语法的大规模整理。像 ML 这样的语言需要使用诸如 var 或 fun 这样的关键字。在哈斯克尔，这些事情可以归结为一个概念。

第三 ，惰性使您可以编写非常函数化的代码，这些代码可以分段理解。在哈斯克尔，写一个函数体是很常见的，比如:

foo x y = if condition1
then some (complicated set of combinators) (involving bigscaryexpression)
else if condition2
then bigscaryexpression
else Nothing
where some x y = ...
bigscaryexpression = ...
condition1 = ...
condition2 = ...

这使您能够通过对函数体的理解来“自顶向下”地工作。类 ML 语言强制您使用严格求值的 let。因此，您不敢将 let 子句“提升”到函数的主体，因为如果它代价高昂(或者有副作用) ，您不希望它总是被求值。Haskell 可以明确地将细节“推迟”到 where 子句，因为它知道该子句的内容只会在需要时进行评估。

在实践中，我们倾向于使用警卫，并进一步崩溃:

foo x y
| condition1 = some (complicated set of combinators) (involving bigscaryexpression)
| condition2 = bigscaryexpression
| otherwise  = Nothing
where some x y = ...
bigscaryexpression = ...
condition1 = ...
condition2 = ...

第四 ，惰性有时提供了某些算法的更优雅的表达。在哈斯克尔，懒惰的“快速排序”是一个单行程序，它的好处是，如果你只看前几个项目，你只需支付与选择这些项目成本成比例的费用。没有什么可以阻止您严格地执行此操作，但是您可能每次都必须重新编码算法，以获得相同的渐近性能。

第五 ，惰性允许您在语言中定义新的控制结构。你不能写一个新的“如果”。.那么。.别的。.就像用严格的语言构造。如果尝试定义如下函数:

if' True x y = x
if' False x y = y

在一个严格的语言，然后两个分支将被计算，而不管条件值。当你考虑循环时，情况会变得更糟。所有严格的解决方案都需要该语言为您提供某种引用或显式的 lambda 构造。

最后 ，按照同样的思路，类型系统中处理副作用的一些最佳机制，例如 monads，实际上只能在惰性设置中有效地表示。这可以通过比较 F # 的工作流和 Haskell Monads 的复杂性来证明。(您可以用严格的语言来定义单子，但不幸的是，由于缺乏懒惰，您常常无法通过一两条单子定律，而相比之下，工作流会背上一大堆严格的包袱。)

小开

我使用过的延迟计算最有用的应用是一个函数，它按照特定的顺序调用一系列子函数。如果这些子函数中的任何一个失败(返回 false) ，则调用函数需要立即返回。所以我可以这样做:

bool Function(void) {
if (!SubFunction1())
return false;
if (!SubFunction2())
return false;
if (!SubFunction3())
return false;


(etc)


return true;
}

或者，更优雅的解决方案是:

bool Function(void) {
if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
return false;
return true;
}

一旦你开始使用它，你就会看到越来越多地使用它的机会。

小开

惰性计算的一个有用的例子是使用 quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

如果我们现在想要找到列表的最小值，我们可以定义

minimum ls = head (quickSort ls)

它首先对列表进行排序，然后获取列表的第一个元素。但是，由于延迟计算，只计算头部。例如，如果我们采用列表 [2, 1, 3,]的最小值，那么快速排序将首先过滤掉所有小于两个的元素。然后对它进行快速排序(返回单例列表[1]) ，这已经足够了。由于惰性计算，其余部分从不排序，从而节省了大量计算时间。

这当然是一个非常简单的例子，但是懒惰对于非常大的程序同样有效。

然而，所有这些都有一个缺点: 预测程序的运行时速度和内存使用量变得更加困难。这并不意味着懒惰的程序会变慢或占用更多的内存，但是了解这一点是有好处的。

小开

正常顺序评估和惰性评估之间是有区别的(就像在哈斯克尔一样)。

square x = x * x

计算下面的表达式..。

square (square (square 2))

... 热切的评价:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... 正常的秩序评估:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

以及懒惰的评价:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

这是因为惰性计算会查看语法树并进行树转换..。

square (square (square 2))


||
\/


*
/ \
\ /
square (square 2)


||
\/


*
/ \
\ /
*
/ \
\ /
square 2


||
\/


*
/ \
\ /
*
/ \
\ /
*
/ \
\ /
2

... 而正常的顺序计算只做文本扩展。

这就是为什么我们在使用延迟计算时会变得更强大(计算比其他策略终止得更频繁) ，而性能等同于渴望计算(至少在 O 符号中)。

小开

如果没有懒惰的评估，你就不会被允许写下这样的东西:

  if( obj != null  &&  obj.Value == correctValue )
{
// do smth
}
小开

其中，惰性语言允许多维无限数据结构。

虽然 Scheme、 python 等允许带有流的单维无限数据结构，但是您只能沿着一维遍历。

懒惰对于 同样的边缘问题很有用，但是值得注意的是链接中提到的协程连接。

小开

如果你相信西蒙·佩顿·琼斯，那么懒惰的评价并不重要，它只是一件“毛衬衫”，迫使设计师保持语言的纯粹性。我发现自己同情这种观点。

理查德 · 伯德、约翰 · 休斯和拉尔夫 · 亨泽都能用懒惰的评价做出惊人的事情。阅读他们的作品会帮助你欣赏它。良好的起点是 鸟的华丽的数独游戏求解器和休斯关于 为什么函数式编程很重要的论文。

小开

考虑一个井字游戏程序，它有四个功能:

  • 一种移动生成功能，它采用当前板块，并生成一个新板块列表，每个板块应用一次移动。
  • 然后还有一个“移动树”函数，它应用移动生成函数来推导出所有可能的董事会位置，可以从这一个。
  • 有一个极大极小函数，它遍历树(或者可能只是树的一部分)来寻找最佳的下一步。
  • 有一个董事会评估功能，决定是否有一个球员已经赢了。

这就创造了一个清晰的关注点分离。特别是移动生成函数和棋盘评估函数是唯一需要理解游戏规则的函数: 移动树和极小极大值函数是完全可重用的。

现在让我们尝试实施国际象棋，而不是井字游戏。在“热切的”(即传统的)语言中，这不会起作用，因为移动树不适合内存。因此，现在董事会的评估和移动生成功能需要与移动树和极小极大逻辑混合，因为极小极大逻辑必须用来决定哪些移动生成。我们漂亮干净的模块化结构消失了。

然而，在一种惰性语言中，move 树的元素仅仅是为了响应极小极大值函数的需求而生成的: 在我们放开顶部元素的极小极大值之前，不需要生成整个 move 树。因此，我们干净的模块化结构仍然在一个真正的游戏中工作。

小开

懒惰的一个巨大好处是能够编写具有合理分摊界限的不可变数据结构。一个简单的例子是不可变堆栈(使用 F #) :

type 'a stack =
| EmptyStack
| StackNode of 'a * 'a stack


let rec append x y =
match x with
| EmptyStack -> y
| StackNode(hd, tl) -> StackNode(hd, append tl y)

代码是合理的，但是附加两个堆栈 x 和 y 在最佳、最差和平均情况下需要 O (x 的长度)时间。附加两个堆栈是一个整体操作，它涉及堆栈 x 中的所有节点。

我们可以将数据结构重写为惰性堆栈:

type 'a lazyStack =
| StackNode of Lazy<'a * 'a lazyStack>
| EmptyStack


let rec append x y =
match x with
| StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
| Empty -> y

lazy通过挂起构造函数中的代码求值来工作。一旦使用 .Force()进行计算，返回值将被缓存，并在随后的每个 .Force()上重用。

对于延迟版本，追加是一个 O (1)操作: 它返回1个节点并挂起列表的实际重建。当您获取这个列表的头部时，它将计算节点的内容，强制它返回头部并创建一个包含其余元素的暂停，因此获取列表的头部是一个 O (1)操作。

因此，我们的延迟列表处于重新构建的恒定状态，在遍历列表的所有元素之前，不需要为重新构建列表支付成本。使用惰性，该列表支持 O (1)调用和追加。有趣的是，由于我们在访问节点之前不会对它们进行评估，因此完全有可能构造一个具有潜在无限元素的列表。

上面的数据结构不需要在每次遍历时重新计算节点，因此它们与。NET.

小开

与 CPU 相关的惰性评估与与 RAM 相关的垃圾收集相同。GC 允许您假装拥有无限量的内存，从而根据需要请求尽可能多的内存对象。运行时将自动回收不可用的对象。LE 允许你假装你有无限的计算资源-你可以做任何你需要的计算。运行时不会执行不必要的计算(对于给定的情况)。

这些“伪装”模式的实际优势是什么？它从管理资源中释放开发人员(在某种程度上) ，并从源代码中删除一些样板代码。但更重要的是，您可以在更广泛的上下文集中有效地重用解决方案。

假设您有一个数字 S 和数字 N 的列表。您需要从列表 S 中找到与数字 N 最接近的数字 M。可以有两个上下文: 单个 N 和一些 N 的列表 L (例如，对于 L 中的每个 N，查找 S 中最接近的 M)。如果使用延迟计算，可以对 S 进行排序，并应用二进制搜索找到最接近 M 到 N 的值。对于好的延迟排序，对于单个 N 和 O (ln (size (S)) * (size (S) + size (L))步骤，都需要 O (size (S) + size (L))步骤。如果没有延迟计算来获得最佳效率，那么必须为每个上下文实现算法。

小开

我不知道您目前是如何看待这些问题的，但是我发现将惰性评估视为库问题而不是语言特性是很有用的。

我的意思是，在严格的语言中，我可以通过构建一些数据结构来实现惰性计算，而在惰性语言(至少是 Haskell)中，我可以在需要时要求严格。因此，语言选择并不会真正使程序变得懒惰或不懒惰，而只是简单地影响默认情况下得到的结果。

一旦你这样想，然后想想你在哪里编写了一个数据结构，你可以在以后用来生成数据(在那之前不要看太多) ，你会看到很多懒惰计算的用途。

小开

这里还有两点，我相信在讨论中还没有提出来。

  1. 惰性是并发环境中的一种同步机制。它是一种轻量级的简单方法，可以创建对某些计算的引用，并在许多线程之间共享其结果。如果多个线程试图访问一个未计算的值，其中只有一个线程会执行该值，其他线程将相应地阻塞该值，一旦该值可用，其他线程将接收该值。

  2. 懒惰是在纯设置中摊销数据结构的基础。Okasaki 在 纯功能性数据结构中对此进行了详细描述，但其基本思想是，惰性评估是一种可控的变异形式，对于让我们有效地实现某些类型的数据结构至关重要。当我们经常谈论懒惰迫使我们穿上纯洁的发型时，另一种方式也适用: 它们是一对协同的语言特征。

小开

延迟评估对于数据结构最有用。您可以定义一个数组或向量，只归纳指定结构中的某些点，并用整个数组表示所有其他点。这使您可以非常简洁地生成具有高运行时性能的数据结构。

要了解这种情况，您可以查看我的神经网络库 直觉。它大量使用惰性评估，以获得优雅和高性能。例如，我完全去掉了传统的命令式激活计算。一个简单的懒惰的表达方式为我做了一切。

这在 激活函数和反向传播学习算法中都有使用(我只能发布两个链接，所以您需要自己在 AI.Instinct.Train.Delta模块中查找 learnPat函数)。传统上，两者都需要更复杂的迭代算法。

小开

其他人已经给出了所有重要的理由，但我认为一个有用的练习是尝试用严格的语言编写 定点函数，以帮助理解为什么懒惰很重要。

在哈斯克尔，定点功能非常简单:

fix f = f (fix f)

扩展到

f (f (f ....

但是因为 Haskell 是懒惰的，那个无限的计算链不是问题; 计算是“从外到内”的，一切都运行得很好:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

重要的是，重要的不是 fix懒惰，而是 f懒惰。一旦你已经得到了一个严格的 f，你可以把你的手在空中放弃，或预计展开和杂乱的东西了。(这很像诺亚所说的 图书馆是严格/懒惰的，而不是语言)。

现在想象一下用严格的 Scala 编写同样的函数:

def fix[A](f: A => A): A = f(fix(f))


val fact = fix[Int=>Int] { f => n =>
if (n == 0) 1
else n*f(n-1)
}

当然会出现堆栈溢出。如果你想让它起作用，你需要让 f参数按需调用:

def fix[A](f: (=>A) => A): A = f(fix(f))


def fact1(f: =>Int=>Int) = (n: Int) =>
if (n == 0) 1
else n*f(n-1)


val fact = fix(fact1)
小开

  1. 它可以提高效率。这个看起来很明显，但实际上不是最重要的。(还要注意的是，懒惰也可以提高 杀戮的效率——这个事实并不明显。然而，通过存储大量的临时结果而不是立即计算它们，您可能会消耗大量的 RAM。)

  2. 它允许您在普通用户级代码中定义流控制构造，而不是将其硬编码到语言中。(例如，Java 有 for循环; Haskell 有 for函数。Java 具有异常处理; Haskell 具有各种类型的异常单子。C # 有 goto; Haskell 有延续单子...)

  3. 它使您可以将 产生数据的算法与决定要生成的 多少钱数据的算法解耦。您可以编写一个函数来生成一个概念上无限的结果列表，另一个函数根据需要处理列表中的大部分内容。更重要的是，您可以拥有 五生成器函数和 五使用者函数，并且可以高效地生成任何组合——而不是手动编码5 x 5 = 25个同时结合这两个操作的函数。(!)我们都知道脱钩是件好事。

  4. 它或多或少地迫使您设计一种 纯洁函数式语言。走捷径总是很诱人，但是在一种懒惰的语言中，最轻微的杂质都会使代码 疯狂变得不可预测，这对走捷径非常不利。

小开

懒惰评估是穷人的等式推理(理想情况下，可以期望从所涉及的类型和操作的性质中推断出代码的性质)。

它运行良好的示例: sum . take 10 $ [1..10000000000]。我们不介意把它减少到10个数字之和，而不仅仅是一个简单的直接的数字计算。当然，如果没有惰性计算，仅仅为了使用前10个元素，就会在内存中创建一个巨大的列表。它肯定会非常慢，并可能导致内存不足错误。

例如，它没有我们想要的那么好: sum . take 1000000 . drop 500 $ cycle [1..20]。即使是在循环中而不是在列表中，它实际上也会对1000000个数字求和; ，但是它 应该仍然被简化为只有一个直接的数值计算，只有很少的条件和公式。哪个 会比100万个数字加起来好多了。即使是在一个循环中，而不是在一个列表中(即在森林砍伐优化之后)。

另一件事是，它使得 尾递归模风格的代码成为可能，而且它是 很有效风格的。

参考 相关的答案。

小开

节选自 高阶函数

让我们找出10万以下，被3829整除的最大数。 要做到这一点，我们只需筛选出一组我们已知的可能性 解决办法在于。

largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
where p x = x `mod` 3829 == 0

我们首先列出所有低于100,000的数字，降序。 然后我们通过谓词对其进行过滤，因为数字是有序的 以递减的方式，最大的数量，满足我们的 谓词是过滤列表的第一个元素 需要使用一个有限的列表为我们的开始设置。这是懒惰在 动作再次。因为我们最终只使用头部过滤 列表，过滤的列表是有限的还是无限的并不重要。 当找到第一个适当的解决方案时，计算停止。


提交答案