Lista funkcji Big-O dla PHP

346

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.

Kendall Hopkins
źródło
31
Zupełnie nie na temat, ale 1 nie jest liczbą pierwszą.
Jason Punyon
24
Tablice w PHP to tabele skrótów. To powinno ci powiedzieć wszystko, co musisz wiedzieć. Wyszukiwanie klucza w tablicy mieszającej to O (1). Wyszukiwanie wartości to O (n) - której nie można pokonać w nieposortowanym zestawie. Większość funkcji, które Cię interesują, to prawdopodobnie O (n). Oczywiście, jeśli naprawdę chcesz wiedzieć, możesz przeczytać źródło: cvs.php.net/viewvc.cgi/php-src/ext/standard/…
Frank Farmer
11
Dla przypomnienia, najszybszą implementacją tego, co próbujesz zrobić, byłoby (zamiast użycia NULL dla swoich wartości) użycie, truea następnie przetestowanie obecności za pomocą isset($large_prime_array[$number]). Jeśli dobrze pamiętam, jest to setki razy szybsze niż in_arrayfunkcja.
mattbasta
3
Notacja Big O nie dotyczy prędkości. Chodzi o ograniczenie zachowania.
Gumbo,
3
@Kendall Nie porównuję array_key_exists, porównuję in_array. in_arrayiteruje każdy element w tablicy i porównuje wartość z igłą, którą mu przekazujesz. Jeśli przerzucisz wartości na klucz (i po prostu zastąpisz każdą z wartościami fikcyjnymi, np. trueUżycie issetjest wiele razy szybsze. Jest tak, ponieważ klucze tablicy są indeksowane przez PHP (jak tablica haszująca). W rezultacie wyszukiwanie tablica w ten sposób może znacząco poprawić prędkość
mattbasta

Odpowiedzi:

650

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

Wykres wyszukiwania tablicy 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 );
}
Kendall Hopkins
źródło
5
@Kendall: Dzięki! Przeczytałem trochę i okazuje się, że PHP używa „zagnieżdżonych” tablic mieszających do kolizji. Oznacza to, że zamiast struktury logowania w przypadku kolizji po prostu używa innej tablicy haszującej. Rozumiem, że praktycznie mówiąc tablice skrótów PHP dają wydajność O (1), a przynajmniej średnio O (1) - po to są tabele. Byłem ciekawy, dlaczego powiedziałeś, że są „naprawdę O (n)”, a nie „naprawdę O (logn)”. Nawiasem mówiąc, świetny post!
Cam
10
Złożoność czasowa powinna być dołączona do dokumentacji! Wybór odpowiedniej funkcji pozwala zaoszczędzić tyle czasu lub nakazuje unikać robienia tego, co planujesz: p Dzięki za tę listę!
Samuel
41
Wiem, że to stare ... ale co? Ta krzywa wcale nie pokazuje O (n), pokazuje O (log n), en.wikipedia.org/wiki/Logarithm . Co jest również dokładne w porównaniu z zagnieżdżonymi mapami skrótów.
Andreas
5
Co to jest Big-O unset na elemencie tablicy?
Chandrew
12
Chociaż tabele skrótów rzeczywiście mają złożoność wyszukiwania O (n) w najgorszym przypadku, średni przypadek to O (1), a szczególny przypadek, w którym testowany jest test porównawczy, jest nawet gwarantowany O (1), ponieważ jest ciągły, liczony od 0 tablica, która nigdy nie będzie miała kolizji mieszających. Powód, dla którego nadal widzisz zależność od rozmiaru tablicy, nie ma nic wspólnego ze złożonością algorytmu, jest to spowodowane efektami pamięci podręcznej procesora. Im większa jest tablica, tym bardziej prawdopodobne jest, że wyszukiwania o losowym dostępie spowodują pominięcia pamięci podręcznej (i pamięci podręcznej wyżej w hierarchii).
NikiC
5

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 .

Dathan
źródło
To naprawdę nie jest odpowiedź. Jak powiedziałem w pytaniu, próbowałem już zajrzeć do kodu źródłowego PHP. Ponieważ PHP jest zaimplementowane, zostało napisane w języku C przy użyciu złożonych makr, co może czasami utrudnić „zobaczenie” leżącego u podstaw dużego O dla funkcji.
Kendall Hopkins
@Kendall Przeoczyłem twoje odniesienie do nurkowania w kodzie źródłowym. Jednak w mojej odpowiedzi znajduje się odpowiedź: „Nie sądzę, aby istniała konkretna kompleksowa dokumentacja złożoności algorytmicznej metod PHP”. „Nie” to całkowicie poprawna odpowiedź. (c:
Dathan
4

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.

ryeguy
źródło
9
To jest źle. Jestem w 100% pewien, że array_key_exists nie musi iterować każdego klucza. Jeśli nie wierzysz, spójrz na poniższy link. Powodem jest to, że jest o wiele szybszy, ponieważ jest to konstrukcja językowa. Co oznacza, że ​​nie ma narzutu wywołania funkcji. Myślę też, że z tego powodu może to być buforowanie wyszukiwania. Nie jest to również odpowiedź na PYTANIE! Chciałbym listę funkcji Big (O) dla funkcji PHP (jak mówi pytanie). Ani jednego wzorca moich przykładów. svn.php.net/repository/php/php-src/branches/PHP_5_3/ext/…
Kendall Hopkins
Jeśli nadal mi nie wierzysz, stworzyłem mały punkt odniesienia, aby pokazać, o co chodzi. pastebin.com/BdKpNvkE
Kendall Hopkins
To, co jest nie tak z twoim testem porównawczym, polega na tym, że musisz wyłączyć xdebug. =)
Guilherme Blanco
3
Istnieją dwa krytyczne powody, dla których chcesz używać isset zamiast array_key_exists. Po pierwsze, isset to konstrukcja języka zmniejszająca koszt wywołania funkcji. Jest to podobne do argumentu $arrray[] = $appendvs. array_push($array, $append)Po drugie, array_key_exists rozróżnia także wartości nie ustawione i zerowe. Gdyż $a = array('fred' => null); array_key_exists('fred', $a)zwróci prawdę, a isset($['fred'])zwróci fałsz. Ten dodatkowy krok nie jest trywialny i znacznie wydłuży czas wykonania.
orca
0

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.

Josh Stern
źródło