Liste von Big-O für PHP Funktionen

Da es nicht so aussieht, als hätte jemand das getan, bevor ich dachte, es wäre eine gute Idee, es irgendwo als Referenz zu haben. Ich bin aber entweder über Benchmark oder Code-Skimming gegangen, um die array_*-Funktionen zu charakterisieren. Ich habe versucht, das interessantere Big-O an die Spitze zu bringen. Diese Liste ist nicht vollständig.

Hinweis: Alle Big-O, bei denen unter der Annahme einer Hash-Suche berechnet wird, lautet O(1), obwohl es wirklich O (n) ist. Der Koeffizient von n ist so niedrig, dass der RAM-Aufwand für das Speichern eines ausreichend großen Arrays Sie verletzen würde, bevor die Eigenschaften des Nachschlages von Big-O wirksam werden. Zum Beispiel ist die Differenz zwischen einem Aufruf von array_key_exists bei N = 1 und N = 1.000.000 um 50% Zeitsteigerung.

Interessante Punkte:

1. issetarray_key_exists ist viel schneller als in_array und array_search
2. + (union) ist etwas schneller als array_merge (und sieht schöner aus). Aber es funktioniert anders, also vergiss das nicht.
3. shuffle befindet sich auf derselben Big-O-Schicht wie array_Rand
4. array_pop/array_Push ist schneller als array_shift/array_unshift, weil der Index erneut bestraft wird

_/Lookups:

array_key_exists O(n), aber sehr nahe an O(1) - dies ist auf lineares Polling in Kollisionen zurückzuführen, aber da die Wahrscheinlichkeit von Kollisionen sehr gering ist, ist der Koeffizient auch sehr klein. Ich finde, Sie behandeln Hash-Lookups wie 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 sehr nahe an O(1) - es verwendet dieselbe Suche wie array_key_exists. Da es sich um ein Sprachkonstrukt handelt, wird die Suche zwischenspeichert, wenn der Schlüssel hartcodiert ist. Dies führt zu einer Beschleunigung in Fällen, in denen derselbe Schlüssel wiederholt verwendet wird. 

in_array O(n) - Dies geschieht, weil das Array linear durchsucht wird, bis der Wert gefunden wird.

array_search O(n) - verwendet dieselbe Kernfunktion wie in_array, gibt jedoch den Wert zurück.

Warteschlangenfunktionen:

array_Push O (∑ var_i, für alle i)

array_pop O(1) 

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

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

Array Schnittpunkt, Vereinigung, Subtraktion:

array_intersect_key wenn der Schnittpunkt 100% O (Max (param_i_size)) * ∑param_i_count für alle i) ist, wenn der Schnittpunkt 0% O (∑param_i_size, für alle i) schneidet

array_intersect wenn die Kreuzung 100% für O (n ^ 2 * ∑param_i_count für alle i) ist, wenn die Kreuzung 0% O (n ^ 2) schneidet

array_intersect_assoc wenn der Schnittpunkt 100% O (Max (param_i_size)) * ∑param_i_count für alle i) ist, wenn der Schnittpunkt 0% O (∑param_i_size, für alle i) schneidet

array_diff O (π param_i_size, für alle i) - Das ist ein Produkt aller param_sizes

array_diff_key O (∑ param_i_size, für i! = 1) - dies liegt daran, dass wir das erste Array nicht durchlaufen müssen.

array_merge O (∑ array_i, i! = 1) - das erste Array muss nicht wiederholt werden

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

array_replace O (∑ array_i, für alle i)

Zufällig:

shuffle O (n)

array_Rand O(n) - Erfordert eine lineare Abfrage.

Offensichtliches Big-O:

array_fill O (n)

array_fill_keys O (n)

range O (n)

array_splice O (Offset + Länge)

array_slice O (Offset + Länge) oder O(n), wenn length = 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 bei Eureqa dafür bedanken, dass Sie das Big-O der Funktionen leicht gefunden haben. Es ist ein erstaunliches freies Programm, das die am besten geeignete Funktion für beliebige Daten findet.

BEARBEITEN:

Für diejenigen, die bezweifeln, dass PHP Array-Lookups O(N) sind, habe ich einen Benchmark geschrieben, um dies zu testen (sie sind immer noch 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 );
}