PHP tableaux et data-structures

Cela fait plusieurs projets que je mène en PHP dans lesquels l’impact de mes choix de conteneur de données sont très importants. Basiquement, en php, en utilise les tableaux qui sont très intuitifs et très… puissants.  Pourtant pour des raisons d’occupation mémoire ou bien pour une utilisation très précise, eh bien ils sont gourmand. Petit tour d’horizon des tableaux et de leurs alternatives en php.

Les tableaux php : caisse omnipotents?

Conception

Soyons clairs : un tableau PHP, ce n’est pas un tableau C ou Java. Ce n’est pas une liste python, c’est… un tableau PHP. A la source, c’est une “ordered map”. Cela permet d’utiliser ces tableaux comme tableau, dictionnaire, liste, file, pile… Mais surtout, de manière sous-jacente cela signifie qu’en PHP tout ce qui sera rangé dans un conteneur de donnée (que ça soit un array ou autre chose), il y aura une association clé=>valeur.

Cela est extrêmement important car en PHP, cela signifie qu’avec un peu d’effort de conception, vous pouvez organiser vos tableaux pour qu’à l’usage tout soit en O(1). Vous sacrifiez un peu (beaucoup) de mémoire, mais ça va vite.
SI je prend le temps de dire cela, c’est qu’il arrive souvent qu’un développeur, habitué à des langages comme Java ou C construise son tableau comme un tableau indicé. Puis, comme il veut que ses données n’aient pas de duplicata, il fait une fonction du type :

[cc lang=”php”]
function insert($value,$collection){
if(array_search($value)!==false){
$array[] = $value;
}
}

[/cc]

Et ça c’est du O(n), donc le temps pour insérer un élément, au lieu d’être constant comme il l’est habituellement avec les tableaux php, sera croissant avec le nombre de données. Puisque nous sommes en php, rien ne nous interdisait pourtant de faire

[cc lang=”php”]
$array[$value]=isset($array[$value])?:true;
[/cc]

API

L’autre avantage des arrays PHP est l’API qui les accompagne. C’est cette API qui vous permettra d’utiliser les tableaux comme des piles/files (pop,push,shift), qui vous permettra aussi de voir les tableaux comme des ensembles (diff, merge, surcharge de l’opérateur + et -). Ces fonctions sont très nombreuses, et vous permettent d’économiser du temps de développement sur tout ce qui concerne les algorithmes de tri, de filtrage…

Les fonctions sur les arrays sont nommées de cette manière : array_nom_de_la_fonction. Et si la méthode a une variante qui accepte une callback, il suffira d’ajouter un “u” pour faire array_unom_de_la_fonction.

Les alternatives

Les alternatives que je présentes sont celles proposées par la SPL (Standard PHP Library). Je n’en présente volontairement que deux que j’ai utilisés récemment, mais un grand nombres de structures de données vous sont proposées. Vous aurez ainsi la possibilité d’utiliser une liste chaînée, une implémentation objet des tableaux, une pile et une file déjà codées. Mais place à deux structures que j’apprécie beaucoup.

Pour faire comme Java

Il faut faire plaisir aux fan de Java, il faut leur donner un tableau indicé à taille fixe qui ne se soucie pas des clés string des arrays.
C’est ainsi que fut créé SPLFixedArray. Son utilisation? comme un tableau java :
[cc lang=”php”]$array = new SPLFixedArray($size);[/cc] Contrairement à un tableau php habituel, il y aura d’emblée 5 cases de créées, et la taille sera de $size et non de 0. Un json_encode vous en assurera en imprimant :

{“0″:null,”1″:null,”2″:null,”3″:null,”4”:null}

Si, théoriquement un FixedArray est plus rapide (pas de hashmap) (5% sur la version 5.4, je ne sais pas pour la 5.5), son implémentation dans la 5.3 est légèrement plus lente qu’un array normal. Néanmoins, des progrès sont sans cesse faits et la conception en soit de la SPL évolue donc il faudra être patient. En fait la principale optimisation de la SPLFixedArray c’est l’utilisation mémoire. Ces derniers temps, j’ai migré un code qui se servait de matrice 10×10 de array vers SPLFixedArray. Auparavant, pour m’assurer du gain réel, j’avais été vérifier avec quelques benchmark le gain que je faisais et pour la mémoire, voici la différence :

  • Array : 225952 octets pour une matrice d’entiers 5×5
  • SPLFixedArray : 225632 octets pour une matrice d’entiers 5×5

gain : 320 octets pour 25 entiers stockés, ces entiers étant sur 64bits : nous faisons une économie de 320 octets pour 200 octets de données pures.

Cette tendance est réelle et confirmée par un gain de 1024 octets sur une matrice d’entiers 10×10.

SPLHeap

Se déclinant en MinHeap, MaxHeap et PriorityQueue, le tas est une structure de données que j’ai pu utiliser dans deux cas très précis, à savoir l’algorithme de Dijkstra et une insertion de données dans une collection de manière à ce que les nouvelles données ne cassent pas l’ordre désiré.

Ici il s’agit surtout d’éviter absolument des opérations de tri en O(nlog(n)) à chaque fois qu’on doit insérer une donnée. En effet même si les processeurs actuels sont rapides, c’est quand même assez long comme complexité. Consommer un “log(n)” à l’insertion permet d’éviter un tri complet à chaque fois. En plus cela permet de contrôler l’endroit où l’objet est inséré grâce à plusieurs paramètres pondérés.

Conclusion

Même si elle a certaines failles de conception la SPL vous offre des alternatives intéressantes pour ranger vos données de manière optimisée. Néanmoins les tableaux php restent sa plus grande force et permettent une optimisation temporelle des algorithmes qui est immense ! N’hésitez pas à réfléchir à la manière dont vous utilisez vos tableaux !