Так как, похоже, никто не делал этого прежде, чем я подумал, что было бы неплохо иметь его где-нибудь для справки. Я использовал тесты или скимминг кода, чтобы охарактеризовать функции array_*. Я пытался поставить более интересный Big-O в верхней части. Этот список не полный.
Примечание. Все значения Big-O, рассчитанные в предположении хэш-поиска, равны O (1), хотя в действительности это O (n). Коэффициент n настолько низок, что накладные расходы на хранение достаточно большого массива могут повредить вам, прежде чем характеристики поиска Big-O начнут действовать. Например, разница между вызовом на array_key_exists при N = 1 и N = 1 000 000 составляет ~ 50% увеличения времени.
Интересные моменты :
isset / array_key_exists намного быстрее, чем in_array и array_search+ (union) немного быстрее, чем array_merge (и выглядит лучше). Но это работает по-другому, так что имейте это в виду. shuffle находится на том же уровне Big-O, что и array_randarray_pop / array_push быстрее array_shift / array_unshift из-за штрафа за переиндексацию
Lookups
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, для всех i) - необходимо переиндексировать все ключи
Пересечение массивов, объединение, вычитание :
array_intersect_key если пересечение 100% сделать O (Макс (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 (Макс (param_i_size) * ∑param_i_count, для всех i), если пересечение 0% пересечь O (∑param_i_size, для всех i)
array_diff O (π param_i_size, для всех i) - это произведение всех param_sizes
array_diff_key O (∑ param_i_size, для 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, для всех i)
Random
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 (смещение + длина) или O (n), если длина = NULL
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)
Я хотел бы поблагодарить Eureqa за упрощение поиска 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 );
}