私は2D曲線アルゴリズムを書いていて、効果的に合計を行うコードが少しありました:
for (i=0, end=...; i<end; i++) {
value += coefficients[i] * expensiveToCalculateValue(i);
}
coefficients[i]
一部の反復ステップでは値がゼロでした。0 回何かが 0 であるため (少なくとも単純な算術規則の下では)、最初に 0 かどうかをチェックし、coefficients[i]
0 である場合はcontinue
次の反復に進むことで、このコードを大幅に最適化できると考えました。追加、ソート、見事に機能します。
しかし、これには疑問が残ります:なぜこれが私のために行われないのですか? これは乗算の創造的なニッチ バージョンではなく、単純な算術演算です。実質的にすべての言語は、その時点から結果を不変にするオペランドが見つかった場合、バイナリ OR 演算と AND 演算を短絡します。
このコード (synax 用に変更) を Java、PHP、JavaScript、Perl、Python、C++ で実行してみました。また、Prolog が何をしたかを調べましたが、「ゼロ回 ...」と表示されると誰も気づきませんでした。潜在的に高価な 2 番目 (または 3 番目、4 番目など) の項を評価する必要はありません。
printed = 0;
function veryExpensive() {
print "oh god this costs so much, x" + (printed++);
return 0;
}
value = 0 * veryExpensive() * veryExpensive() * veryExpensive()
それらはすべてveryExpensive()
3 回実行されるだけです。
さて、あなたがそのような人なら、結果が算術式に寄与しないにもかかわらず実行されることに依存できるという事実に基づいて、管理上のオーバーヘッド作業を行う関数を書くことができることveryExpensive
を理解しています(あなたがそうする場合)言語を悪用している可能性がありますが、誰もがプログラミングの人生のある時点で卑劣な忍者コードを愛しています)。言語が算術評価を最適化したとしても、コードの表現力が損なわれることはありません。
では、現在使用されている大量の言語が「true OR ...」および「false AND ...」を最適化するが、「zero TIMES ...」は最適化しない歴史的な前例はありますか? 二項演算を最適化するのに、MUL 0 を最適化しないのはなぜですか? (もし運が良ければ、私たちがショートしない理由について興味深い話を誰かが教えてくれるかもしれません)
アップデート
John Skeet と Nik Bougalis はどちらも、現存する言語でこれを最適化すると問題が発生する理由について良い議論をしていますが、Nik の答えは質問ともう少し一致しているので、彼の答えを「正しい」ものとしてマークしました。とはいえ、それらは同じ問題のさまざまな側面をカバーしているため、本当の答えは 2 つの組み合わせです。