После некоторого времени использования 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
(с входами в массив) и т.д.