11

私はBrianBeckmanと一緒にこのMSDNビデオを見てきましたが、彼の言うことをもっとよく理解したいと思います。

すべての必須プログラマーは、関数をテーブルルックアップに置き換えることができることを学習するこのフェーズを通過します

今、私は大学に行ったことがないC＃プログラマーなので、おそらくどこかで、他の誰もが理解できることを見逃してしまいました。

ブライアンとはどういう意味ですか：

関数はテーブルルックアップに置き換えることができます

これが行われている実際的な例はありますか？それはすべての機能に適用されますか？彼は私が理解できる罪の機能の例を挙げていますが、もっと一般的な言葉でこれをどのように理解するのですか？

4

3 に答える 3

15

ブライアンは、関数もデータであることを示しました。関数は一般に、あるセットから別のセットへの単なるy = f(x)マッピングです。セット{x}からセット{y}へのマッピングですf:X->Y。テーブルもマッピングです：[x1, x2, ..., xn] -> [y1, y2, ..., yn]。

関数が有限集合で動作する場合（これはプログラミングの場合です）、そのマッピングを表すテーブルに置き換えることができます。ブライアンが述べたように、すべての命令型プログラマーは、パフォーマンス上の理由から、関数をテーブルルックアップに置き換えることができるという理解のこの段階を通過します。

ただし、すべての関数をテーブルに簡単に置き換えることができる、または置き換える必要があるという意味ではありません。これは、理論的にはすべての関数に対してそれを実行できることを意味するだけです。したがって、テーブルは（もちろんプログラミングのコンテキストでは）データであるため、関数はデータであるという結論になります。

于 2012-12-07T17:33:32.793 に答える
5

Mathematicaには、関数呼び出しを書き換えルールとして評価することの副作用としてテーブルを作成するという素敵なトリックがあります。古典的なスローフィボナッチを考えてみましょう

fib[1] = 1
fib[2] = 1
fib[n_] := fib[n-1] + fib[n-2]

最初の2行は、入力1と2のテーブルエントリを作成します。これは、次のように言うのとまったく同じです。

fibTable = {};
fibTable[1] = 1;
fibTable[2] = 1;

JavaScriptで。fib[n_]Mathematicaの3行目は、「パターン変数n_をオカレンスの実際の引数に置き換えた後、オカレンスを置き換える書き換えルールをインストールしてください」と述べていfib[n-1] + fib[n-2]ます。リライターはこの手順を繰り返し、最終的fib[n]には指数関数的な数のリライト後にの値を生成します。これは、JavaScriptで取得する再帰関数呼び出しフォームと同じです。

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  return result;
}

再帰呼び出しを行う前に、明示的に格納した2つの値について最初にテーブルをチェックすることに注意してください。ルールの表示順序が重要であるため、Mathematicaエバリュエーターはこのチェックを自動的に行います-Mathematicaは最初により具体的なルールをチェックし、後でより一般的なルールをチェックします。そのため、Mathematicaには2つの割り当て形式が=あり:=ます。前者は、ルールの定義時に右側を評価できる特定のルール用です。後者は、ルールが適用されるときに右側を評価する必要がある一般的なルール用です。

さて、Mathematicaでは、

fib[4]

に書き直されます

fib[3] + fib[2]

その後に

fib[2] + fib[1] + 1

その後に

1 + 1 + 1

そして最後に3になります。これは、次の書き換えでは変更されません。fib[35]と言えば、膨大な表現を生成し、メモリをいっぱいにし、CPUを溶かしてしまうことを想像できます。ただし、秘訣は、最終的な書き換えルールを次のように置き換えることです。

fib[n_] := fib[n] = fib[n-1] + fib[n-2]

fib[n_]これは、「のすべての出現箇所を、の値に新しい特定のルールをインストールし、値をfib[n]生成する式に置き換えてください」という意味です。これは、ルールベース（値のテーブル）を拡張するため、はるかに高速に実行されます。-実行時。

JavaScriptでも同様にできます

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  fibTable[n] = result;
  return result;
}

これは、fibの以前の定義よりもはるかに高速に実行されます。

これは「自動メモ化」と呼ばれます[原文のまま-「メモ化」ではなく、自分でメモを作成する場合の「メモ化」]。

もちろん、現実の世界では、作成されるテーブルのサイズを管理する必要があります。Mathematicaでテーブルを調べるには、

DownValues[fib]

JavaScriptでそれらを検査するには、

fibTable

Node.JSでサポートされているようなREPLで。

于 2012-12-07T23:11:31.940 に答える
2

関数型プログラミングの文脈では、参照透過性の概念があります。参照透過性のある関数は、プログラムの動作を変更することなく、任意の引数（または引数のセット）の値に置き換えることができます。

参照透過性

たとえば、1つの引数nをとる関数Fについて考えてみます。Fは参照透過性であるため、F（n）はnで評価されたFの値に置き換えることができます。プログラムに違いはありません。

C＃では、これは次のようになります。

public class Square
{
    public static int apply(int n)
    {
        return n * n;
    }

    public static void Main()
    {
        //Should print 4
        Console.WriteLine(Square.apply(2));
    }
}

（私はJavaのバックグラウンドから来たC＃にあまり精通していないので、この例が構文的に正しくない場合はご容赦ください）。

ここで、関数applyは、引数の2乗を返すだけなので、引数2で呼び出されたときに4以外の値を持つことができないことは明らかです。関数の値は、その引数nにのみ依存します。言い換えれば、参照透過性。

Console.WriteLine(Square.apply(2))では、との違いは何ですかConsole.WriteLine(4)。答えは、すべての意図が目的であるため、まったく違いはないということです。プログラム全体を調べて、のすべてのインスタンスをSquare.apply(n)、によって返される値に置き換えることができSquare.apply(n)ます。結果はまったく同じになります。

では、Brian Beckmanは、関数呼び出しをテーブルルックアップに置き換えることについての彼のステートメントで何を意味しましたか？彼は、参照透過性関数のこの特性について言及していました。プログラムの動作に影響を与えずSquare.apply(2)に置き換えることができる場合は、最初の呼び出しが行われたときに値をキャッシュして、関数の引数でインデックス付けされたテーブルに配置してください。4の値のルックアップテーブルは、次のSquare.apply(n)ようになります。

              n: 0 1 2 3 4  5  ...
Square.apply(n): 0 1 4 9 16 25 ...

また、への呼び出しでは、関数を呼び出す代わりに、テーブルでnSquare.apply(n)のキャッシュされた値を見つけて、関数呼び出しをこの値に置き換えることができます。これにより、プログラムの速度が大幅に向上する可能性が高いことは明らかです。

于 2012-12-07T17:49:48.073 に答える