PHPで多次元連想配列を高速に検索する

はじめに

データベースから取得した多次元連想配列に対して検索を行うとき、どのように処理するのが一番いいのか分からなかったので調べてみました。
ざっくり調べた限りだとarray_search + array_columnで実装するのが多かったんですが、計算量が O(n^2) になってしまうのでパフォーマンス的にどうなんだろうと思い、実際に測定してみました。

今回は以下の2パターンについて検証を行います。

1. array_search + array_column で検索する
2. 検索したいキーで連想配列を作り直してから検索する

バージョン

PHP 7.2

検証コード

1. array_search + array_column で検索する

上述の通り計算量がO(n^2)になってしまうのでパフォーマンス的に不安がありますが、比較的シンプルに記述することができます。

$size = 100;

// 検証用の配列を作成する
$array = [];
foreach(range(0, $size) as $i) {
    $part['hoge'] = 'key' . $i;
    foreach(range(1, 9) as $j) {
        $part[$j] = 'fuga';
    }
    $array[] = $part;
}

$time_start = microtime(true);

foreach (range(0, $size) as $i) {
    array_search('key' . $i, array_column($array, 'hoge'));
}

$time = microtime(true) - $time_start;
print($time * 1000 . 'ms');

2. 検索したいキーで連想配列を作り直してから検索する

こちらは計算量がO(n)になるのでパフォーマンスが良くなると考えられますが、配列を作り直す処理が必要なのと検索したいキーが重複している場合に使えないというデメリットがあります。

$size = 100;

// 検証用の配列を作成する
$array = [];
foreach(range(0, $size) as $i) {
    $part['hoge'] = 'key' . $i;
    foreach(range(1, 9) as $j) {
        $part[$j] = 'fuga';
    }
    $array[] = $part;
}

$time_start = microtime(true);

// 検索したいキーで配列を再生成する
$mapping = [];
foreach($array as $a) {
    $mapping[$a['hoge']] = $a;
}

foreach (range(0, $size) as $i) {
    $mapping['key' . $i];
}

$time = microtime(true) - $time_start;
print($time * 1000 . 'ms');

測定結果

上のコードの$sizeを変えながら実行速度を測定しました。

$size	100	1,000	10,000
1. array_search + array_column で検索する	0.14ms	16ms	1886ms
2. 検索したいキーで連想配列を作り直してから検索する	0.02ms	0.19ms	4.54ms

結論

• 1,000レコード程度までならどちらを使ってもパフォーマンスに大きな差はない
• 10,000レコード以上なら速度がかなり低下するので、検索したいキーで連想配列を作り直して検索した方が良さそう