4

過去数日間、私は主にパフォーマンスの側面で LazyEvaluation を調査しました。

さまざまな記事を読んでもよくわかりませんが、以下を含むごく少数の記事を読んでいます

遅延評価の利点は何ですか?

これは、構文ツリーの評価を指します。構文ツリーを遅延して評価する場合 (つまり、それが表す値が必要な場合)、計算の前のステップ全体を実行する必要があります。これは遅延評価のオーバーヘッドです。ただし、2 つの利点があります。1)結果がまったく使用されない場合、不必要にツリーを評価しません。

たとえば、if構文を実装した JavaScript。

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

この通常のシナリオでは、パフォーマンスの問題はありません。

評価される場合は実行され、評価されない場合は構文ツリーで無視されます。

ただし、一部の再帰ループでは、たとえば、Tak 関数 AKA Tarai 関数

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

JS の Eager Evaluation 戦略は関数 (引数) の必然性を評価するため、if - else - 評価されない制御が機能しなくなり、 tak 関数の評価ステップの数が爆発的に増加します。

Eager Evaluation (JS や他の言語の) のこの欠点に対して、Haskell はtakをそのまま問題なく評価でき、 lazy.jsなどの一部の JS ライブラリは、再帰的なリスト管理が必要な関数型プログラミングのような特定の領域で優れています。

無限リストは別として、これが LazyEvaluation のパフォーマンス上の利点の正確な理由であることを理解しています。私は正しいですか？

4

1 に答える 1

4

あなたは正しい考えを持っていると思います。

ただし、すべての複雑さが必要だとは思いません。JavaScript が

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

veryExpensiveFunctionそれが実装されていると想像してください。

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

JavaScript||が遅延している (必要な場合にのみ 2 番目の引数を評価する) 場合、これは非常に迅速に返されます (trueまあ、本当だからです!)。代わりに実装された場合

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

  return a || b;
}

引数を不必要に評価したため、これを評価するには時間がかかります。ここで、適用された魔法||がすべての関数 (つまり遅延言語) に適用されたと想像してください。おそらく、遅延がもたらすパフォーマンス上の利点の種類を想像することができます。

あなたの例では

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)); }

すべてが怠惰だったと想像してみましょう。

 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(   true  ? 2 : tak(tak(1-1, 2, 3), tak(2-1, 1, 3), tak(3-1, 1, 2));
 console.log(2);

この例では (ひどいタイプミスはしていないと仮定します)、引数以外を評価する必要はなく、再帰呼び出しも行われません。

于 2013-07-18T07:18:07.230 に答える