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(1) で実装されており、ハッシュ テーブルが極端に多くならない限り速度は低下しません (その場合、速度は O(n) のみになります)。
これまで私は試行錯誤しながらビッグオーを発見し、時にはソースコードを見るさて、質問です...
すべての組み込み PHP 関数の理論上の (または実際の) big O 時間のリストはありますか?
*少なくとも興味深いもの
array_mergeたとえば、可能な実装は PHP の未知のコアデータ構造 ( 、、、、(配列入力付き) など)に依存するため、リストさarray_merge_recursiveれている関数の大きなO を予測するのは非常に困難ですarray_reverse。array_intersectarray_combinestr_replace
ベストアンサー1
これまで誰もこれをやったことがないようなので、どこかに参考として置いておくのがいいだろうと思いました。ベンチマークやコードスキミングで関数の特徴を調べましたarray_*。より興味深い Big-O を一番上に置くようにしました。このリストは完全ではありません。
注: すべての Big-O は、ハッシュ検索が O(1) であると仮定して計算されていますが、実際には O(n) です。n の係数は非常に低いため、検索 Big-O の特性が効果を発揮し始める前に、十分に大きな配列を格納するための RAM オーバーヘッドが問題になります。たとえば、array_key_existsN=1 での呼び出しと N=1,000,000 での呼び出しの違いは、約 50% の時間増加です。
興味深い点:
isset/ は、およびarray_key_existsよりもはるかに高速ですin_arrayarray_search+(union) は () よりも少し高速でarray_merge、見た目もきれいです。ただし、動作が異なるので、その点に注意してください。shuffle同じBig-O層にあるarray_randarray_pop/は再インデックスのペナルティにより/array_pushより高速ですarray_shiftarray_unshift
検索:
array_key_existsO(n) ですが、O(1) に非常に近いです。これは衝突時の線形ポーリングによるものですが、衝突の可能性は非常に小さいため、係数も非常に小さくなります。より現実的な big-O を得るには、ハッシュ検索を O(1) として扱うのがよいと思います。たとえば、N=1000 と N=100000 の違いは、速度低下が約 50% だけです。
isset( $array[$index] )O(n) ですが、O(1) に非常に近いです。array_key_exists と同じ検索を使用します。これは言語構造であるため、キーがハードコードされている場合は検索をキャッシュし、同じキーが繰り返し使用される場合に速度が向上します。
in_arrayO(n) - これは、値が見つかるまで配列全体を線形検索するためです。
array_searchO(n) - in_array と同じコア関数を使用しますが、値を返します。
キュー機能:
array_pushO(∑ var_i、すべてのiに対して)
array_popオー(1)
array_shiftO(n) - すべてのキーを再インデックスする必要がある
array_unshiftO(n + ∑ var_i, すべてのiに対して) - すべてのキーを再インデックスする必要がある
配列の交差、結合、減算:
array_intersect_key交差が 100% の場合は O(Max(param_i_size)*∑param_i_count, すべての i について) を実行し、交差が 0% の場合は交差 O(∑param_i_size, すべての i について) を実行します。
array_intersect交差が 100% の場合、O(n^2*∑param_i_count、すべての i について) を実行し、交差が 0% の場合、交差は O(n^2) になります。
array_intersect_assoc交差が 100% の場合は O(Max(param_i_size)*∑param_i_count, すべての i について) を実行し、交差が 0% の場合は交差 O(∑param_i_size, すべての i について) を実行します。
array_diffO(π param_i_size、すべてのiについて) - これはすべてのparam_sizesの積です
array_diff_keyO(∑ param_i_size, for i != 1) - これは、最初の配列を反復処理する必要がないためです。
array_mergeO( ∑ array_i, i != 1 ) - 最初の配列を反復処理する必要がない
+(union) O(n)、ここでnは2番目の配列のサイズ(つまりarray_first + array_second)です。番号を再割り当てする必要がないため、array_mergeよりもオーバーヘッドが少なくなります。
array_replaceO( ∑ array_i、すべてのiに対して )
ランダム:
shuffleの上）
array_randO(n) - 線形ポーリングが必要です。
明らかなビッグオー：
array_fillの上）
array_fill_keysの上）
rangeの上）
array_spliceO(オフセット + 長さ)
array_sliceO(オフセット + 長さ)、または長さ = NULL の場合は O(n)
array_keysの上）
array_valuesの上）
array_reverseの上）
array_padO(パッドサイズ)
array_flipの上）
array_sumの上）
array_productの上）
array_reduceの上）
array_filterの上）
array_mapの上）
array_chunkの上）
array_combineの上）
感謝したいユーレカ関数の Big-O を簡単に見つけられるようにします。任意のデータに最適な関数を見つけることができる素晴らしい無料プログラムです。
編集：
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 );
}