15

次の関数がある場合、それは副作用がなく、同じ入力x に対して常に同じ結果を生成するという点で純粋であると見なされます。

public static int AddOne(int x) { return x + 1; }

私が理解しているように、ランタイムが関数の純度を理解していれば、戻り値を再計算する必要がないように実行を最適化できます。

C# でこの種のランタイム最適化を実現する方法はありますか? そして、この種の最適化には名前があると思います。それは何と呼ばれていますか？

編集:明らかに、私の例の関数は、この種の最適化から多くの利益を得ることはありません. この例は、実際の例ではなく、私が念頭に置いていた純粋さのタイプを表現するために与えられました.

4

8 に答える 8

26

他の人が指摘したように、既に計算した結果を再計算するコストを節約したい場合は、関数をメモ化できます。これは、メモリ使用量の増加と引き換えに速度を向上させます。キャッシュが際限なく大きくなり、メモリが不足する可能性があると思われる場合は、時々キャッシュをクリアすることを忘れないでください。

ただし、結果をメモ化する以外に、純粋な関数に対して実行できる他の最適化があります。たとえば、副作用のない純粋な関数は、通常、他のスレッドで安全に呼び出すことができます。多くの純粋な関数を使用するアルゴリズムは、多くの場合、複数のコアを利用するために並列化できます。

この分野は、大規模なマルチコア マシンがより安価になり、より一般的になるにつれて、ますます重要になります。C# 言語の長期的な研究目標は、言語、コンパイラ、およびランタイムで純粋な関数 (および純粋ではないが「分離された」関数) の能力を活用する方法を見つけ出すことです。しかし、それには多くの困難な問題が伴います。この問題については、産業界や学界で最善のアプローチについてほとんどコンセンサスが得られていません。トップマインドはそれについて考えていますが、すぐに大きな結果を期待することはできません.

于 2009-09-01T15:24:10.003 に答える
8

計算にコストがかかる場合、結果を辞書にキャッシュできますか?

    static Dictionary<int, int> cache = new Dictionary<int, int>();
    public static int AddOne(int x)
    {
        int result;
        if(!cache.TryGetValue(x, out result))
        {
            result = x + 1;
            cache[x] = result;
        }
        return result;
    }

もちろん、この場合の辞書検索は、追加よりもコストがかかります:)

ここで Wes Dyer によって説明されている、関数型メモ化を行うための別のはるかに優れた方法があります: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx - このキャッシングをたくさん行うと、その後、彼の Memoize 関数を使用すると、多くのコードを節約できる可能性があります...

于 2009-09-01T15:15:26.387 に答える
2

機能的なメモ化を探していると思います

于 2009-09-01T15:15:44.480 に答える
2

あなたが求めているテクニックはメモ化です。関数に渡された引数をキーオフした実行結果を、配列または辞書にキャッシュします。ランタイムはそれを自動的に適用する傾向はありませんが、適用する場合は確かにあります。C# も .NET も自動的にメモ化を適用しません。自分でメモ化を実装することはできますが、これはかなり簡単ですが、通常は、計算を繰り返す傾向があり、十分なメモリがある低速の純粋な関数に対してのみ有効です。

于 2009-09-01T15:16:37.367 に答える
1

これはおそらくコンパイラによってインライン化されます（別名インライン展開）...

「コードの最適化」フラグを設定してコードをコンパイルすることを確認してください（VS：プロジェクトのプロパティ/ビルドタブ/コードの最適化）

他にできることは、結果をキャッシュすることです (別名memoization )。ただし、ルックアップ ロジックが原因で初期パフォーマンスが大幅に低下するため、これは遅い関数 (つまり、int 加算ではない) でのみ興味深いものです。

メモリへの影響もありますが、これは弱い参照を巧みに使用することで管理できます。

私が理解しているように、ランタイムが関数の純度を理解していれば、戻り値を再計算する必要がないように実行を最適化できます。

あなたの例では、コンパイル時に x がわからない限り、ランタイムは結果を計算する必要があります。その場合、コードは定数の折りたたみを使用してさらに最適化されます

于 2009-09-01T15:12:47.497 に答える
0

コンパイラは、インライン化(呼び出しサイトで関数呼び出しをその関数の本体に置き換える) と定数伝播(自由変数のない式をその式の結果に置き換える) を組み合わせて、この関数を最適化できます。たとえば、このコードでは次のようになります。

AddOne(5);

AddOne はインライン化できます。

5 + 1;

定数伝播は式を単純化できます。

6;

(デッドコードの削除により、この式をさらに単純化できますが、これは単なる例です)。

AddOne()に副作用がないことを知ることで、コンパイラは一般的な部分式の削除を実行できるようになる可能性もあります。したがって、次のようになります。

AddOne(3) + AddOne(3)

次のように変換できます。

int x = AddOne(3);
x + x;

または強度の低下によって、さらに：

2*AddOne(3);

これらの最適化を実行するように c# JIT コンパイラに命令する方法はありません。独自の裁量で最適化します。しかし、それは非常にスマートであり、ユーザーの介入なしでこの種の変換を実行するために安心して信頼できるはずです。

于 2009-09-01T15:16:35.853 に答える
0

コンパイラはどのようにそれを行うことができますか? 実行時に渡される x の値をどのように知るのでしょうか?

およびre：インライン化に言及する他の回答...私の理解では、インライン化（​​最適化として）は、副作用がないためではなく、1回だけ（または非常に数回だけ...）使用される小さな関数に対して保証されます。 ..

于 2009-09-01T15:16:48.100 に答える