がるの健忘録

エンジニアでゲーマーで講師で占い師なおいちゃんのブログです。

ちょっとした小技……の背景

PHP

典型的には「(第一種)ホワイトリスト*1」の実装でありがちなのですが。

declare(strict_types=1);

$white_list = [
    'hoge',
    'foo',
    'bar',
    'baz',
    'qux',
];
//
$input = 'bar';
//
if (true === in_array($input, $white_list, true)) {
    echo "{$input} is in \n";
} else {
    echo "{$input} is NOT in \n";
}

こんな風に書く事が多いと思うんですよね、多分。

ただ、おいちゃんはこんな風に書きます。

declare(strict_types=1);

$white_list = [
    'hoge' => 1,
    'foo' => 1,
    'bar' => 1,
    'baz' => 1,
    'qux' => 1,
];
//
$input = 'bar';
//
if (true === isset($white_list[$input])) {
    echo "{$input} is in \n";
} else {
    echo "{$input} is NOT in \n";
}

valueは別に1でも''(空文字)でもtrueでもなんでもよいのですが(nullだけは嫌)。
あと、issetじゃなくてarray_key_existsでも、と思うのですがなんでだかarray_key_existsの綴りを指が覚えてくれないので、「値がnullじゃない事が確定している」状態だとisset使う事が多いです。

先に、テストコード。

declare(strict_types=1);

$s = 'a';
$awk = [];
for($i = 0; $i < 100000; ++$i) {
    $awk[] = $s;
    $s ++;
}
$t = microtime(true);
$hash_awk = array_flip($awk);
$t_end = microtime(true);
echo 'array_flip is ' , $t_end - $t , "\n";

//
$needle = $awk[ count($awk) - 1 ];

//
$t = microtime(true);
in_array($needle, $awk, true);
$t_end = microtime(true);
echo "in_\tis " , $t_end - $t , "\n";

//
$t = microtime(true);
isset($hash_awk[$needle]);
$t_end = microtime(true);
printf("isset\tis %.28f\n", $t_end - $t);

//
$t = microtime(true);
array_key_exists($needle, $hash_awk);
$t_end = microtime(true);
printf("array_\tis %.28f\n", $t_end - $t);

何回かお試し。

[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0030989646911621
in_ is 0.00078010559082031
isset is 0.0000009536743164062500000000
array_ is 0.0000009536743164062500000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0043699741363525
in_ is 0.00089287757873535
isset is 0.0000011920928955078125000000
array_ is 0.0000009536743164062500000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0034210681915283
in_ is 0.00078892707824707
isset is 0.0000009536743164062500000000
array_ is 0.0000009536743164062500000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0035109519958496
in_ is 0.00085806846618652
isset is 0.0000009536743164062500000000
array_ is 0.0000000000000000000000000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0038630962371826
in_ is 0.0010230541229248
isset is 0.0000009536743164062500000000
array_ is 0.0000009536743164062500000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0031359195709229
in_ is 0.00078296661376953
isset is 0.0000009536743164062500000000
array_ is 0.0000011920928955078125000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0031070709228516
in_ is 0.00080204010009766
isset is 0.0000009536743164062500000000
array_ is 0.0000000000000000000000000000
[gallu@ip-256.257.258.259 php]$ php t.php
array_flip is 0.0037379264831543
in_ is 0.0010411739349365
isset is 0.0000009536743164062500000000
array_ is 0.0000009536743164062500000000

issetとarray_key_existsは、なんかもはや「誤差レベル」のような雰囲気が(笑
in_arrayとは露骨に数値が違う、ってのだけ覚えておいていただければ。

ここで書きたいのは「検索するんなら、in_arrayよりisset(かarray_key_exists)のほうがよりよいのではないかしらん？」というお話でふ。

端的には「O(n)かO(1)か」の違いなのですが……厳密には「O(1)かどうかはkeyのコリジョンの具合にもよるんだけど、大分と1に近い」くらい。
in_arrayは線形探索だと思われるので、基本的に「配列を頭から舐めていって見つかったらそこで終了」となります。だからまぁ、テストでは最悪の形である「一番最後の要素」にしたのですが。
issetとarray_key_existsは「hash検索」なので。 https://gallu.hatenadiary.jp/entries/2006/09/30 とか https://gallu.hatenadiary.jp/entry/20060930/p2 とか見ていただくと(多少)細かく書いてありますが、元々が「速やかに検索するための方法」という側面でのhashでもあるので、要素がｎ個あっても、比較的高速に検索をする事が出来るようになるです。

これが「どっかから配列を取ってきて検索」の場合、「array_flipのコスト」と「検索のコスト」とのせめぎ合いになるので微妙な所ではあるのですが。
(第一種)ホワイトリストとかの場合は大体「コードのどこか(定数とか)」にあらかじめ配列を書いている、と思われるので。
そーゆー時は、普通の配列をin_arrayするよりもhash配列をissetなりarray_key_existsなりするほうが、速度的にも早いし、「検索」という理屈からもより「適切」なんじゃないかなぁ、とか思うわけなんですね。

なんていう小技を、なにげにちょいちょいと説明するケースがあったので、どこかで文章に残せたらなぁ、と思ったので残しておきます。

*1:許可されたモノが列挙されたリスト