LoginSignup
6
1
PHPAdvent Calendar 2023Day 19
@wakabadou(wakaba akira)inProject ICKX

君たちはどう再帰するか

Last updated at Posted at 2023-12-18

君も再帰しないか

多次元配列のさきっちょにいっちょフィルタをかましたい。

よくあるお話です。

一般的にはarray_walk_recursiveやユーザ定義再帰関数を利用する所です。

単純な処理だったらそれで問題ありません。
では階層の構造変更を伴うような処理だったらどうでしょうか？

例えば配列やエンティティオブジェクトをそれらが持つ特定の値に置き換えたいなど。

という事で今日は再帰を使って配列を書き換えていこうと思います。

処理対象のデータ

多次元配列の末尾に日付オブジェクトを複数持つものを対象とします。
実用で考えたい場合は、あに入っているものをエンティティや行データに置き換えてください。

<?php

$date = new DateTime('2024/12/19');

$data = [
    1 => [
        'a' => [
            'あ' => [
                $date,
            ],
            'い' => [
                $date,
                $date,
            ],
            'う' => [
                $date,
            ],
        ],
    ],
    2 => [
        'b' => [
            'あ' => [
                $date,
            ],
        ],
        'c' => [
            'い' => [
                $date,
            ],
            'う' => [
                $date,
                $date,
            ],
        ],
    ],
];

意図している処理結果は次の形です。

array(2) {
  [1]=>
  array(1) {
    ["a"]=>
    array(3) {
      ["あ"]=>
      string(10) "2024/12/19"
      ["い"]=>
      string(10) "2024/12/19"
      ["う"]=>
      string(10) "2024/12/19"
    }
  }
  [2]=>
  array(2) {
    ["b"]=>
    array(1) {
      ["あ"]=>
      string(10) "2024/12/19"
    }
    ["c"]=>
    array(2) {
      ["い"]=>
      string(10) "2024/12/19"
      ["う"]=>
      string(10) "2024/12/19"
    }
  }
}

再帰での処理：ユーザ定義再帰関数

現在対象としている配列に対してarray_walk_recursiveでは構造を変更することはできません。

一例目ではユーザ定義再帰関数を利用して再帰的に処理を行います。

function recursiveFunc(&$array)
{
    foreach ($array as &$value) {
        if (\is_array($value)) {
            if (!\is_bool($target = recursiveFunc($value))) {
                $value  = $target->format('Y/m/d');
            }
        } else {
            return $value;
        }
    }

    return false;
}

//==============================================
recursiveFunc($data);

この処理の肝は状態や処理対象を返り値で返しているところです。
ここで値を返すことで、末端の呼び出し元で明示的に処理を行えるようになっています。

再帰での処理：リファレンス

二例目ではリファレンスを利用した脅威のインライン展開を行います。

PHPにはリファレンスという機能があります。
これは同じ変数の内容を異なった名前でコールする機能です。

より詳解に言うとC言語でいうポインタや実メモリのアドレスではありません。
リファレンスはシンボルテーブルのエイリアスです。

//==============================================
foreach ($data as &$value) {
    $stack = [];

    foreach ($value as &$stack_value) {
        if (!\is_array($stack_value)) {
            $value  = $stack_value->format('Y/m/d');

            break;
        }

        $stack[]    = [&$value, &$stack_value];

        unset($stack_value);
    }

    unset($value);

    for (;0 < \count($stack);) {
        \end($stack);
        $last_key   = \key($stack);
        $parent     = &$stack[$last_key][0];
        $current    = &$stack[$last_key][1];

        unset($stack[$last_key]);

        if (\is_array($current)) {
            foreach ($current as &$current_child) {
                $stack[]    = [&$current, &$current_child];
            }
            continue;
        }

        $parent = $current->format('Y/m/d');

        unset($parent, $current, $map);
    }

    unset($value);
}

この処理の肝は配列の構造をスタックで持ち、その際に自身と親のリファレンスを持たせています。
これにより、子を処理するタイミングで親に付け替える事が可能となっています。

して、実用できるのは？

圧倒的にユーザ定義再帰関数なんだよなぁ…
PHP固有事情としてユーザ定義関数呼び出しとリファレンスの使用は実行効率の低下を招くのですが、上記のような使用例ではリファレンスはユーザ定義関数に敵わないようです。

PHPバージョン ユーザ定義再帰関数 リファレンス渡し
8.3.0 0.0365 0.0452
8.2.13 0.0229 0.0465
8.1.26 0.0235 0.0476
8.0.30 0.0338 0.0544
7.4.33 0.0212 0.0420
7.3.33 0.0417 0.0668
7.2.34 0.0276 0.0656
7.1.33 0.0215 0.0467
7.0.33 0.0223 0.0497
5.6.40 0.0624 0.1204
5.5.38 0.0685 0.1257
5.4.45 0.0916 0.1838 
<?php

$date = new DateTime('2024/12/19');

$data = [
    1 => [
        'a' => [
            'あ' => [
                $date,
            ],
            'い' => [
                $date,
                $date,
            ],
            'う' => [
                $date,
            ],
        ],
    ],
    2 => [
        'b' => [
            'あ' => [
                $date,
            ],
        ],
        'c' => [
            'い' => [
                $date,
            ],
            'う' => [
                $date,
                $date,
            ],
        ],
    ],
];

function recursiveFunc(&$array)
{
    foreach ($array as &$value) {
        if (\is_array($value)) {
            if (!\is_bool($target = recursiveFunc($value))) {
                $value  = $target->format('Y/m/d');
            }
        } else {
            return $value;
        }
    }

    return false;
}

$count = 10000;

//==============================================
$ret = [];
for ($i = 0;$i < $count;++$i) {
    $work1  = $data;

    $mts = microtime(true);
    recursiveFunc($work1);
    $ret[]  = microtime(true) - $mts;
}
echo substr(array_sum($ret) / count($ret) * $count, 0, 6), ':再帰関数', \PHP_EOL;

//==============================================
$ret = [];
for ($i = 0;$i < $count;++$i) {
    $work2  = $data;

    $mts = microtime(true);
    foreach ($work2 as &$value) {
        $stack = [];

        foreach ($value as &$stack_value) {
            if (!\is_array($stack_value)) {
                $value  = $stack_value->format('Y/m/d');

                break;
            }

            $stack[]    = [&$value, &$stack_value];

            unset($stack_value);
        }

        unset($value);

        for (;0 < \count($stack);) {
            \end($stack);
            $last_key   = \key($stack);
            $parent     = &$stack[$last_key][0];
            $current    = &$stack[$last_key][1];

            unset($stack[$last_key]);

            if (\is_array($current)) {
                foreach ($current as &$current_child) {
                    $stack[]    = [&$current, &$current_child];
                }
                continue;
            }

            $parent = $current->format('Y/m/d');

            unset($parent, $current, $map);
        }

        unset($value);
    }

    $ret[]  = microtime(true) - $mts;
}
echo substr(array_sum($ret) / count($ret) * $count, 0, 6), ':リファレンス渡し', \PHP_EOL;

おまけ

単純な変換な場合でも現代PHPではユーザ定義再帰関数が最速。

PHPバージョン array_walk_recursive ユーザ定義再帰関数 リファレンス渡し
8.3.0 0.0515 0.0250 0.0360
8.2.13 0.0300 0.0257 0.0358
8.1.26 0.0408 0.0276 0.0376
8.0.30 0.0250 0.0209 0.0311
7.4.33 0.0251 0.0230 0.0323
7.3.33 0.0281 0.0249 0.0347
7.2.34 0.0282 0.0258 0.0373
7.1.33 0.0519 0.0359 0.0390
7.0.33 0.0230 0.0241 0.0370
5.6.40 0.0463 0.0658 0.1006
5.5.38 0.0429 0.0606 0.0970 
<?php

$date = new DateTime('2024/12/19');

$data = [
    1 => [
        'a' => [
            'あ' => [
                $date,
            ],
            'い' => [
                $date,
                $date,
            ],
            'う' => [
                $date,
            ],
        ],
    ],
    2 => [
        'b' => [
            'あ' => [
                $date,
            ],
        ],
        'c' => [
            'い' => [
                $date,
            ],
            'う' => [
                $date,
                $date,
            ],
        ],
    ],
];

function recursiveFunc(&$array)
{
    foreach ($array as &$value) {
        if (is_array($value)) {
            recursiveFunc($value);
        } else {
            $value = $value->format('Y/m/d');
        }
    }
}

$count = 10000;

//==============================================
$ret = [];
for ($i = 0;$i < $count;++$i) {
    $work1  = $data;

    $mts = microtime(true);
    \array_walk_recursive($work1, function (&$data) {
        $data = $data->format('Y/m/d');
    });
    $ret[]  = microtime(true) - $mts;
}
echo substr(array_sum($ret) / count($ret) * $count, 0, 6), ':array_walk_recursive', \PHP_EOL;

//==============================================
$ret = [];
for ($i = 0;$i < $count;++$i) {
    $work2  = $data;

    $mts = microtime(true);
    recursiveFunc($work2);
    $ret[]  = microtime(true) - $mts;
}
echo substr(array_sum($ret) / count($ret) * $count, 0, 6), ':再帰関数', \PHP_EOL;

//==============================================
$ret = [];
for ($i = 0;$i < $count;++$i) {
    $work3  = $data;

    $mts = microtime(true);
    foreach ($work3 as &$value) {
        $stack = [];

        foreach ($value as &$stack_value) {
            $stack[] = &$stack_value;
        }

        for (;0 < \count($stack);) {
            \end($stack);
            $last_key   = \key($stack);
            $current    = &$stack[$last_key];
            unset($stack[$last_key]);

            if (\is_array($current)) {
                foreach ($current as &$stack_value) {
                    $stack[] = &$stack_value;
                }
            } else {
                $current    = $current->format('Y/m/d');
            }

            unset($current, $map);
        }

        unset($value);
    }

    $ret[]  = microtime(true) - $mts;
}
echo substr(array_sum($ret) / count($ret) * $count, 0, 6), ':リファレンス渡し', \PHP_EOL;

宣伝

上記のテクニックを利用した特に2回目以降のアクセスが爆速になるコレクションライブラリ、tacddd/tacdddをよろしくね。
なお、2月くらいまでにPHP8.3前提になる予定です。traitで定数使いたい。

6
1
0

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
Sign upLogin
6
1