計算量を常に意識しよう

計算量を常に意識しよう

  • こういうコードを見るとパフォーマンスが劣化しないか気になります
foreach ($foo => $bar) {
    if (!in_array($bar, $some_list)) {
        continue;
    }

    // 何かの処理
}

何がよくないのか？

  • in_array は毎回、配列内を検索します
  • 今回はPHPのコードを追ってみましょう
  • まずはコードの定義された箇所を特定します
$ grep -r in_array php-src | grep PHP_FUNCTION
php-src/ext/standard/array.c:PHP_FUNCTION(in_array)
php-src/ext/standard/php_array.h:PHP_FUNCTION(in_array);
  • ext/standard/array.cを見ればよいことがわかります
PHP_FUNCTION(in_array)
{
    php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
}
  • php_search_arrayの定義がどこにあるか調べます
$ grep -lr php_search_array php-src
php-src/ext/standard/array.c
  • 関数を確認するとstrictモード|数値|文字列|それ以外で処理が分かれています
  • 常にZEND_HASH_FOREACH_KEY_VALが呼ばれることがわかります
  • 下記のコードは個別の内容を折り畳んだもの
    if (strict) {
        ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {...} ZEND_HASH_FOREACH_END();
    } else {
        if (Z_TYPE_P(value) == IS_LONG) {
            ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {...} ZEND_HASH_FOREACH_END();
        } else if (Z_TYPE_P(value) == IS_STRING) {
            ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {...} ZEND_HASH_FOREACH_END();
        } else {
            ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {...} ZEND_HASH_FOREACH_END();
        }
    }
  • 次はZEND_HASH_FOREACH_KEY_VALを調べれば良いことがわかります
  • php-src/Zend/zend_hash.cがあるのでそちらを読みましょう
$ grep -wr ZEND_HASH_FOREACH_KEY_VAL php-src | grep define
php-src/Zend/zend_hash.h:#define ZEND_HASH_FOREACH_KEY_VAL(ht, _h, _key, _val) \
  • 内部で与えられた配列の要素が以下の条件を満たすまで無限ループを行っていることがわかります
  • 目的の値が見つかる
  • 配列の要素が見つかった
convert:
    {
        HashTable *new_ht = zend_new_array(zend_hash_num_elements(ht));

        ZEND_HASH_FOREACH_KEY_VAL(ht, num_key, str_key, zv) {
            do {
                if (Z_OPT_REFCOUNTED_P(zv)) {
                    if (Z_ISREF_P(zv) && Z_REFCOUNT_P(zv) == 1) {
                        zv = Z_REFVAL_P(zv);
                        if (!Z_OPT_REFCOUNTED_P(zv)) {
                            break;
                        }
                    }
                    Z_ADDREF_P(zv);
                }
            } while (0);
            /* Again, thank ArrayObject for `!str_key ||`. */
            if (!str_key || ZEND_HANDLE_NUMERIC(str_key, num_key)) {
                zend_hash_index_update(new_ht, num_key, zv);
            } else {
                zend_hash_update(new_ht, str_key, zv);
            }
        } ZEND_HASH_FOREACH_END();

        return new_ht;
    }
}
  • 上記からわかることは2つあります
  • PHPのin_arrayは毎回ループを行う
  • 配列後方に目的の値があるほど探索が遅くなる

どうすればよかったのか？

  • 最初にarray_flipした配列を用意してissetを使いましょう
$flipped = array_flip($some_list);
foreach ($foo => $bar) {
    if (!isset($flipped[$bar])) {
        continue;
    }

    // 何かの処理
}

array_flipした内容をissetで見る方が本当に高速か検証する

<?php
require_once '.composer/vendor/devster/ubench/src/Ubench.php';

$list = range(1, 10000);

$b = new Ubench();
$b->start();
foreach (range(1, 10000) as $i) {
    in_array(1, $list);
}
$b->end();
echo 'in_array_1st: ' . $b->getTime(), "\n";

$b->start();
foreach (range(1, 10000) as $j) {
    in_array(10000, $list);
}
$b->end();
echo 'in_array_last: ' . $b->getTime(), "\n";

$b->start();
$flipped = array_flip($list);
foreach (range(1, 10000) as $l) {
    isset($flipped[1]);
}
$b->end();
echo 'isset_1st: : ' . $b->getTime(), "\n";

$b->start();
$flipped = array_flip($list);
foreach (range(1, 10000) as $m) {
    isset($flipped[10000]);
}
$b->end();
echo 'isset_last: ' . $b->getTime(), "\n";
  • ベンチ結果はこの様になりました
  • 期待した通り、末尾に目的の値がある場合に劣化します
  • 逆にissetの場合は劣化することもなく、先頭要素を探すのに比べても若干高速ですね
$ php test.php
in_array_1st: 6ms
in_array_last: 1.680s
isset_1st: : 5ms
isset_last: 5ms

伝えたいこと

  • (特に組込)関数が何をしているのかを理解して使う様にしましょう
  • 内部でループが行われている場合は、いかにループを少なくするかを検討しましょう