Pourquoi la lecture en boucle d'un tableau est-elle tellement plus rapide que la méthode native JavaScript indexOf ? Y a-t-il une erreur ou quelque chose que je n'ai pas pris en compte ? Je m'attendais à ce que les implémentations natives soient plus rapides.
For Loop While Loop indexOf
Chrome 10.0 50,948,997 111,272,979 12,807,549
Firefox 3.6 9,308,421 62,184,430 2,089,243
Opera 11.10 11,756,258 49,118,462 2,335,347 
Ok, en regardant les autres benchmarks ici, je me gratte la tête sur la façon dont la plupart des développeurs semblent faire leur benchmarking.
Je m'excuse, mais la manière dont cela est fait conduit à des conclusions terriblement erronées, et je dois donc aller un peu plus loin et donner un commentaire sur les réponses fournies.
Mesurer où trouver l'élément 777 dans un tableau qui ne change jamais et qui mène toujours à l'index 117 semble tellement inapproprié pour des raisons évidentes que j'ai du mal à expliquer pourquoi. On ne peut raisonnablement extrapoler quoi que ce soit à partir d'un point de repère aussi excessivement spécifique ! La seule analogie qui me vient à l'esprit est celle d'une recherche anthropologique sur les un et de qualifier les résultats de vue d'ensemble de toute la culture du pays dans lequel cette personne vit. Les autres points de référence ne sont pas beaucoup plus intéressants.
Pire encore : la réponse acceptée est une image sans lien avec la référence utilisée Nous n'avons donc aucun moyen de contrôler si le code de ce benchmark est correct (je n'ai pas d'autre choix que de le faire). espoir il s'agit d'une capture d'écran d'un lien jsperf qui figurait à l'origine dans la question et qui a ensuite été supprimé en faveur du nouveau lien jsben.ch). Ce n'est même pas une explication de la question originale : pourquoi l'un est plus performant que l'autre (une affirmation très discutable au départ).
Tout d'abord, vous devez savoir que tous les sites d'évaluation des performances ne se valent pas - Certains peuvent ajouter des erreurs significatives à certains types de mesures en raison de leur propre cadre qui interfère avec la synchronisation.
Aujourd'hui, nous sommes supposé pour comparer les performances de différentes méthodes de recherche linéaire sur un tableau. Réfléchissez un instant à l'algorithme lui-même :
C'est tout l'algorithme de recherche linéaire, n'est-ce pas ?
Ainsi, certains des tests liés comparent des tableaux triés et non triés (parfois incorrectement appelés "aléatoires", bien qu'ils soient dans le même ordre à chaque itération). XKCD pertinent ). Il devrait être évident que cette n'affecte en rien l'algorithme ci-dessus - l'opérateur de comparaison ne voit pas que toutes les valeurs augmentent de manière monotone.
Oui, les tableaux ordonnés ou non ordonnés peuvent avoir de l'importance, lorsque l'on compare les performances de recherche linéaire a binaire o _recherche par interpolation_ les algorithmes, mais personne ici ne le fait !
En outre, tous les benchmarks présentés utilisent un tableau de longueur fixe, avec un index fixe. Tout ce que cela vous dit, c'est la rapidité avec laquelle indexOf trouve cet indice exact pour cette longueur exacte - comme indiqué plus haut, on ne peut pas en tirer de généralité.
Voici le résultat de la copie du benchmark lié à la question sur perf.zone (qui est plus fiable que jsben.ch), mais avec les modifications suivantes :
https://run.perf.zone/view/for-vs-while-vs-indexof-100-integers-1516292563568
https://run.perf.zone/view/for-vs-while-vs-indexof-1000-integers-1516292665740
https://run.perf.zone/view/for-vs-while-vs-indexof-100-strings-1516297821385
https://run.perf.zone/view/for-vs-while-vs-indexof-1000-strings-1516293164213
Voici les résultats sur ma machine :
Comme vous pouvez le constater, le résultat change drastiquement en fonction du benchmark et du navigateur utilisé, et chacune des options l'emporte dans au moins un des scénarios : longueur mise en cache vs longueur non mise en cache, boucle while vs boucle for-loop vs boucle for-loop. indexOf .
Il n'y a donc pas de réponse universelle, et cela changera certainement à l'avenir, au fur et à mesure de l'évolution des navigateurs et du matériel.
Il convient de noter qu'avant de procéder à la construction de points de référence, il faut déterminer si la partie recherche linéaire est un goulot d'étranglement au départ ! Ce n'est probablement pas le cas, et si c'est le cas, la meilleure stratégie consiste probablement à utiliser une structure de données différente pour stocker et récupérer vos données de toute façon, et/ou un algorithme différent.
Cela ne veut pas dire que cette question n'est pas pertinente - elle est rare, mais il s'agit d'une question d'actualité. peut Il se trouve que la performance de la recherche linéaire est importante ; j'ai un exemple de cela : établir la vitesse de construction et de recherche dans une base de données. préfixe trie construits à l'aide d'objets imbriqués (utilisant la recherche dans le dictionnaire) ou de tableaux imbriqués (nécessitant une recherche linéaire).
Comme le montre ce commentaire github Dans le cadre de ce projet, les tests de référence impliquent diverses charges utiles réalistes et dans le meilleur et le pire des cas, sur divers navigateurs et plates-formes. Ce n'est qu'après avoir parcouru tout cela que je tire des conclusions sur les performances attendues. Dans mon cas, pour la plupart des situations réalistes, la recherche linéaire dans un tableau est plus rapide que la consultation d'un dictionnaire, mais la performance dans le pire des cas est pire au point de geler le script (et facile à construire), de sorte que l'implémentation a été marquée comme une méthode "non sûre" pour signaler aux autres qu'ils devraient réfléchir au contexte dans lequel le code serait utilisé.
Réponse de Jon J est également un bon exemple de prise de recul pour réfléchir au véritable problème.
Supposons que nous ayons fait nos devoirs et que nous ayons établi que nous devions optimiser notre recherche linéaire.
Ce qui importe alors, c'est l'index éventuel auquel nous espérons trouver notre élément (s'il y en a un), le type de données recherchées et, bien sûr, les navigateurs à prendre en charge.
En d'autres termes : tout indice a-t-il la même probabilité d'être trouvé (distribution uniforme) ou est-il plus susceptible d'être centré autour du milieu (distribution normale) ? Trouvera-t-on nos données au début ou à la fin ? Notre valeur est-elle garantie d'être dans le tableau, ou seulement un certain pourcentage du temps ? Quel pourcentage ?
Est-ce que je recherche un tableau de chaînes de caractères ? Des objets Des nombres ? S'il s'agit de nombres, s'agit-il de valeurs à virgule flottante ou d'entiers ? Essayons-nous d'optimiser l'affichage pour les anciens smartphones, les ordinateurs portables récents ou les ordinateurs de bureau de l'école équipés d'IE10 ?
C'est un autre point important : n'optimisez pas les performances dans le meilleur des cas, optimisez-les pour des performances réalistes dans le pire des cas . Si vous créez une application web pour laquelle 10 % de vos clients utilisent de très vieux téléphones intelligents, optimisez-la en conséquence ; leur expérience sera insupportable et les performances médiocres, tandis que la micro-optimisation sera gaspillée sur les téléphones phares de la dernière génération.
Posez-vous les questions suivantes sur les données auxquelles vous appliquez la recherche linéaire et sur le contexte dans lequel vous le faites. Ensuite, créez des cas de test correspondant à ces critères et testez-les sur les navigateurs/matériels qui représentent les cibles que vous soutenez.
Probablement parce que l'implémentation réelle de indexOf fait beaucoup plus que simplement boucler le tableau. Vous pouvez voir l'implémentation interne de Firefox ici :
https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf
Il y a plusieurs choses qui peuvent ralentir la boucle et qui sont là pour des raisons de sécurité :
fromIndex est transformé en un nombreMath.max au lieu d'un ternaireMath.abs
IndexOf effectue un certain nombre de vérifications de type et de validations que la boucle for et la boucle while ignorent.
Voici l'algorithme indexOf :
https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf
Edit : Je pense que indexOf est plus rapide pour les grands tableaux parce qu'il met en cache la longueur du tableau avant de le parcourir en boucle.
Exécutez le test une nouvelle fois avec les modifications que j'ai apportées.
J'ai augmenté la taille du tableau et l'index que vous recherchez. Il semble que dans les grands tableaux, indexOf soit un choix plus rapide.
EDIT : Sur la base de tests supplémentaires, indexOf semble fonctionner plus rapidement qu'une boucle for dans la version de Safari que j'utilise (5.0.3) et plus lentement dans à peu près toutes les autres versions.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
