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

Поскольку не похоже, что кто-то делал это раньше, я подумал, что было бы неплохо иметь это где-нибудь для справки. Я пошел, хотя и либо через бенчмарк, либо через просмотр кода, чтобы охарактеризовать функции array_*. Я попытался поместить более интересную букву "О" ближе к вершине. Этот список неполон.

Примечание: Все Большие O, где вычисляется при условии, что поиск хэша равен O(1), хотя на самом деле это O(n). Коэффициент n настолько мал, что затраты оперативной памяти на хранение большого достаточное количество массивов повредит вам, прежде чем характеристики lookup Big-O начнут действовать. Например, разница между вызовом array_key_exists при N=1 и N=1 000 000 составляет ~50% увеличения времени.

Интересные Моменты:

1. isset/array_key_exists намного быстрее, чем in_array и array_search
2. +(объединение) немного быстрее, чем 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(π парам_и_размер, для всех i) - Это произведение всех парам_размеров

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( ∑ массив_i, для всех i)

Случайный:

shuffle O(n)

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

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

array_fill O(n)

array_fill_keys O(n)

range O(n)

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

array_slice O(смещение + длина) или O(n), если длина = НОЛЬ

array_keys O(n)

array_values O(n)

array_reverse O(n)

array_pad O(размер подложки)

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

ИЗМЕНИТЬ:

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