PHP
再帰

PHPにおける再帰処理の高速化

More than 3 years have passed since last update.

鉄則: C言語レベルで再帰処理させろ!

PHP言語レベルで再帰させるのとC言語レベルで再帰させるのでは、処理速度に雲泥の差がある。
圧倒的にC言語レベルの方が高速。

よく使う関数・クラス

以下の関数やクラスを使えば、配列の要素を辿っていく再帰処理であっても、
葉ノードだけを (PHP言語レベルでは) 単一のループ で処理させることが可能。

array_walk_recursive()

http://php.net/manual/ja/function.array-walk-recursive.php
最速。

RecursiveIteratorIterator

http://www.php.net/manual/ja/recursiveiteratoriterator.construct.php
array_walk_recursive()より速度的には僅かに劣るが、こちらにしか出来ないこともある。

  • RecursiveIteratorIterator::LEAVES_ONLY
    デフォルト。イテレーションで葉ノードだけを取り上げます。
  • RecursiveIteratorIterator::SELF_FIRST
    イテレーションで葉と親を (親から先に) 取り上げます。
  • RecursiveIteratorIterator::CHILD_FIRST
    イテレーションで葉と親を (葉から先に) 取り上げます。

このようにモードを切り替えることが可能。
更に、 RecursiveArrayIterator 以外にも

  • RecursiveDirectoryIterator
  • RecursiveCachingIterator
  • RecursiveCallbackFilterIterator
  • RecursiveFilterIterator
  • RecursiveRegexIterator
  • RecursiveTreeIterator

と併せて使うことが可能。

応用例

array_map_recursive()

array_map()みたいに複数の配列引数は受け付けないけど。

PHP5.3の場合はcallableタイプヒンティング消してください
<?php
function array_map_recursive(callable $func, array $arr) {
    array_walk_recursive($arr, function(&$v) use ($func) {
        $v = $func($v);
    });
    return $arr;
}

追加記事: array_map_recursiveはPHPに標準実装されていた! もご覧ください。

array_flatten()

葉要素だけを取り出して1次元の配列にする。

<?php
function array_flatten(array $arr) {
    $ret = array();
    array_walk_recursive($arr, function($v) use (&$ret) {
        $ret[] = $v;
    });
    return $ret;
}

dirsize()

指定したディレクトリのサイズを取得する。

<?php
function dirsize($dir) {
    $sum = 0;
    foreach (new RecursiveIteratorIterator(
        new RecursiveDirectoryIterator(
            $dir,
            FileSystemIterator::SKIP_DOTS
        )
    ) as $item) {
        if ($item->isFile()) {
            $sum += $item->getSize();
        }
    }
    return $sum;
}

scan_image()

指定したディレクトリ下にあるGIF/JPEG/PNG画像へのパスを再帰的に取得する。

<?php
function scan_image($dir) {
    $ret = array();
    foreach (new RecursiveIteratorIterator(
        new RecursiveDirectoryIterator(
            $dir,
            FileSystemIterator::SKIP_DOTS
        )
    ) as $item) {
        switch (true) {
            case !$item->isFile():
            case ($info = @getimagesize($path = $item->getPathname())) === false:
                break;
            case $info['mime'] === 'image/gif':
            case $info['mime'] === 'image/jpeg':
            case $info['mime'] === 'image/png':
                $ret[] = $path;
        }
    }
    return $ret;
}