Command disabled: index


̃Gg[͂ĂȃubN}[Nɒlj

PHP :: static を使って関数をメモ化する



メモ化とは
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E5%8C%96

  • 引用
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、
後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。
メモ化可能な関数は参照透過性を備えたものに限られる。
すなわち、メモ化されたことで副作用が生じない場合に限られる。


要は、関数の返り値を記憶しておき、それを再利用することで計算を省略して処理速度を向上させる手法です。
ただし、引用でも触れていますが、メモ化されたことで副作用が生じない場合に限られます。
ここで言う「副作用が生じない」とは、関数が呼ばれたタイミングや状態で、「関数の返り値が変化することが無い」ということを指します。

一回のリクエストで複数回コールされる関数で、以下のいずれかに当てはまる場合は、メモ化すると良いかもしれません。

  • 副作用が生じないことが前提で、
    • 関数内で複雑な正規表現を使っている
    • 巨大な配列のループ処理
    • 巨大な xml や csv のパース
    • その他、パフォーマンス的に不利な仕様の関数


php では、下記のように static を使って返り値を記憶しておくことができます。

<?php
 
function hoge()
{
    static $ret = null;
    if ($ret !== null) return $ret;
 
    /**
     *
     * 大きなリソースを消費する何か複雑な処理が書かれるとする。
     *
     *   :
     *   :
     *
     * ただし、この関数が呼ばれたタイミングや状態によって、返り値が変化する場合は
     * この手法(メモ化)は使えない。
     * 同一プロセス内で何度呼ばれても返り値が同一の場合のみ有効。
     *
     *   例えば、この関数内で下記のように、実行する時刻によって
     *   何か変化がある場合はNG
     *
     *   $mode = 1;
     *   if (date('g') > 10) {
     *       $mode = 2;
     *   }
     */
 
    $ret = $result;
    // $result: 処理した結果を保持していると仮定。
 
    return $ret;
}

返り値が null になる可能性がある場合は、$ret の初期化と判定を以下のように false 等 に変更します。

static $ret = false;
if ($ret !== false) return $ret;

当然ですが、上記の場合 false は返らない前提です。



動作サンプルとベンチマーク

<?php
 
/**
 * $min .. $max の合計
 *
 * hoge(1, 4) = 1 + 2 + 3 + 4 = 10
 *
 */
function hoge($min, $max)
{
    static $ret = array();
    if (isset($ret[$min][$max])) return $ret[$min][$max];
 
    $buf = 0;
    foreach (range($min, $max) as $i) {
        $buf += $i;
    }
    $ret[$min][$max] = $buf;
 
    return $ret[$min][$max];
}
 
$bench = new Benchmark();
$bench->start();
echo '1回目: '.hoge(1, 100000).PHP_EOL;
echo $bench->stop().PHP_EOL.PHP_EOL;
 
$bench->start();
echo '2回目: '.hoge(1, 100000).PHP_EOL;
echo $bench->stop().PHP_EOL.PHP_EOL;

↓結果

1回目: 5000050000
0.125004 sec / init_mem: 327 KB / fini_mem: 327 KB / peak_mem: 8,653 KB

2回目: 5000050000
0.000062 sec / init_mem: 327 KB / fini_mem: 327 KB / peak_mem: 8,653 KB
  • ちょっと極端な例ですが、1回目と2回目を比較すると雲泥の差です。



上記サンプルで使ったベンチマーククラス

<?php
 
class Benchmark
{
    private $start_time;
    private $end_time;
    private $init_memory;
    private $fini_memory;
    private $peak_memory = 'unknown (PHP 5 >= 5.2.0)';
    private $format;
 
    public function __construct($format = '%.6f sec / init_mem: %s KB / fini_mem: %s KB / peak_mem: %s KB')
    {
        $this->start_time = 0;
        $this->end_time   = 0;
        $this->format     = $format;
    }
 
    public function start()
    {
        $this->start_time = $this->microtimeFloat();
        $this->init_memory = number_format(round(memory_get_usage() / 1024, 2));
    }
 
    public function stop()
    {
        $this->end_time = $this->microtimeFloat();
        $this->fini_memory = number_format(round(memory_get_usage() / 1024, 2));
 
        if (version_compare(PHP_VERSION, '5.2.0', '>=')) {
            $this->peak_memory = number_format(round(memory_get_peak_usage() / 1024, 2));
        }
 
        return sprintf(
            $this->format, 
            $this->end_time - $this->start_time, 
            $this->init_memory, 
            $this->fini_memory, 
            $this->peak_memory
        );
    }
 
    private function microtimeFloat()
    {
        list($usec, $sec) = explode(' ', microtime());
        return ((float)$usec + (float)$sec);
    }
}



programming/php/etc/memoization.txt