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

346

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

Кендалл Хопкинс
источник
31
Совершенно не по теме, но 1 не является основным.
Джейсон Пунион
24
Массивы в PHP являются хеш-таблицами. Это должно сказать вам все, что вам нужно знать. Поиск ключа в хеш-таблице - это O (1). Поиск значения - это O (n), который нельзя разбить на несортированном множестве. Большинство функций, которые вам интересны, вероятно, O (n). Конечно, если вы действительно хотите знать, вы можете прочитать источник: cvs.php.net/viewvc.cgi/php-src/ext/standard/…
Фрэнк Фармер
11
Напомним, что самой быстрой реализацией того, что вы пытаетесь сделать, было бы (вместо использования NULL для ваших значений) использовать, trueа затем протестировать на наличие присутствия isset($large_prime_array[$number]). Если я правильно помню, это в сотни раз быстрее, чем in_arrayфункция.
Маттбаста
3
Система обозначений Big O не связана со скоростью. Речь идет об ограничении поведения.
Гамбо
3
@Kendall Я не сравниваю array_key_exists, я сравниваю с in_array. in_arrayвыполняет итерацию каждого элемента в массиве и сравнивает значение со стрелкой, которую вы ему передаете. Если вы переворачиваете значения в ключ (и просто заменяете каждое из значений фиктивным значением, например true, использование issetпроисходит во много раз быстрее. Это происходит потому, что ключи массива индексируются PHP (например, хеш-таблица). Следовательно, поиск таким образом, массив может значительно улучшить скорость.
Mattbasta

Ответы:

650

Поскольку кажется, что никто не делал этого раньше, я подумал, что было бы неплохо иметь его где-нибудь для справки. Я прошел через тестирование или скимминг кода, чтобы охарактеризовать 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намного быстрее чем in_arrayиarray_search
  2. +(union) немного быстрее чем array_merge(и выглядит лучше). Но это работает по-другому, так что имейте это в виду.
  3. shuffle находится на том же уровне Big-O, что и array_rand
  4. array_pop/ array_pushбыстрее чем array_shift/ array_unshiftиз-за штрафа за переиндексацию

Поиски :

array_key_existsO (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_size

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, для всех я)

Случайный :

shuffle На)

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

Очевидный Big-O :

array_fill На)

array_fill_keys На)

range На)

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

array_slice O (смещение + длина) или O (n), если длина = NULL

array_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)для большинства реалистичных значений).

график поиска в массиве php

$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 );
}
Кендалл Хопкинс
источник
5
@ Кендалл: Спасибо! Я немного почитал, и оказалось, что PHP использует «вложенные» хеш-таблицы для коллизий. То есть вместо структуры logn для коллизий он просто использует другую хеш-таблицу. И я понимаю, что практически говорящие хеш-таблицы PHP дают производительность O (1) или, по крайней мере, в среднем O (1) - для этого и нужны хеш-таблицы. Мне было просто любопытно, почему вы сказали, что они «действительно O (n)», а не «действительно O (logn)». Отличный пост, кстати!
Cam
10
Временные сложности должны быть включены в документацию! Выбор правильной функции может сэкономить вам столько времени или сказать, что вы не должны делать то, что планировали: p Спасибо за этот список!
Самуил
41
Я знаю, что это старый ... но что? Эта кривая вообще не показывает O (n), она показывает O (log n), en.wikipedia.org/wiki/Logarithm . Что также точно соответствует тому, что вы ожидаете от вложенных хэш-карт.
Андреас
5
Что такое Big-O unset на элементе массива?
Чандрю
12
В то время как хеш-таблицы действительно имеют сложность поиска O (n) в худшем случае, средний случай равен O (1), а частный случай, когда тестируется ваш тест, даже гарантированно O (1), так как это непрерывный, нумерованный индекс с нуля массив, который никогда не будет иметь хеш-коллизий. Причина, по которой вы все еще видите зависимость от размера массива, не имеет ничего общего с алгоритмической сложностью, а вызвана эффектами кеша процессора. Чем больше массив, тем больше вероятность того, что поиск с произвольным доступом приведет к пропаданию кэша (и кешу выше в иерархии).
NikiC
5

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

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

Дафан
источник
Это не совсем ответ. Как я уже говорил в этом вопросе, я уже пытался изучить исходный код PHP. Поскольку PHP реализован, он написан на C с использованием сложных макросов, которые иногда могут затруднить «просмотр» лежащего в основе большого O для функций.
Кендалл Хопкинс
@Kendall Я пропустил вашу ссылку на погружение в исходный код. Тем не менее, в моем ответе есть ответ: «Я не думаю, что есть конкретная исчерпывающая документация об алгоритмической сложности методов PHP». «Нет» - совершенно правильный ответ. (c:
Dathan
4

Вы почти всегда хотите использовать 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 секунд

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

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

ryeguy
источник
9
Это не верно. Я на 100% уверен, что array_key_exists не нужно перебирать каждый ключ. Если вы не верите, взгляните на ссылку ниже. Причина заключается в том, что намного быстрее, в том, что это языковая конструкция. Это означает, что нет необходимости выполнять вызов функции. Кроме того, я думаю, что это может быть кэширование поиска, из-за этого. Кроме того, это не ответ на вопрос! Я хотел бы список Big (O) для функций PHP (как говорится в вопросе). Ни одного эталона моих примеров. svn.php.net/repository/php/php-src/branches/PHP_5_3/ext/…
Кендалл Хопкинс
Если вы все еще не верите мне, я создаю небольшой тест, чтобы продемонстрировать это. pastebin.com/BdKpNvkE
Кендалл Хопкинс,
Что не так с вашим тестом производительности, так это то, что вы должны отключить xdebug. =)
Гильерме Бланко
3
Есть две критические причины, по которым вы хотите использовать isset вместо array_key_exists. Во-первых, isset - это языковая конструкция, снижающая стоимость вызова функции. Это сродни аргументу $arrray[] = $appendпротив array_push($array, $append). Во-вторых, array_key_exists также различает ненулевые и нулевые значения. For $a = array('fred' => null); array_key_exists('fred', $a)вернет true, пока isset($['fred'])вернет false. Этот дополнительный шаг нетривиален и значительно увеличит время выполнения.
orca
0

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

Джош Стерн
источник