Список функций Big-O для PHP

Поскольку это не похоже, что кто-то сделал это, прежде чем я подумал, что было бы неплохо иметь его для справки где-то. Я пошел, хотя и через бенчмарк или код-скимминг, чтобы охарактеризовать функции 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 намного быстрее, чем array_search и array_search
2. + (union) немного быстрее, чем 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), чтобы дать более реалистичный большой-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 (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_diff O (π param_i_size, для всех i) – это продукт всех param_sizes

array_diff_key O (Σ param_i_size, для i! = 1) – это потому, что нам не нужно перебирать первый массив.

array_merge O (Σ array_i, i! = 1) – не нужно перебирать первый массив

+ (объединение) O (n), где n – размер 2-го массива (т. е. array_first + array_second) – меньше накладных расходов, чем array_merge, поскольку он не имеет нумерации

array_replace O (Σ array_i, для всех i)

Случайный :

shuffle O (n)

array_rand O (n) – Требуется линейный опрос.

Очевидный Большой-O :

array_fill O (n)

array_fill_keys O (n)

range O (n)

array_splice O (смещение + длина)

array_slice O (смещение + длина) или O (n), если length = 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 функций. Это потрясающая бесплатная программа, которая может найти наилучшую подходящую функцию для произвольных данных.

РЕДАКТИРОВАТЬ:

Для тех, кто сомневается в том, что поиск в массиве 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 ); } 

Объяснение конкретного случая, которое вы конкретно описываете, это то, что ассоциативные массивы реализованы как хеш-таблицы, поэтому поиск по ключу (и, соответственно, array_key_exists ) равен O (1). Однако массивы не индексируются по значению, поэтому единственный способ в общем случае выяснить, существует ли значение в массиве, – это линейный поиск. Там нет ничего удивительного.

Я не думаю, что есть специальная всесторонняя документация об алгоритмической сложности методов PHP. Однако, если это достаточно большой интерес, чтобы оправдать усилия, вы всегда можете просмотреть исходный код .

Вы почти всегда хотите использовать isset вместо array_key_exists . Я не смотрю на внутренности, но я уверен, что array_key_exists – это O (N), потому что он выполняет итерацию по каждому ключу массива, а isset пытается получить доступ к элементу, используя тот же алгоритм хеширования, который используется, когда вы получаете доступ к индексу массива. Это должно быть O (1).

Один из них: «получить» – это:

 $search_array = array('first' => null, 'second' => 4); // returns false isset($search_array['first']); // returns true array_key_exists('first', $search_array); 

---

Мне было любопытно, поэтому я сравнил разницу:

 <?php $bigArray = range(1,100000); $iterations = 1000000; $start = microtime(true); while ($iterations--) { isset($bigArray[50000]); } echo 'is_set:', microtime(true) - $start, ' seconds', '<br>'; $iterations = 1000000; $start = microtime(true); while ($iterations--) { array_key_exists(50000, $bigArray); } echo 'array_key_exists:', microtime(true) - $start, ' seconds'; ?> 

is_set: 0.132308959961 секунд
array_key_exists: 2.33202195168 секунд

Конечно, это не показывает временную сложность, но показывает, как 2 функции сравниваются друг с другом.

Чтобы проверить временную сложность, сравните время, затрачиваемое на выполнение одной из этих функций на первом и последнем ключах.

Если бы люди столкнулись с трудностями на практике с ключевыми столкновениями, они реализовали бы контейнеры со вторичным поиском хэшей или сбалансированным деревом. Сбалансированное дерево дало бы поведение O (log n) худшего случая и O (1) avg. case (сам хэш). Накладные расходы не стоят в большинстве практических приложений с памятью, но, возможно, есть базы данных, которые реализуют эту форму смешанной стратегии в качестве случая по умолчанию.