Список Больших-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 намного быстрее, чем 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 (π 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 - размер второго array (т.е. array_first + array_second) - меньше накладных расходов, чем array_merge, поскольку не требуется перенумеровать

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

Случайно :

перемешать O (n)

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

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

array_fill O (n)

array_fill_keys O (n)

диапазон O (n)

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

слой_массива O (смещение + длина) или O (n), если длина = NULL

ключи_массивов O (n)

значения_массива 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 );
}