Lista Big-O dla funkcji PHP

Ponieważ wydaje się, że nikt nie robił tego wcześniej, pomyślałem, że dobrze byłoby mieć to gdzieś w celach informacyjnych. Poszedłem jednak i albo poprzez benchmark, albo code-skimming, aby scharakteryzować funkcje array_*. Próbowałem umieścić bardziej interesujący Big-O blisko góry. Ta lista nie jest kompletna.

Uwaga: Wszystkie Duże-o, gdzie obliczane przy założeniu, że szukanie hash jest O(1), nawet jeśli jest naprawdę O (n). Współczynnik n jest tak niski, że napowietrzność pamięci RAM jest wystarczająco duża array zaszkodziłoby, zanim właściwości wyszukiwania Big-O zaczną działać. Na przykład różnica między wywołaniem {[2] } przy N=1 i n = 1,000,000 wynosi ~50% wzrost czasu.

Ciekawe Punkty :

1. isset/array_key_exists jest znacznie szybszy niż in_array i array_search
2. + (union) jest nieco szybszy niż array_merge (i wygląda ładniej). Ale to działa inaczej, więc miej to na uwadze.
3. shuffle jest na tym samym poziomie Big-O co array_rand
4. array_pop/array_push jest szybszy niż array_shift/array_unshift ze względu na karę ponownego indeksowania

Lookups :

array_key_exists O (n), ale naprawdę blisko O(1) - wynika to z liniowego sondowania w kolizjach, ale ponieważ szansa na kolizje jest bardzo mała, współczynnik jest również bardzo mały. Uważam, że traktujesz szukanie hash jako O (1), aby dać bardziej realistyczne big-O. na przykład różnica między N=1000 i N=100000 jest tylko o 50% spowolniona.

isset( $array[$index] ) O (n) ale bardzo blisko O(1) - używa tego samego wyszukiwania co array_key_exists. Ponieważ jest to konstrukcja językowa, będzie buforować wyszukiwanie, jeśli klucz jest zakodowany na twardo, co spowoduje przyspieszenie w przypadkach, gdy ten sam klucz jest używany wielokrotnie.

in_array O (n) - dzieje się tak dlatego, że dokonuje przeszukiwania liniowego tablicy, dopóki nie znajdzie wartości.

array_search O ( n) - używa tej samej podstawowej funkcji co in_array, ale zwraca wartość.

Funkcje kolejki :

array_push O (var var_i, dla wszystkich i)

array_pop O (1)

array_shift O (n) - musi reindeksować wszystkie klucze

array_unshift O (n + var var_i, for all i) - musi reindexować wszystkie klucze

Array Intersection, Union, Subtraction :

array_intersect_key jeśli przecięcie 100% do O(Max(param_i_size)*param param_i_count, dla wszystkich i), jeśli przecięcie 0% intersect O (∑param_i_size, dla wszystkich i)

array_intersect if przecięcie 100% do O(n^2*∑param_i_count, for all I), if przecięcie 0% intersect O (n^2)

array_intersect_assoc jeśli przecięcie 100% do O(Max(param_i_size)*param param_i_count, dla wszystkich i), jeśli przecięcie 0% intersect O (∑param_i_size, dla wszystkich i)

array_diff o (π param_i_size, dla wszystkich i) - to iloczyn wszystkich param_sizes

array_diff_key O (∑param_i_size, for i != 1) - dzieje się tak dlatego, że nie musimy iteracji nad pierwszą tablicą.

array_merge O (arra array_i, i != 1) - nie wymaga iteracji nad pierwszą tablicą

+ (union) O (n), gdzie n jest wielkością array_first + array_second) - mniej narzutu niż array_merge, ponieważ nie musi zmieniać numeracji

array_replace O (arra array_i, for all I)

Losowe:

shuffle O (n)

array_rand O (n) - wymaga liniowej ankiety.

:

array_fill O (n)

array_fill_keys O (n)

range O (n)

array_splice O (offset + Długość)

array_slice O (offset + długość) lub O (n) jeżeli długość = NULL

array_keys O (n)

array_values 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)

Chciałbym podziękować Eureqa za ułatwienie znalezienia Big-O funkcji. Jest to niesamowity darmowy program, który może znaleźć najlepsze dopasowanie funkcja dla dowolnych danych.

EDIT:

Dla tych, którzy wątpią, że PHP array lookups są O(N), napisałem benchmark, aby to przetestować(nadal są one skutecznie O(1) dla najbardziej realistycznych wartości).

$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 );
}