Liste der Big-O für PHP-Funktionen

Question

Nachdem ich PHP nun schon eine Weile benutze, habe ich festgestellt, dass nicht alle eingebauten PHP-Funktionen so schnell sind wie erwartet. Betrachten Sie diese beiden möglichen Implementierungen einer Funktion, die herausfindet, ob eine Zahl eine Primzahl ist, indem sie ein zwischengespeichertes Array von Primzahlen verwendet.

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

Der Grund dafür ist in_array wird mit einer linearen Suche O(n) implementiert, die linear langsamer wird, wenn $prime_array wächst. Wo die array_key_exists Funktion ist mit einem Hash-Lookup O(1) implementiert, was nicht zu einer Verlangsamung führt, es sei denn, die Hash-Tabelle wird extrem voll (in diesem Fall ist es nur O(n)).

Bisher musste ich die großen O's durch Versuch und Irrtum entdecken, und gelegentlich Blick in den Quellcode . Nun zu der Frage...

Gibt es eine Liste mit den theoretischen (oder praktischen) Big-O-Zeiten für alle* eingebauten PHP-Funktionen?

*oder zumindest die interessanten davon

Ich finde es zum Beispiel sehr schwer, das große O der aufgeführten Funktionen vorherzusagen, weil die mögliche Implementierung von unbekannten Kerndatenstrukturen von PHP abhängt: array_merge , array_merge_recursive , array_reverse , array_intersect , array_combine , str_replace (mit Array-Eingängen), usw.

Answer 1

Da es nicht so aussieht, als hätte das schon jemand gemacht, dachte ich, es wäre eine gute Idee, es irgendwo als Referenz zu haben. Ich bin durchgegangen und habe entweder mittels Benchmark oder Code-Skimming die array_* Funktionen. Ich habe versucht, die interessanteren Big-O an die Spitze zu stellen. Diese Liste ist nicht vollständig.

Hinweis: Alle Big-O wurden unter der Annahme berechnet, dass ein Hash-Lookup O(1) ist, obwohl es in Wirklichkeit O(n) ist. Der Koeffizient von n ist so niedrig, dass der Aufwand für die Speicherung eines ausreichend großen Arrays Sie schmerzen würde, bevor die Eigenschaften des Big-O-Lookups zum Tragen kommen. Zum Beispiel ist der Unterschied zwischen einem Aufruf von array_key_exists bei N=1 und N=1.000.000 ist ~50% Zeitgewinn.

Interessante Punkte :

1. isset / array_key_exists ist viel schneller als in_array y array_search
2. + (Vereinigung) ist ein wenig schneller als array_merge (und sieht schöner aus). Aber es funktioniert anders, also bedenken Sie das.
3. shuffle ist auf der gleichen Big-O-Ebene wie array_rand
4. array_pop / array_push ist schneller als array_shift / array_unshift wegen der Re-Indexierungsstrafe

Nachschlagen :

array_key_exists O(n), aber wirklich nahe an O(1) - das liegt an der linearen Abfrage bei Kollisionen, aber da die Wahrscheinlichkeit von Kollisionen sehr gering ist, ist auch der Koeffizient sehr klein. Ich finde, man behandelt Hash-Lookups als O(1), um ein realistischeres Big-O zu erhalten. Zum Beispiel ist der Unterschied zwischen N=1000 und N=100000 nur etwa 50% langsamer.

isset( $array[$index] ) O(n), aber wirklich nahe an O(1) - es verwendet den gleichen Lookup wie array_key_exists. Da es sich um ein Sprachkonstrukt handelt, wird die Suche gecacht, wenn der Schlüssel hartkodiert ist, was zu einer Beschleunigung in Fällen führt, in denen derselbe Schlüssel wiederholt verwendet wird.

in_array O(n) - das liegt daran, dass eine lineare Suche durch das Array durchgeführt wird, bis der Wert gefunden ist.

array_search O(n) - verwendet die gleiche Kernfunktion wie in_array, gibt aber einen Wert zurück.

Warteschlangenfunktionen :

array_push O( var_i, für alle i)

array_pop O(1)

array_shift O(n) - es müssen alle Schlüssel neu indiziert werden

array_unshift O(n + var_i, für alle i) - es müssen alle Schlüssel neu indiziert werden

Array-Schnittmenge, Vereinigung, Subtraktion :

array_intersect_key wenn Schnittmenge 100% O(Max(param_i_size)*param_i_count, für alle i), wenn Schnittmenge 0% Schnittmenge O(param_i_size, für alle i)

array_intersect wenn Schnittmenge 100% O(n^2*param_i_count, für alle i), wenn Schnittmenge 0% Schnittmenge O(n^2)

array_intersect_assoc wenn Schnittmenge 100% O(Max(param_i_size)*param_i_count, für alle i), wenn Schnittmenge 0% Schnittmenge O(param_i_size, für alle i)

array_diff O( param_i_size, für alle i) - Das ist das Produkt aus allen param_sizes

array_diff_key O( param_i_size, for i != 1) - das liegt daran, dass wir nicht über das erste Array iterieren müssen.

array_merge O( array_i, i != 1 ) - braucht nicht über das erste Array zu iterieren

+ (union) O(n), wobei n die Größe des 2. Arrays ist (d.h. array_first + array_second) - weniger Overhead als array_merge, da es nicht neu nummerieren muss

array_replace O( array_i, für alle i )

Zufällig :

shuffle O(n)

array_rand O(n) - Erfordert eine lineare Abfrage.

Offensichtlich Big-O :

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice O(Versatz + Länge)

array_slice O(Offset + Länge) oder O(n) wenn Länge = 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)

Ich möchte mich bedanken bei Eureqa dafür, dass es einfach ist, das Big-O der Funktionen zu finden. Es ist eine erstaunliche kostenlos Programm, das die beste Anpassungsfunktion für beliebige Daten finden kann.

EDITAR:

Für diejenigen, die bezweifeln, dass PHP Array Lookups sind O(N) Ich habe einen Benchmark geschrieben, um das zu testen (sie sind immer noch effektiv O(1) für die meisten realistischen Werte).

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

Answer 2

Die Erklärung für den von Ihnen beschriebenen Fall ist, dass assoziative Arrays als Hash-Tabellen implementiert sind - so dass die Suche nach dem Schlüssel (und dementsprechend, array_key_exists ) ist O(1). Allerdings sind Arrays nicht nach Wert indiziert, so dass die einzige Möglichkeit, herauszufinden, ob ein Wert in dem Array existiert, eine lineare Suche ist. Das ist keine Überraschung.

Ich glaube nicht, dass es eine umfassende Dokumentation über die algorithmische Komplexität von PHP-Methoden gibt. Wenn es jedoch wichtig genug ist, um den Aufwand zu rechtfertigen, können Sie jederzeit einen Blick auf den Quellcode .

Answer 3

Sie sollten fast immer Folgendes verwenden isset 代わりに array_key_exists . Ich schaue mir die Interna nicht an, aber ich bin ziemlich sicher, dass array_key_exists ist O(N), weil es über jeden einzelnen Schlüssel des Arrays iteriert, während isset versucht, auf das Element mit demselben Hash-Algorithmus zuzugreifen, der beim Zugriff auf einen Array-Index verwendet wird. Das sollte O(1) sein.

Ein "Fallstrick", auf den Sie achten sollten, ist folgender:

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

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

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

---

Ich war neugierig, also habe ich den Unterschied gemessen:

<?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,132308959961 Sekunden
array_key_exists: 2,33202195168 Sekunden

Dies zeigt natürlich nicht die Zeitkomplexität, aber es zeigt, wie die beiden Funktionen im Vergleich zueinander stehen.

Um die Zeitkomplexität zu testen, vergleichen Sie die Zeit, die benötigt wird, um eine dieser Funktionen auf der ersten Taste und der letzten Taste auszuführen.

Answer 4

Wenn man in der Praxis Probleme mit Schlüsselkollisionen hätte, würde man Container mit einem sekundären Hash-Lookup oder einem ausgeglichenen Baum implementieren. Der balancierte Baum würde im schlimmsten Fall O(log n) und im durchschnittlichen Fall O(1) ergeben (der Hash selbst). Der Overhead lohnt sich in den meisten praktischen speicherinternen Anwendungen nicht, aber vielleicht gibt es Datenbanken, die diese Form der gemischten Strategie als Standardfall implementieren.