Edited at

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;
}