19.5 メモ化
メモ化とは、低速な関数呼び出しの結果をキャッシュし、関数が同じ入力で再度呼び出されたときに、再評価する代わりにキャッシュされた値を返す手法です。同じ入力が既知の予測可能な方法で何度も発生する場合、関数呼び出しをルックアップ テーブルに置き換えることは非常に一般的です。メモ化は、本質的にはこの手法の拡張であり、実行時にもルックアップ テーブルが拡張され、以前には見られなかった新しい引数が提供されます。基本的な理論的背景は、Wikipedia または学部レベルのコンピューター サイエンスの教科書に記載されています。
Octave のmemoize関数は、コンパイルされた関数を含む、任意のユーザー関数または Octave 関数にドロップイン メモ化機能を提供します。
: mem_fcn_handle = memoize (fcn_handle)
関数fcn_handleのメモ化されたバージョンmem_fcn_handleを作成します。
メモ化されたバージョンのmem_fcn_handleの各呼び出しは、内部で管理されているテーブルに対して入力をチェックし、入力が以前に発生した場合は、関数全体を再度評価するのではなく、テーブル自体から関数呼び出しの結果が返されます。これにより、同じ入力で複数回呼び出される関数の実行が高速化されます。
たとえば、ここでは、 という名前の低速なユーザー記述関数を取り出しslow_fcn 、それを新しいハンドルにメモ化しますcyc。両方のバージョンの最初の実行には同じ時間がかかりますが、メモ化されたバージョンの後続の実行では、以前に計算された値が返されるため、実行時間の 2.4 秒が 2.4 ミリ秒に短縮されます。最終チェックでは、両方のバージョンから同じ結果が返されたことを確認します。
>> tic; p = slow_fcn (5040); toc Elapsed time is 2.41244 seconds. >> tic; p = slow_fcn (5040); toc Elapsed time is 2.41542 seconds. >> cyc = memoize (@slow_fcn); >> tic; r = cyc (5040); toc Elapsed time is 2.42609 seconds. >> tic; r = cyc (5040); toc Elapsed time is 0.00236511 seconds. >> all (p == r) ans = 1
See also: clearAllMemoizedCaches.
関数をメモ化するにはz = foo(x, y)、次の一般的なパターンを使用します。
foo2 = memoize (@(x, y) foo(x, y)); z = foo2 (x, y);
上記の例では、最初の行でfoo2関数のメモ化されたバージョンが作成されますfoo。単純なラッピングのみの関数の場合、この行は次のように短縮することもできます。
foo2 = memoize (@foo);
2 行目は 、元の関数の代わりにz = foo2 (x, y);メモ化されたバージョンを呼び出します。これにより、入力が以前に発生した場合は、元の関数を再度評価する代わりに、呼び出しをインターセプトして、テーブルから検索された値に置き換えることができます。 foo2memoize
ただし、これにより関数の 最初の呼び出しが高速化されるのではなく、後続の呼び出しのみが高速化されることに注意してください。
各関数のルックアップ テーブルを作成して管理することで発生するオーバーヘッドのためmemoize、この手法は実行に少なくとも数秒かかる関数にのみ有効であることに注意してください。このような関数は、わずか 1 ミリ秒程度のテーブル ルックアップで置き換えることができますが、元の関数自体がわずか数ミリ秒しかかからなかった場合、それをメモ化しても速度は上がりません。
再帰関数も、次のようなパターンを使用してメモ化できます。
function z = foo (x, y) persistent foo2 = memoize (@foo); foo2.CacheSize = 1e6; ## Call the memoized version when recursing z = foo2 (x, y); endfunction
CacheSize再帰関数内などからの大量の関数呼び出しを予測して、オプションで を増やすことができます。 を超えると 、CacheSizeメモ化テーブルのサイズが変更され、速度が低下します。 を増やすと、CacheSize事前割り当てのように動作して実行速度が向上します。
この関数は、clearAllMemoizedCachesメモ化テーブルが不要になったときにそれをクリアします。
: clearAllMemoizedCaches ()
メモ化されたキャッシュをすべてクリアします。
メモ化は、どの関数がどの入力で呼び出されたかを示す内部テーブルを維持します。この関数は、メモリを解放するか、新たに開始するために、それらのテーブルをクリアします。
See also: memoize.