[解決済み] Big-O for PHP関数一覧

質問

PHP をしばらく使ってみて、すべての PHP 組み込み関数が期待通りに高速に動作するわけではないことに気がつきました。キャッシュされた素数の配列を使用して、ある数が素数かどうかを調べる関数について、 以下の2つの実装が考えられるとします。

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

これは、以下の理由からです。 in_array は線形探索O(n)で実装されており、この線形探索は $prime_array が大きくなる。ここで array_key_exists このため、ハッシュテーブルが極端に肥大化しない限り（その場合、O(n)で済む）、速度が低下することはないでしょう。

これまでは試行錯誤でbig-Oを発見する必要があり、時には ソースコードを見る . では、質問です...

PHP の組み込み関数すべて* の理論的な (あるいは実際的な) 大 O 回数の一覧はありますか?

*または少なくとも興味深いもの

例えば、リストアップされた関数のうち、大きなOを予測するのは非常に困難です。なぜなら、実装の可能性が、PHPの未知のコアデータ構造に依存するからです。 array_merge , array_merge_recursive , array_reverse , array_intersect , array_combine , str_replace (配列入力の場合)など。

どのように解決するのですか？

誰もやったことがないようなので、どこかで参考にしたほうがいいと思いました。私は、ベンチマークやコードスキミングによって array_* という関数があります。より興味深いBig-Oをトップに近いところに置くようにしました。このリストは完全ではありません。

注：すべてのBig-Oは、ハッシュのルックアップがO(1)であると仮定して計算されているが、実際にはO(n)である。nの係数は非常に小さく、ルックアップBig-Oの特性が効果を発揮する前に、十分に大きな配列を格納するためのラムオーバーヘッドが痛手となります。たとえば array_key_exists N=1とN=1,000,000では、50%程度の時間増加です。

興味深い点 :

1. isset / array_key_exists よりもはるかに高速です。 in_array と array_search
2. + (ユニオン) の方が少し速いです。 array_merge (そして見た目もきれい)。しかし、動作は異なるので、その点は注意してください。
3. shuffle と同じBig-Oの階層にあります。 array_rand
4. array_pop / array_push よりも高速です。 array_shift / array_unshift 再インデックスペナルティにより

ルックアップ :

array_key_exists O(n)ですが、本当にO(1)に近いです。これは衝突の線形ポーリングのためですが、衝突の確率が非常に小さいため、係数も非常に小さくなります。ハッシュのルックアップをO(1)として扱うと、より現実的なBig-Oが得られると思います。例えば、N=1000とN=100000の違いは、約50％の速度低下だけです。

isset( $array[$index] ) O(n) でも O(1) に近い - array_key_exists と同じルックアップを使用します。これは言語処理なので、キーがハードコードされている場合はキャッシュされ、同じキーが繰り返し使用される場合に高速化されます。

in_array O(n) - これは、値を見つけるまで配列の線形探索を行うからです。

array_search O(n) - in_arrayと同じコア関数を使用しますが、値を返します。

キュー関数 :

array_push O(∑ var_i, すべてのiに対して)

array_pop O(1)

array_shift O(n) - すべてのキーのインデックスを再作成する必要があります。

array_unshift O(n + ∑ var_i, for all i) - すべてのキーのインデックスを再作成する必要があります。

配列の交差、結合、減算 :

array_intersect_key 交差点が100%の場合はO(Max(param_i_size)*∑param_i_count, for all i), 交差点が0%の場合は O(∑param_i_size, for all i) を実行する。

array_intersect 交差点が100%の場合はO(n^2*∑param_i_count, for all i)、交差点が0%の場合はO(n^2)

array_intersect_assoc 交差点が100%の場合はO(Max(param_i_size)*∑param_i_count, for all i), 交差点が0%の場合はO(∑param_i_size, for all i) を実行します。

array_diff O(π param_i_size, for all i) - これはすべてのparam_sizeの積です．

array_diff_key O(∑ param_i_size, for i != 1) - これは、最初の配列に対して反復処理を行う必要がないためです。

array_merge O( ∑ array_i, i != 1 ) - 最初の配列に対して反復処理を行う必要はありません。

+ (union) O(n), ただし n は 2 番目の配列のサイズ (array_first + array_second) - array_merge よりもオーバーヘッドが少なく、番号を変更する必要がありません。

array_replace O( ∑ array_i, for all i )

ランダム :

shuffle O(n)

array_rand O(n) - リニアポールが必要です。

明らかなBig-O :

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice O(オフセット＋長さ)

array_slice O(offset + length) または length = NULL の場合は O(n)

array_keys O(n)

array_values O(n)

array_reverse O(n)

array_pad O(pad_size)

array_flip O(n)

array_sum O(n)

array_product O(n)

array_reduce O(n)

array_filter O(n)

array_map O(n)

array_chunk O(n)

array_combine O(n)

感謝する ユーレカ 関数のBIG-Oを簡単に探せるようにしたこと。それは、驚くべき フリー は、任意のデータに対して最適な関数を求めることができるプログラムです。

EDIT

PHPの配列検索を疑っている人へ O(N) ということをテストするためのベンチマークを書きました。 O(1) を使用すると、ほとんどの現実的な値になります。）

<イグ

$tests = 1000000;
$max = 5000001;


for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}