Comment le tableau PHP est-il implémenté au niveau C ?

Question

Le PHP array est l'une des principales fonctionnalités de PHP. Il est clairsemé, permet des clés multi-types dans le même tableau, et supporte les fonctionnalités d'ensemble, de dictionnaire, de tableau, de pile/queue et d'itération.

Mais après avoir travaillé avec PHP pendant un certain temps, je me suis rendu compte que beaucoup d'éléments de l'environnement de travail de l'entreprise ne sont pas toujours disponibles. array_* sont beaucoup plus lentes que ce que l'on pourrait croire à première vue. Comme dans le cas de array_rand sur un très grand tableau (10000+). array_rand est si lent en fait, que dans les cas où vous utilisez le tableau php comme un tableau indexé, une fonction comme rand( 0, array_length( $array ) - 1 ) fonctionne BEAUCOUP plus vite que array_rand .

J'en viens maintenant à ma question.

Comment le tableau PHP est-il implémenté au niveau C ? Cela serait très utile pour prédire le Big O d'une fonction qui utilise fortement les différentes fonctionnalités du type de données tableau de PHP.

Answer 1

Après avoir lu zend/zend_hash.h et ext/standard/array.c, je pense avoir trouvé la réponse (Merci à Chris et gumbo pour les suggestions).

Le tableau PHP est une table de hachage chaînée (recherche de O(c) et O(n) sur les collisions de clés) qui permet des clés de type int et string. Elle utilise deux algorithmes de hachage différents pour faire tenir les deux types de clés dans le même espace de hachage. De plus, chaque valeur stockée dans la table de hachage est liée à la valeur stockée avant et à la valeur stockée après (liste liée). Il possède également un pointeur temporaire qui est utilisé pour contenir l'élément actuel afin que le hachage puisse être itéré.

La prise pour le array_rand est qu'afin de garantir que la clé est vraiment aléatoire, la fonction array_rand doit itérer sur le tableau rand(0, count($array)) fois (O(n)). Ceci est dû au fait qu'il n'y a aucun moyen de se déplacer vers un décalage dans la table de hachage en temps O(c) car il n'y a aucune garantie qu'il n'y a pas de clés manquantes dans la plage.

Cette découverte m'a quelque peu troublé, car cela signifie qu'il n'existe AUCUN type de données en PHP qui ait les caractéristiques normales d'un tableau C. La plupart du temps, cela ne pose pas de problème, car les recherches par hachage sont plus rapides, mais ses défauts apparaissent dans les cas suivants array_rand .

Une autre chose qui m'a également troublé est la différence entre l'implémentation de array_key_exists y in_array . array_key_exists utilise la recherche de hachage (la plupart du temps O(c)) pour voir si une clé est dans le tableau, alors que in_array doit rechercher linéairement le hachage (O(n)).

Considérez les deux exemples ci-dessous :

in_array version

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

tableau_clé_existe version

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

Bien que la version in_array semble beaucoup plus propre et plus simple à comprendre, elle est en fait très lente sur les grands tableaux (O(n)), alors que array_key_exists (malgré son nom fâcheusement long) est très rapide (O(c) ou presque).

En conclusion : J'aurais aimé qu'il y ait un drapeau transparent dans la structure de données de zend HashTable qui serait activé dans les cas où le tableau a été créé en utilisant array_push o array[] = $value qui permettrait une mise à l'échelle comme un tableau C au lieu d'une liste liée.

Answer 2

Les tableaux associatifs de PHP sont en fait des implémentations de Tableaux de hachage .

En interne, il est possible de faire des tableaux numériques ou des tableaux associatifs. Si vous les combinez, vous obtenez un tableau associatif.

Dans les tableaux numériques, c'est très similaire au C. Vous avez un tableau de pointeurs vers des structs ZVAL.

Comme les pointeurs ont une longueur fixe (appelons-la n), le calcul du décalage (x) est facile : x * n.

En PHP, les types sont des structs ZVAL (parce que de cette façon, il implémente les types dynamiques), mais cela aide aussi dans les tableaux associatifs, parce que vous pouvez assumer une longueur fixe. Ainsi, même si l'accès direct aux tableaux est plus lent, il est toujours considéré comme O(1).

Alors, que se passe-t-il dans les chaînes de caractères ? PHP utilise la fonction de hachage pour les convertir en nombres entiers.

La recherche dans les tableaux numériques et associatifs a une efficacité similaire, car ils sont tous numériques en interne.

Seul l'accès direct aux clés du tableau est plus lent, en raison du niveau supplémentaire (fonction de hachage).

Answer 3

Puisque les tableaux PHP sont des cartes ordonnées (même en utilisant des indices entiers contigus) array_rand() doit probablement consulter une liste de clés pour sélectionner un élément. Je suppose qu'il serait prohibitif, en termes d'espace et de temps, de mettre en cache la liste de clés (fréquemment invalidée), de sorte que chaque appel va entraîner au moins un coût de traversée et de construction O(n).

Parce que votre rand(... length ...) tire avantage de la connaissance spéciale que vous avez que les clés sont des entiers contigus, vous obtiendrez des coûts de recherche O(log n). Cela semble cohérent avec les données de Chacha102.

Answer 4

Jetez un coup d'œil à zend/zend_hash.c y zend/zend_hash.h

Je ne connais pas le c, mais pour moi, ça ressemble à une table de hachage chaînée.

Answer 5

Voyez ce commentaire dans la documentation qui confirme votre dilemme : array_rand, bien que rapide pour les petits tableaux, évolue très mal.

J'ai modifié fake_array_rand pour qu'il ne renvoie toujours qu'un seul élément, et j'ai effectué quelques tests par rapport à l'appel de array_rand avec le second paramètre égal à 1. J'ai exécuté 100 échantillons pour chaque fonction pour chaque nombre d'éléments et j'ai pris le résultat moyen. Alors que le array_rand interne est plus rapide pour un petit nombre d'éléments, il est très mal adapté.

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