再帰関数の高速化

はじめまして。今井です。

スパイスワークスでは主にWebシステムの設計、PHPでのWebシステム開発をしています。

今回は再帰関数の高速化について書きたいと思います。

以前開発したシステムで、管理画面からディレクトリ情報とHTML情報をDBに登録し、一括でディレクトリとHTMLをツリー構造で書き出すという処理を開発しました。(Movable Typeようなシステム)

書き出し時の処理は
①：最上位ディレクトリに属するディレクトリをDBから探す
②：探したディレクトリを物理的に作成する
③：探したディレクトリ内にあるHTMLページをDBから探す
④：探したHTMLページを物理的に作成する
⑤：探したディレクトリ内にディレクトリがさらにあるかDBから探す
⑥：②～⑤を繰り返し
となっています。
イメージとしたらこのようなイメージです。

この②～⑤の処理を再帰関数を利用して行っています。
しかし、DBへのアクセスがオーバヘッドとなり書き出し処理が遅すぎる、または終らないという問題が発生しました。

このDBアクセス部分がボトルネックとなっていましたのでこの箇所の高速化を考え、再帰関数の処理を１つ１つ確認しました。
確認したところ、全く同じDBアクセスを行っている箇所が多く存在しました。

この結果を踏まえて、初回のDBアクセス時にメモリに結果を登録して２度目からはメモリから返すようにするという処理に変更しました。

変更前プログラム例

/**
 * 指定したカテゴリIDに所属するHTMLページ一覧を返す処理
 */
function getPagesByCategoryId($category_id){
    global $pdo;
    $sql = "SELECT * FROM `pages` WHERE `category_id` = :category_id";
    //↑本来はもっと複雑なSQLです
    $stmt = $pdo->prepare($sql);
    $stmt->execute(array('category_id'=>$category_id));
    $results = $stmt->fetchAll(PDO::FETCH_ASSOC);
    return $results;
}

変更後プログラム例

/**
 * 指定したカテゴリIDに所属するHTMLページ一覧を返す処理
 * 検索結果をstatic変数に登録して、２度目の検索はstatic変数から返すようにした
 */
function getPagesByCategoryId($category_id){
    static $results = null;
    global $pdo;
    if( null === $results ){
        //$results===nullの場合は初回処理なのでDBアクセスを行う
        //２回目以降のアクセスは$resultsにはデータが格納されているのでDBアクセス処理は行わない
        $sql = "SELECT * FROM `pages` WHERE `category_id` = :category_id";
        //↑本来はもっと複雑なSQLです
        $stmt = $pdo->prepare($sql);
        $stmt->execute(array('category_id' => $category_id));
        $results = $stmt->fetchAll(PDO::FETCH_ASSOC);
    }

    return $results;
}

この処理を行ったことで、冗長なDBアクセスが減り処理が終わるようになりました。

このような問題は調べたところ、ナップサック問題って言うんですね。
勉強になりました。