LoginSignup
87

More than 5 years have passed since last update.

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

Last updated at Posted at 2013-08-22

鉄則: 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;
}

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
87