| 翻訳と辞書 |
メモ化[めもか]
メモ化（）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。分割統治法とメモ化の両方を利用したものを動的計画法と呼ぶ。
==概要==
メモ化（memoization）という用語は1968年にドナルド・ミッキーがラテン語の （覚えておく）から作った造語である〔Michie, Donald, "Memo Functions and Machine Learning," ''Nature'', No. 218, pp. 19-22, 1968.〕。''memorization''（記憶、暗記）は同根語であってよく似ているが、メモ化という言葉は情報工学では特別な意味を持つ。
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備えたものに限られる。すなわち、メモ化されたことで副作用が生じない場合に限られる。メモ化の実装ではルックアップテーブルなどの参照方式が使われるが、メモ化では参照されるテーブルの内容は必要に応じて格納されるという点で、通常のテーブル参照とは異なる。
メモ化は関数の時間コストを領域コストに交換して、時間コストを低減させる手段である。すなわち、メモ化された関数は速度の面で最適化され、記憶装置の領域という面ではより多く消費する。計算複雑性理論は、アルゴリズムの時間と領域のコストを扱う。全ての関数には時間と領域についての複雑性が定義される。
このようにトレードオフが発生するが、同様のトレードオフがある最適化とは異なる。というのも、演算子強度低減などの最適化はコンパイル時のものだが、メモ化は実行時の最適化であるためである。さらに言えば、演算子強度低減は例えば、乗算を加算の組合せで表すことで性能を改善しようとするもので、プラットフォームのアーキテクチャに深く依存している。一方、メモ化はプラットフォームからは独立した戦略である。
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「メモ化」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|