in_array n'est pas lent
Par Laurentj le vendredi, juin 6 2008, 11:03 - Technologies Web - Lien permanent
Je réagis à certains billets comme celui de nexen qui annoncent que in_array est lent, comme si c'était un scoop.
Franchement, tout développeur ayant un minimum d'experience en programmation (niveau IUT première année, premiers cours en algorithmie), sait que faire une recherche séquencielle dans un ensemble de valeur est plus lent que faire une recherche en passant par un index. Ce n'est pas un scoop. C'est mathématique.
Maintenant on n'utilise pas in_array pour faire la même chose qu'avec des isset. C'est comme si on s'aperçevait sur un circuit que la 2CV est plus lente qu'une formule 1. Bah oui mais la 2CV n'est pas conçu pour aller sur un circuit.
Bref, l'auteur du billet original n'a pas choisi les bonnes fonctions pour coder son truc, et il s'étonne ensuite que c'est lent. Normal quoi.
Conclusion : in_array n'est pas lent. Il fait ce qu'il doit faire. Il n'est lent que si on l'utilise dans des situations inadaptées. point.
Commentaires
Un petit wtf ce code non (le code original) ?
@mathedit : oui, j'osais pas le dire :-)
Un algo en O(n) est plus rapide qu'un algo en O(n²) sur une quantité importante de données ! Quelle découverte ! Faisons-en une publication !
Ce genre d'article m'intéresse, car en 10 secondes, je sait que pour des gros traitement isset sera plus rapide que in_array.
Je n'ai pas eu la chance (ou la présence d'esprit) de faire des études en rapport avec le développement.
:)
Le geek aime rappeler qu'il est un geek, il a un léger complexe de supériorité.
Le geek n'est pas pédagogue, ça lui fait perdre du temps.
C'est simplement la base de l'algorithmie. Ça doit être enseigné en premier semestre d'études supérieures, même aux non-informaticiens. Enfin bon, une petite explication :
in_array parcourt tout le tableau jusqu'à trouver la valeur, la complexité est donc linéaire en la taille du tableau, que l'on appelle n. C'est donc une fonction en O(n). Une table de hachage fonctionne en calculant un entier à partir des clés (ici, des chaînes), et en les utilisant comme index de tableau. Il peut tout de même y avoir des collisions, donc dans le pire des cas c'est O(n) mais en moyenne c'est O(1). Une autre technique consiste tout simplement à trier les données (c'est ce que font les bases de données). Dans ce cas-là, la recherche peut s'effectuer par dichotomie, donc en O(log n).
Donc, pour vérifier qu'un tableau (de taille n) se trouve inclus dans un autre tableau (de taille m), une solution en O(max(n, m)) est possible, il suffit de construire la table de hachage correspondante à l'un des tableaux O(la_taille_du_tableau) puis à parcourir l'autre et vérifier que chaque élément se trouve dans la table. Alors que le mec, il a fait un algo stupide en O(n*m), qui bien sûr se dégrade fortement en performance par rapport à l'autre quand n et m augmentent...
@root
Je suppose que c'est une remarque à mon égard. Je crois donc que vous me connaissez très mal. Il me semble qu'en terme de pédagogie, j'en ai fait déjà énormément sur d'autres thèmes, une recherche sur google vous le montrera.
En tout cas, vous êtes de ceux qui font des suppositions et jugement à deux balles gratuitement. Par exemple, il ne vous serez pas venu à l'idée qu'une des raisons du pourquoi je n'ai pas donné autant d'explication que loufoque (merci à lui ;-) ), pouvait être le manque de temps. Juste par exemple... Et encore, j'ai bien indiqué qu'il s'agit du b.a.ba de l'algorithmie, donc que ceci est expliqué dans le premier bon bouquin venu sur la programmation, et à plein d'endroit sur le web très certainement, suffit de chercher ou de se déplacer dans une bibliothèque.
Bref, monsieur root, abstenez-vous à l'avenir de poster de tels commentaires sur mon blog. Surtout que vous n'êtes même pas obligé de me lire.
@laurent
Je trouve que le travail réalisé sur Jelix est particulièrement intéressant, d'autant qu'il tend à être bien documenté. Un sacré boulot.
Loin de moi l'idée de juger de vous sur ce blog ou sur vos forums, cependant il me semble que le ton de certains de vos posts n'est pas tjrs bien senti. Parfois un peu expédié, un peu sec, voir désagréable pour certaines personnes qui vous lisent régulièrement. Celui-ci pourrait en faire partie.
C'est sans doute de voir le commentaire de Lipki, par ailleurs contributeur de Jelix, qui m'a fait écrire ainsi.
Bonne continuation.
Alors la, j'suis fan ! <3 MERCI !