После некоторого времени использования PHP я заметил, что не все встроенные функции PHP работают так быстро, как ожидалось. Рассмотрим эти две возможные реализации функции, которая находит, является ли число простым, используя кэшированный массив простых чисел.
//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)).
До сих пор мне приходилось открывать big-O методом проб и ошибок, а иногда и просматривать исходный код . Теперь к вопросу ...
Есть ли список теоретических (или практических) больших значений O для всех * встроенных функций PHP?
* или хотя бы интересные
Например, я считаю , это очень трудно предсказать , большой O функций , перечисленных , так как возможная реализация зависит от неизвестных основных структур данных PHP: array_merge
, array_merge_recursive
, array_reverse
, array_intersect
, array_combine
, str_replace
(с входами массива), и т.д.
true
а затем протестировать на наличие присутствияisset($large_prime_array[$number])
. Если я правильно помню, это в сотни раз быстрее, чемin_array
функция.array_key_exists
, я сравниваю сin_array
.in_array
выполняет итерацию каждого элемента в массиве и сравнивает значение со стрелкой, которую вы ему передаете. Если вы переворачиваете значения в ключ (и просто заменяете каждое из значений фиктивным значением, напримерtrue
, использованиеisset
происходит во много раз быстрее. Это происходит потому, что ключи массива индексируются PHP (например, хеш-таблица). Следовательно, поиск таким образом, массив может значительно улучшить скорость.Ответы:
Поскольку кажется, что никто не делал этого раньше, я подумал, что было бы неплохо иметь его где-нибудь для справки. Я прошел через тестирование или скимминг кода, чтобы охарактеризовать
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_rand
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, для всех я)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, для всех я), если пересечение 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, для всех я) - это произведение всех param_sizearray_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, для всех я)Случайный :
shuffle
На)array_rand
O (n) - Требуется линейный опрос.Очевидный Big-O :
array_fill
На)array_fill_keys
На)range
На)array_splice
O (смещение + длина)array_slice
O (смещение + длина) или O (n), если длина = NULLarray_keys
На)array_values
На)array_reverse
На)array_pad
O (pad_size)array_flip
На)array_sum
На)array_product
На)array_reduce
На)array_filter
На)array_map
На)array_chunk
На)array_combine
На)Я хотел бы поблагодарить Eureqa за то, что он упростил поиск Big-O функций. Это удивительная бесплатная программа, которая может найти наиболее подходящую функцию для произвольных данных.
РЕДАКТИРОВАТЬ:
Для тех, кто сомневается
O(N)
в правильности поиска в массивах PHP , я написал тест для проверки этого (они все еще эффективныO(1)
для большинства реалистичных значений).источник
Объяснение для случая, который вы конкретно описываете, заключается в том, что ассоциативные массивы реализованы в виде хеш-таблиц, поэтому поиск по ключу (и, соответственно,
array_key_exists
) - это O (1). Однако массивы не индексируются по значению, поэтому единственный способ в общем случае определить, существует ли значение в массиве, - это линейный поиск. Там нет ничего удивительного.Я не думаю, что есть конкретная всесторонняя документация алгоритмической сложности методов PHP. Однако, если это достаточно большая проблема, чтобы оправдать усилия, вы всегда можете просмотреть исходный код .
источник
Вы почти всегда хотите использовать
isset
вместоarray_key_exists
. Я не смотрю на внутренние компоненты, но я почти уверен, чтоarray_key_exists
это O (N), потому что он перебирает каждый ключ массива,isset
пытаясь получить доступ к элементу, используя тот же алгоритм хеширования, который используется при доступе индекс массива. Это должно быть O (1).Вот одна «ошибка», на которую стоит обратить внимание:
Мне было любопытно, поэтому я оценил разницу:
is_set:
0,132308959961 секундarray_key_exists:
2,33202195168 секундКонечно, это не показывает сложность времени, но показывает, как эти две функции сравниваются друг с другом.
Чтобы проверить сложность времени, сравните количество времени, необходимое для запуска одной из этих функций на первом и последнем ключах.
источник
$arrray[] = $append
противarray_push($array, $append)
. Во-вторых, array_key_exists также различает ненулевые и нулевые значения. For$a = array('fred' => null);
array_key_exists('fred', $a)
вернет true, покаisset($['fred'])
вернет false. Этот дополнительный шаг нетривиален и значительно увеличит время выполнения.Если бы на практике люди сталкивались с проблемами из-за столкновений ключей, они реализовывали бы контейнеры со вторым поиском хеша или сбалансированным деревом. Сбалансированное дерево даст O (log n) в худшем случае и O (1) avg. case (сам хеш). В большинстве практических приложений с памятью эти издержки не стоят того, но, возможно, существуют базы данных, которые реализуют эту форму смешанной стратегии в качестве варианта по умолчанию.
источник