Lista funkcji Big-O dla PHP

Po dłuższym użyciu PHP zauważyłem, że nie wszystkie wbudowane funkcje PHP działają tak szybko, jak się spodziewano. Rozważ te dwie możliwe implementacje funkcji, która sprawdza, czy liczba jest liczbą pierwszą, używając buforowanej tablicy liczb pierwszych.

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

Wynika to z faktu, że in_arrayjest realizowane za pomocą wyszukiwania liniowego O (n), które będzie liniowo zwalniać w miarę $prime_arraywzrostu. Gdy array_key_existsfunkcja jest zaimplementowana z wyszukiwaniem skrótów O (1), który nie zwolni, chyba że tablica skrótów zostanie bardzo zapełniona (w takim przypadku jest to tylko O ​​(n)).

Do tej pory musiałem odkrywać duże O poprzez próbę i błąd, a czasami od czasu do czasu patrzę na kod źródłowy . Teraz pytanie…

Czy istnieje lista teoretycznych (lub praktycznych) dużych czasów O dla wszystkich * wbudowanych funkcji PHP?

* lub przynajmniej te interesujące

Na przykład, bardzo trudno przewidzieć Big O funkcji wymienionych ponieważ ewentualna realizacja zależy od struktury danych brak podstawowych PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace(z wejściami tablicy), etc.

Ponieważ wydaje się, że nikt tego nie zrobił, zanim pomyślałem, że dobrze byłoby mieć go gdzieś w celach informacyjnych. Poszedłem i albo poprzez test porównawczy lub przeglądanie kodu, aby scharakteryzować array_*funkcje. Próbowałem umieścić bardziej interesujący Big-O u góry. Ta lista nie jest kompletna.

Uwaga: Wszystkie wartości Big-O zostały obliczone przy założeniu, że wyszukiwanie skrótem to O (1), nawet jeśli tak naprawdę to O (n). Współczynnik n jest tak niski, że obciążenie pamięci RAM związane z przechowywaniem wystarczająco dużej tablicy zraniłoby cię, zanim charakterystyka wyszukiwania Big-O zacznie działać. Na przykład różnica między połączeniem na numer array_key_existsN = 1 a N = 1 000 000 stanowi wzrost o ~ 50%.

Ciekawe punkty :

1. isset/ array_key_existsjest znacznie szybszy niż in_arrayiarray_search
2. +(union) jest nieco szybszy niż array_merge(i wygląda ładniej). Ale działa inaczej, więc miej to na uwadze.
3. shuffle jest na tym samym poziomie co Big-O array_rand
4. array_pop/ array_pushjest szybszy niż array_shift/ z array_unshiftpowodu kary ponownego indeksowania

Wyszukiwania :

array_key_existsO (n), ale naprawdę bliskie O (1) - wynika to z liniowego odpytywania w zderzeniach, ale ponieważ prawdopodobieństwo kolizji jest bardzo małe, współczynnik jest również bardzo mały. Uważam, że traktujesz skróty jako O (1), aby uzyskać bardziej realistyczne duże-O. Na przykład różnica między N = 1000 a N = 100000 jest tylko około 50% spowolnieniem.

isset( $array[$index] )O (n), ale bardzo zbliżone do O (1) - używa tego samego wyszukiwania co tablica_klucz_istnieje. Ponieważ jest to konstrukcja językowa, buforuje wyszukiwanie, jeśli klucz jest zakodowany na stałe, co powoduje przyspieszenie w przypadkach, gdy ten sam klucz jest używany wielokrotnie.

in_array O (n) - dzieje się tak, ponieważ przeszukuje liniowo tablicę, dopóki nie znajdzie wartości.

array_search O (n) - wykorzystuje tę samą funkcję podstawową, co tablica_w, ale zwraca wartość.

Funkcje kolejki :

array_push O (∑ var_i, dla wszystkich i)

array_pop O (1)

array_shift O (n) - musi ponownie indeksować wszystkie klucze

array_unshift O (n + ∑ var_i, dla wszystkich i) - musi ponownie indeksować wszystkie klucze

Przecięcie tablicy, łączenie, odejmowanie :

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

array_intersect jeśli przecięcie 100% do O (n ^ 2 * ∑param_i_count, dla wszystkich i), jeśli przecięcie 0% przecina O (n ^ 2)

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

array_diff O (π param_i_size, for all i) - To iloczyn wszystkich param_sizes

array_diff_key O (∑ param_i_size, dla i! = 1) - dzieje się tak, ponieważ nie musimy iterować po pierwszej tablicy.

array_merge O (∑ array_i, i! = 1) - nie trzeba iterować po pierwszej tablicy

+ (union) O (n), gdzie n jest rozmiarem drugiej tablicy (tj. array_first + array_second) - mniej narzutu niż array_merge, ponieważ nie musi on przenumerowywać

array_replace O (∑ array_i, dla wszystkich i)

Losowo :

shuffle Na)

array_rand O (n) - Wymaga sondowania liniowego.

Oczywiste Big-O :

array_fill Na)

array_fill_keys Na)

range Na)

array_splice O (przesunięcie + długość)

array_slice O (przesunięcie + długość) lub O (n), jeśli długość = NULL

array_keys Na)

array_values Na)

array_reverse Na)

array_pad O (rozmiar_padu)

array_flip Na)

array_sum Na)

array_product Na)

array_reduce Na)

array_filter Na)

array_map Na)

array_chunk Na)

array_combine Na)

Chciałbym podziękować Eureqa za ułatwienie znalezienia Big-O funkcji. To niesamowity darmowy program, który może znaleźć najlepszą funkcję dopasowania do dowolnych danych.

EDYTOWAĆ:

Dla tych, którzy wątpią w wyszukiwanie tablic PHP O(N), napisałem test porównawczy, aby to sprawdzić (wciąż są skuteczne 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 );
}

Wyjaśnienie opisanego przypadku jest takie, że tablice asocjacyjne są implementowane jako tabele skrótów - więc wyszukiwanie według klucza (i odpowiednio array_key_exists) to O (1). Jednak tablice nie są indeksowane według wartości, więc jedynym sposobem w ogólnym przypadku, aby dowiedzieć się, czy wartość istnieje w tablicy, jest wyszukiwanie liniowe. Nie ma w tym niespodzianki.

Nie wydaje mi się, żeby istniała konkretna kompleksowa dokumentacja złożoności algorytmicznej metod PHP. Jeśli jednak jest to wystarczająco duży problem, aby uzasadnić wysiłek, zawsze możesz przejrzeć kod źródłowy .

Prawie zawsze chcesz używać issetzamiast array_key_exists. Nie patrzę na elementy wewnętrzne, ale jestem prawie pewien, że array_key_existsjest to O (N), ponieważ iteruje każdy klucz w tablicy, podczas gdy issetpróbuje uzyskać dostęp do elementu przy użyciu tego samego algorytmu skrótu, który jest używany podczas uzyskiwania dostępu indeks tablicy. To powinno być O (1).

Jedną z rzeczy, na które trzeba uważać, jest:

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

Byłem ciekawy, więc porównałem różnicę:

<?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,133308959961 sekund
array_key_exists:2,33202195168 sekund

Oczywiście nie pokazuje to złożoności czasu, ale pokazuje porównanie dwóch funkcji między sobą.

Aby sprawdzić złożoność czasu, porównaj czas potrzebny do uruchomienia jednej z tych funkcji na pierwszym i ostatnim kluczu.

Gdyby ludzie mieli w praktyce kłopoty z kluczowymi kolizjami, wdrażaliby kontenery z wtórnym wyszukiwaniem skrótu lub zrównoważonym drzewem. Zrównoważone drzewo dałoby O (log n) najgorsze zachowanie i O (1) śr. case (sam skrót). Koszty ogólne nie są tego warte w najbardziej praktycznych aplikacjach pamięciowych, ale być może istnieją bazy danych, które domyślnie wdrażają tę formę strategii mieszanej.