Hoe is de PHP-array geïmplementeerd op C-niveau?

De PHP arrayis een van de kernfuncties van PHP. Het is schaars, laat sleutels met meerdere typen in dezelfde array toe en ondersteunt set-, woordenboek-, array-, stapel/wachtrij- en iteratieve functionaliteit.

Maar na een tijdje met PHP te hebben gewerkt, heb ik ontdekt dat nogal wat van de array_*-functies veel langzamer zijn dan je op het eerste gezicht zou denken. Zoals in het geval van array_randop een zeer grote array (10000+). array_randis zelfs zo traag, dat in gevallen waarin je de php-array als een geïndexeerde array gebruikt, een functie als rand( 0, array_length( $array ) - 1 )werkt VEEL sneller dan array_rand.

Nu over naar mijn vraag.

Hoe is de PHP-array geïmplementeerd op C-niveau?Dit zou erg handig zijn voor het voorspellen van de Big O van een functie die veel gebruikmaakt van de verschillende functionaliteit van het PHP-arraygegevenstype.


Antwoord 1, autoriteit 100%

Na het lezen van zend/zend_hash.h en ext/standard/array.c denk ik dat ik het antwoord heb gevonden (bedankt Chris en gumbo voor de suggesties).

De PHP-array is een geketende hash-tabel (opzoeken van O(c) en O(n) op sleutelbotsingen) die int- en string-sleutels mogelijk maakt. Het gebruikt 2 verschillende hash-algoritmen om de twee typen in dezelfde hash-sleutelruimte te passen. Ook is elke waarde die in de hash is opgeslagen, gekoppeld aan de waarde die ervoor is opgeslagen en de waarde die erna is opgeslagen (gekoppelde lijst). Het heeft ook een tijdelijke aanwijzer die wordt gebruikt om het huidige item vast te houden, zodat de hash kan worden herhaald.

Het addertje onder het gras voor de functie array_randis dat om te verzekeren dat de sleutel echt willekeurig is, de functie array_randde array rand(0, count($array))keer (O(n)). Dit komt omdat er geen manier is om naar een offset in de hashtabel in O(c)-tijd te gaan, omdat er geen garantie is dat er geen sleutels in het bereik ontbreken.

Deze ontdekking heeft me enigszins verontrust, omdat het betekent dat er GEEN datatype in PHP is dat normale C-array-kenmerken heeft. Nu is dit meestal oké, omdat hash-lookups erg sneller zijn, maar de fouten worden zichtbaar in gevallen als array_rand.

Een ander ding waar ik me ook zorgen over maakte, was het verschil tussen de implementatie van array_key_existsen in_array. array_key_existsgebruikt de hash-lookup (meestal O(c)) om te zien of een sleutel in de array staat, terwijl in_arrayde hash lineair moet zoeken (O( N)).

Beschouw de twee onderstaande voorbeelden:

in_array-versie

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

array_key_bestaat versie

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

Hoewel de in_array-versie er veel schoner en eenvoudiger te begrijpen uitziet, is deze in feite erg traag op grote arrays (O(n)), waar array_key_exists (ondanks de irritant lange naam) erg snel is (O(c) of dichtbij).

Tot slot:
Ik wou dat er een transparante vlag was in de zend HashTable-gegevensstructuur die zou worden ingesteld in gevallen waarin de array is gemaakt met behulp van array_pushof array[] = $valuedie zou laat schalen toe als een C-array in plaats van een gekoppelde lijst.


Antwoord 2, autoriteit 80%

PHP associatieve arrays zijn in feite implementaties van HashTables.

Intern is het mogelijk om numerieke arrays of associatieve arrays te maken.
Als je ze combineert, is het een associatieve array.

In numerieke arrays lijkt het erg op C. Je hebt een array van verwijzingen naar ZVAL-structs.

Omdat pointers een vaste lengte hebben (laten we het n noemen), is de berekening van de offset (x) eenvoudig: x * n.

In PHP-typen zijn ZVAL-structs (omdat het op die manier dynamische typen implementeert), maar het helpt ook bij associatieve arrays, omdat je kunt uitgaan van een vaste lengte. Dus zelfs als directe toegang tot array langzamer is, wordt het nog steeds als O(1) beschouwd.

Dus wat gebeurt er in tekenreekstoetsen? PHP gebruikt de hash-functie om ze naar intergers te converteren.

Zoeken in numerieke en associatieve arrays heeft dezelfde efficiëntie, omdat ze intern allemaal numeriek zijn.

Alleen directe toegang tot array-sleutels is langzamer vanwege het extra niveau (hash-functie).


Antwoord 3, autoriteit 15%

Aangezien PHP-arrays geordende kaarten zijn(zelfs bij gebruik van contiguous integer indices) array_rand()moet waarschijnlijk een lijst met sleutels opsommen om een ​​element uit te selecteren. Ik vermoed dat het onbetaalbaar ruimte en tijd zou kosten om de (vaak ongeldig gemaakte) sleutellijst in de cache op te slaan, zodat elke oproep ten minste O(n)-overgangs- en constructiekosten met zich meebrengt.

Omdat uw rand(... length ...)implementatie gebruik maakt van de speciale kennis die u heeft dat de sleutels aaneengesloten gehele getallen zijn, krijgt u O(log n) opzoekkosten. Dit lijkt consistent met de gegevens van Chacha102.


Antwoord 4, autoriteit 7%

Bekijk zend/zend_hash.cen zend/zend_hash.h

Ik ken c niet, maar voor mij lijkt het op een geketende hashtabel.


Antwoord 5, autoriteit 5%

Zie deze opmerking in de documentatie die uw dilemma bevestigt dat array_rand, hoewel snel voor kleine arrays, zeer slecht schaalt.

Ik heb fake_array_rand aangepast om altijd maar 1 element terug te geven, en heb een aantal benchmarks gedaan tegen het aanroepen van array_rand met de tweede parameter als 1. Ik heb 100 samples uitgevoerd voor elke functie voor elk aantal elementen en heb het gemiddelde resultaat genomen. Hoewel de interne array_rand sneller is voor een klein aantal elementen, schaalt het erg slecht.

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

Other episodes