Wie ist das PHP-Array auf der C-Ebene implementiert?

Das PHP- array ist eine der corefunktionen von PHP. Es ist spärlich, erlaubt multi-typisierte Schlüssel im selben Array und unterstützt Set, Dictionary, Array, Stack / Queue und iterative functionalität.

Aber nachdem ich eine Weile mit PHP gearbeitet habe, habe ich festgestellt, dass einige der array_* -functionen viel langsamer sind, als man auf den ersten Blick denkt. Wie im Falle von array_rand auf einem sehr großen Array (10000+). array_rand ist so langsam, dass in Fällen, in denen Sie das PHP-Array als indiziertes Array verwenden, eine function wie rand( 0, array_length( $array ) - 1 ) VIEL schneller läuft als array_rand .

Jetzt zu meiner Frage.

Wie ist das PHP-Array auf der C-Ebene implementiert? Dies wäre sehr hilfreich für die Vorhersage des Big O einer function, die die verschiedenen functionen des PHP-Array-Datentyps stark nutzt.

PHP-assoziative Arrays sind tatsächlich eine Implementierung von HashTables .

Intern ist es möglich, numerische Arrays oder assoziative Arrays zu erstellen. Wenn Sie sie kombinieren, handelt es sich um ein assoziatives Array.

In numerischen Arrays ist es C sehr ähnlich. Sie haben ein Array von pointersn auf ZVAL-Strukturen.

Da pointers eine feste Länge haben (nennen wir es n), ist die Berechnung von offset (x) einfach: x * n.

In PHP-Typen sind ZVAL-Strukturen (weil es so dynamische Typen implementiert), aber es hilft auch im assoziativen Array, weil Sie eine feste Länge annehmen können. Selbst wenn der direkte Zugriff auf das Array langsamer ist, wird es immer noch als O (1) betrachtet.

Was passiert also in String Keys? PHP verwendet die Hash-function, um sie in intergers umzuwandeln.

Die Suche in numerischen und assoziativen Arrays hat eine ähnliche Effizienz, da sie intern alle numerisch sind.

Nur der direkte Zugriff auf Array-Schlüssel ist aufgrund der zusätzlichen Ebene (Hash-function) langsamer.

Nach dem Lesen von zend / zend_hash.h und ext / standard / array.c denke ich, dass ich die Antwort gefunden habe (Danke Chris und Gumbo für die Vorschläge).

Das PHP-Array ist eine verkettete Hash-Tabelle (Nachschlagen von O (c) und O (n) bei Schlüsselkollisionen), die int- und string-Schlüssel erlaubt. Es verwendet 2 verschiedene Hashing-Algorithmen, um die beiden Typen in den gleichen Hash-Schlüsselraum einzupassen. Außerdem wird jeder im Hash gespeicherte Wert mit dem davor gespeicherten Wert und dem hinter ihm gespeicherten Wert verknüpft (verkettete Liste). Es hat auch einen temporären pointers, der verwendet wird, um das aktuelle Element zu halten, so dass der Hash iteriert werden kann.

Der Haken für die function array_rand ist, dass die function array_rand über das Array rand(0, count($array)) mal (0 (n)) iterieren muss, um sicherzustellen, dass der Schlüssel wirklich zufällig ist. Dies liegt daran, dass es in O (c) -Zeit keine Möglichkeit gibt, zu einem Offset in der Hash-Tabelle zu wechseln, da es keine Garantie dafür gibt, dass keine Schlüssel in dem Bereich fehlen.

Diese Entdeckung hat mich etwas beunruhigt, weil es bedeutet, dass es in PHP KEINE Datentypen gibt, die normale C-Array-Eigenschaften haben. Jetzt ist das meistens ok, da Hash-Lookups sehr viel schneller sind, aber in Fällen wie array_rand Fehler array_rand .

Eine andere Sache, die mich auch beunruhigte, war der Unterschied zwischen der Implementierung von array_key_exists und in_array . array_key_exists verwendet die Hash-Suche (meistens O (c)), um zu sehen, ob sich ein Schlüssel im Array befindet, während in_array den Hash (O (n)) linear durchsuchen muss.

Betrachten Sie die folgenden zwei Beispiele:

in_array Version

 $array = range(0, 100000); if( in_array( $random_key, $array ) ) { //we found a value } 

array_key_existiert Version

 $array = array_fill_keys( range(0, 100000), NULL ); if( array_key_exists( $random_key, $array ) ) { //we found a value, err key } 

Während die in_array-Version viel sauberer und einfacher zu verstehen ist, ist sie bei großen Arrays (O (n)) sehr langsam, wobei array_key_exists (trotz des lästigen langen Namens) sehr schnell ist (O (c) oder close).

Zusammenfassend: Ich wünschte, es gäbe ein transparentes Flag in der zend HashTable-Datenstruktur, das in Fällen gesetzt würde, in denen das Array mit array_push oder array[] = $value , die eine Skalierung wie ein C-Array statt eines verknüpften ermöglichen würden Liste.

Da PHP-Arrays geordnete Maps sind (selbst wenn zusammenhängende Integer-Indizes verwendet werden), muss array_rand() wahrscheinlich eine Liste von Schlüsseln array_rand() , aus denen ein Element ausgewählt werden kann. Ich nehme an, dass es ineffektiv wäre, die (häufig invalidierte) Schlüsselliste zwischenzuspeichern, so dass jeder Anruf mindestens einen O (n) -Traversal- und -Kostenaufwand verursachen würde.

Da Ihre rand(... length ...) Implementierung das spezielle Wissen ausnutzt, dass die Schlüssel zusammenhängende Ganzzahlen sind, erhalten Sie O (log n) Lookup-Kosten. Dies scheint mit den Daten von Chacha102 übereinzustimmen.

Sehen Sie diesen Kommentar in der Dokumentation, der Ihr Dilemma bestätigt, dass array_rand, während es für kleine Arrays schnell ist, sehr schlecht skaliert.

Ich modifizierte fake_array_rand, um immer nur 1 Element zurückzugeben, und führte einige Benchmarks gegen den Aufruf von array_rand mit dem zweiten Parameter als 1 durch. Ich führte 100 Samples für jede function für jede Anzahl von Elementen durch und nahm das Durchschnittsergebnis. Während das interne array_rand für eine kleine Anzahl von Elementen schneller ist, skaliert es sehr schlecht.

 1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. for fake_array_rand 10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. for fake_array_rand 100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. for fake_array_rand 1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. for fake_array_rand 10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. for fake_array_rand 100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. for fake_array_rand 1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand < ?php function fake_array_rand ($array) { $count = count ($array); # Help keep the number generator random :) $randval and usleep ("0.$randval"); # Seed the random number generator # Generate a random number srand ((double) microtime() * 10000000); $randval = rand(); # Use the random value to 'pick' an entry from the array # Count the number of times that the entry is picked ++$index[$randval % $count]; return $array[$randval % $count]; } ?> 

http://us.php.net/manual/en/function.array-rand.php#22360

Schauen Sie sich zend/zend_hash.c und zend/zend_hash.h

Ich weiß nicht c, aber für mich sieht es wie ein angeketteter Hashtable aus.