ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

More Effective C++ 項目18 予想される計算のコストを償却する

新訂版 More Effective C++ (AddisonーWesley professional co)

新訂版 More Effective C++ (AddisonーWesley professional co)

  • 作者: スコット・メイヤーズ,安村通晃,伊賀聡一郎,飯田朱美,永田周一
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2007/06/29
  • メディア: 単行本(ソフトカバー)
  • 購入: 8人 クリック: 129回
  • この商品を含むブログ (43件) を見る

項目18 予想される計算のコストを償却する

前回の遅延評価とは逆で、言われる前にやってしまおう、という「過剰積極評価」というアプローチもある。

大規模な数字のデータを表すクラステンプレートを考える。

template<class NumricalType>
class DataCollection {
public:
  NumericalType min() const;
  NumericalType max() const;
  NumericalType avg() const;
  ...
};

min、max、avgがそれぞれ、データに対する現時点での最小値、最大値、平均を返す。
この関数を実現するのに3通りの方法がある。

  • 積極評価を使って、min、max、avgが呼ばれたとき、データを全て調べて適切な値を返す。
  • 遅延評価を使って、実際に値が必要なとき、値を決定できるデータ構造を返す。
  • 過剰積極評価を使って、最小値、最大値、平均を常に追跡し、min、max、avgが呼ばれたときは、正しい値を計算なしで即返すようにする。

過剰積極評価は、ある計算を頻繁に要求することが期待される場合は、1要求あたりの平均コストを下げることが出来る。

過剰積極評価の方法

簡単な方法として、キャッシュとプリフェッチの2つがある。

キャッシュを使う方法では一度計算された値をキャッシュしておき、既に計算済みの値を要求された場合は、計算せずにキャッシュを返すようにする。

プリフェッチは、ディスクからデータを読むときに、データの一部分しか要求していなくても、ブロック全体を読んだりする。
動的にサイズを増やせる配列で、サイズを増やすときにギリギリのサイズを要求するのではなく、2倍のサイズを取ったりするケースもある。

まとめ

遅延評価・過剰積極評価ともに、速度の向上にはメモリ使用量増加というコストが掛かっている。
キャッシュはより大きなメモリを使用するが、一度キャッシュされたものの結果を得る時間は減少する。
プリフェッチは、プリフェッチされたものを置いておく場所が必要だが、参照局所性によりアクセス時間は減少する。

遅延評価は、結果がいつもは必要ないような演算をサポートするときに有効。
過剰積極評価は、結果がほとんど必ず必要、または複数回必要となる演算をサポートする場合に有効。