PHPでメモ化

PHPでメモ化するときの考え方をメモ。

メモ化とは

メモ化（英: Memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。

Wikipedia - メモ化より抜粋
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E5%8C%96

ようするに

プログラム中に何度も同じ引数で何度も同じ結果を得る関数または処理があるとしたら、返り値を記憶させておくことで計算コストを減らし高速化するということ。

コード

計算量の高い処理を思いつかなかったので適当に。

呼ぶ側

<?PHP

  for ($i=1; $i<=100000; $i++) {
    // 適宜
    echo myMemoize1();
    // echo myMemoize2(100);
    // echo myMemoize3(1, 100);
  }

引数なしの場合

  // 1から100までの等差数列の和を返す
  function myMemoize1 () {
    static $ret = null;

    if (isset($ret)) {
      return $ret;
    }

    $ret = 0;
    for($i=1; $i<=100; $i++) {
      $ret += $i;
    }

    return $ret;
  }

引数1つの場合

  // 1からmaxまでの等差数列の和を返す
  function myMemoize2 ($max) {
    static $ret = array();

    if (isset($ret[$max])) {
      return $ret[$max];
    }

    $series_sum = 0;
    for ($i=1; $i<=$max; $i++) {
      $series_sum += $i;
    }

    $ret[$max] = $series_sum;

    return $ret[$max];
  }

引数複数の場合

  // minからmaxまでの等差数列の和を返す
  function myMemoize3 ($min, $max) {
    static $ret = array();

    if (isset($ret[$min][$max])) {
      return $ret[$min][$max];
    }

    $series_sum = 0;
    for ($i=$min; $i<=$max; $i++) {
      $series_sum += $i;
    }

    $ret[$min][$max] = $series_sum;

    return $ret[$min][$max];
  }

ベンチマークは省略

まとめ

myMemoize3のように、同じ組み合わせの引数が何度も頻繁に使われる可能性があるプログラムには使ったほうが良いでしょう。