君たちはどう再帰するか

# 君も再帰しないか

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

よくあるお話です。

一般的には[array_walk_recursive](https://www.php.net/manual/ja/function.array-walk-recursive.php)やユーザ定義再帰関数を利用する所です。

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

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

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

## 処理対象のデータ

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

```php
<?php

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

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

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

```php
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`では構造を変更することはできません。

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

```php
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言語でいうポインタ**や**実メモリのアドレス**ではありません。
リファレンスは**シンボルテーブルのエイリアス**です。

```php
//==============================================
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
<?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
<?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](https://packagist.org/packages/tacddd/tacddd)をよろしくね。
なお、2月くらいまでにPHP8.3前提になる予定です。traitで定数使いたい。