LazyEvalutaion的性能优势究竟在哪里出现？ [英] Where exactly does the performance advantage of LazyEvalutaion emerge from?

问题描述

在过去的几天中，我对LazyEvaluation进行了研究，主要是在性能方面，从LazyEvalutaion的性能优势出现的位置开始思考。

对于我阅读各种文章已经很不清楚了，但很少有包括

懒惰评估的优势是什么？

这指语法树的评估。如果您懒惰地评估
语法树（即需要它所代表的值），则
必须在整个
整个计算过程中执行前面的步骤。这是懒惰评估的开销。但是，有两个优点b $ b。 1）如果
结果从不使用，

例如，JavaScript实现 if 语法。

  if（true）
 {
 //评估
} 
其他
 {
 //不评估
} 
  

在这种普通的情况下，我们没有任何性能问题。

待评估完成后，在语法树中不会被评估。

但是，在某些递归循环中，例如 Tak函数AKA Tarai函数
$ b

函数tak x，y，z）{
return（x <= y）？ y：
tak（x-1，y，z），
tak（y-1，z，x），
tak（z-1，x，y））; }

由于JS的Eager评估策略评估函数（参数）的必然性，因此
if - else - not被评估控制不再有效，并且 tak功能的评估步骤数量爆炸。

针对此缺点渴望评价（JS或其他语言），Haskell可以毫无问题地评估 tak ，并且可以评估一些JS库，如 lazy.js 在需要递归列表管理的功能性编程等特定领域性能优于

。

除了无限列表之外，我明白这是LazyEvaluation性能优势的确切原因。我是否正确？

解决方案

我认为您的想法是正确的。

我不认为你需要所有的复杂性。想象一下，JavaScript是

  if（veryExpensiveFunction（））{
 doThis（）; 
} else {
 doThat（）; 
 
 $ / code> 

现在想象一下 veryExpensiveFunction 已实现。

 函数veryExpensiveFunction（）{
 return true || evenMoreExpensiveFunction（）; 
 
  

如果JavaScript因为 || 是懒惰的（如果需要的话，只评估第二个参数），这将很快返回（因为 true 是，是的，真的！）。如果它被实现，而不是像

 函数veryExpensiveFunction（）{
 var a = true; 
 var b = evenMoreExpensiveFunction（）; //强制评估
 
返回一个|| b; 
} 
  

这需要很长时间才能评估，因为您不必要地评估参数。现在设想应用于 || 的魔法应用于每个函数（即懒惰语言），并且您可以想象懒惰可能带来的那种性能优势。 p>



在您的示例中

 函数tak（x，y，z）{返回（x <= y）？ y：tak（tak（x-1，y，z），tak（y-1，z，x），tak（z-1，x，y））; } 
  

让我们假设一切都很懒。

  var a = tak（1,2,3）; 
  

这没有任何作用（无需评估）。 a 未使用，因此没有评估。

  var a = tak（1,2,3）; 
 console.log（a）; 
  

现在我们可以推动 tak 。当我们需要得到结果时进行评估，我们首先将值替换（用它们的参数替换变量）。然后我们评估条件，然后只评估我们需要的条件一方。



  console.log（（1 < = 2）？2：tak（tak（1-1,2,3），tak（2-1,1,3），tak（3-1,1,2））; 
 console.log（真正的？2：tak（tak（1-1,2,3），tak（2-1,1,3），tak（3-1,1,2））; 
 console.log（2） ; 
  

在这个例子中（假设我没有犯任何可怕的拼写错误），那么我们不需要评估除参数以外的任何其他内容，并且不进行递归调用。

In the past few days, I have researched LazyEvaluation, in performance aspect mostly, wondering from where the performance advantage of LazyEvalutaion emerges.

It's been so unclear to me reading various articles but a very few including

What are the advantages of Lazy Evaluation?

This refers to the evaluation of a syntax tree. If you evaluate a syntax tree lazily (i.e. when the value it represents is needed), you must carry it through the preceeding steps of your computation in its entirety. This is the overhead of lazy evaluation. However, there are two advantages. 1) you will not evaulate the tree unnecessarily if the result is never used,

JavaScript, for instance, implemented if syntax.

if(true)
{
    //to evaluate
}
else
{
    //not to evaluate
}

In this ordinary scenario, we don't have any performance issue.

To be evaluated is done, not to be evaluated is ignored in the syntax tree.

However, in some recursive loop, for instance, Tak function AKA Tarai function

function tak(x,y,z){ return (x <= y) ? y : tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)); }

Since Eager Evaluation strategy of JS evaluates function(arguments) inevitability, the if - else - not to be evaluated control no longer works, and the number of evaluation step of tak function explodes.

Against to this disadvantage of Eager Evaluation(of JS or other languages), Haskell can evaluate the tak without problems as it is, and some JS library such as lazy.js outperforms in a specific area like functional programming where recursive list management required.

Aside from infinite list, I understand this is the exact reason for performance advantage of LazyEvaluation. Am I correct?

解决方案

I think you've got the right idea.

I don't think you need all the complexity though. Imagine that the JavaScript was

if (veryExpensiveFunction()) {
  doThis();
} else {
  doThat();
}

Now imagine that veryExpensiveFunction is implemented.

function veryExpensiveFunction() {
   return true || evenMoreExpensiveFunction();
}

If JavaScript because || is lazy (only evaluates the second argument if needed) this will return very quickly (because true is, well, true!). If it was implemented instead like

function veryExpensiveFunction() {
  var a = true;
  var b = evenMoreExpensiveFunction(); // forces the evaluation

  return a || b;
}

This would take ages to evaluate because you've unnecessarily evaluated the arguments. Now imagine that the magic applied to || was applied to every function (i.e. a lazy language) and you can probably imagine the sort of performance advantages that laziness might bring.

In your example

function tak(x,y,z){ return (x <= y) ? y : tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)); }

Let's imagine that everything was lazy.

 var a = tak(1,2,3);

This doesn't do anything (nothing needs to be evaluated). a isn't used, so nothing is evaluated.

 var a = tak(1,2,3);
 console.log(a);

Now we're in a position to drive the evaluation of tak. Evaluating as we need to get the results, we first substitute the values in (replace variables with their arguments). We then evaluate the condition, and then only the side of the conditional that we need.

 console.log((1 <= 2) ? 2 : tak(tak(1-1, 2, 3), tak(2-1, 1, 3), tak(3-1, 1, 2));
 console.log(   true  ? 2 : tak(tak(1-1, 2, 3), tak(2-1, 1, 3), tak(3-1, 1, 2));
 console.log(2);

In this example (assuming I've not made any horrible typos), then we don't need to evaluate anything else other than the arguments and no recursive calls are made.

这篇关于LazyEvalutaion的性能优势究竟在哪里出现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！