Je pense que sur Habré, il y a des fans de la série Silicon Valley . Cette semaine, pour la première fois en six saisons, ils ont montré un grand code - bien sûr, je veux immédiatement en discuter ici.
Voulant humilier le personnage principal Richard Hendrix, son ancien patron montre lors d'une réunion un fragment de son ancien code. Là, une recherche linéaire est appliquée aux données déjà triées - la tâche sera donc terminée, mais elle semble très inefficace.
Richard lui-même ne prétend pas que le code est mauvais. Cependant, parmi les téléspectateurs de la série, sa décision a soudainement trouvé des défenseurs, et maintenant je me demande ce que Habr pense de leur position.
L'extrait de code connu de Richard ressemble à ceci:
int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1;
Ici, une recherche linéaire se tourne à son tour vers chaque élément d'une liste triée, jusqu'à ce qu'il arrive à la bonne. En règle générale, ils préfèrent la recherche binaire sur les données triées, qui divisent à chaque fois l'ensemble en deux, rejetant la moitié inappropriée dans son ensemble (car avec une augmentation du volume de données, le nombre d'itérations dans le linéaire augmente beaucoup plus rapidement que dans le binaire). Mais dans le subreddit / r / SiliconValleyHBO, le commentaire suivant est apparu:
«Je veux étudier un peu et souligner que« l'erreur »de Richard en utilisant la recherche linéaire au lieu de la recherche binaire sur des données triées s'avère en fait être plus productive dans de nombreux cas. Avec des ensembles de données géants (je pense que le seuil est sur des millions d'éléments), la recherche binaire est plus rapide. Mais en général, si votre ensemble de données n'est pas gigantesque, une recherche linéaire sera mieux mise en cache par le processeur, mieux adaptée au prédicteur de branche, et votre algorithme peut également être vectorisé. Les recherches linéaires nécessitent plus d'itérations, mais chacune est incroyablement plus rapide qu'une itération de recherche binaire. C'est contre-intuitif et contredit tout ce qu'on vous a enseigné à l'université, mais ça l'est.
Ce rapport est très intéressant et montre des résultats étonnants de mesures de performances réelles. »
Et d'autres membres du fil ont soutenu le commentateur: oui, en théorie, toutes les itérations sont équivalentes, mais sur du vrai matériel avec de réelles optimisations, tout est complètement différent. Comme, le créateur de la série, Mike Judge, a travaillé dans la vallée dans les années 80, lorsque tous ces caches L1 et la prédiction de branche n'étaient pas encore particulièrement prononcés, de sorte que le comportement du processeur était beaucoup plus proche du modèle idéal - c'est un exemple de la série.
Pour moi, comme le dit le commentaire, tout cela semble contre-intuitif, mais il est devenu intéressant de savoir si Richard pouvait avoir raison. Bien sûr, cela interfère avec le fait que tout le contexte n'est pas donné dans la série: par exemple, nous n'avons aucune idée de la quantité de données itérée. D'une part, Richard a ensuite travaillé pour le géant de l'Internet Hooli, où il devait probablement gérer des millions d'enregistrements, mais d'autre part, c'était son premier jour ouvrable, et il ne pouvait pas être immédiatement déversé en millions. Nous posons la question de cette façon: même si la recherche binaire est clairement meilleure pour la plupart des tâches dans Hooli, est-il probable que Richard ait pris la bonne décision pour ses conditions et que d'autres personnages se moquent de lui en vain, ne connaissant pas le contexte?
Pour comprendre, j'ai ouvert un rapport cité par Reddit. Comme promis, cela s'est avéré intéressant (pas surprenant, étant donné qu'il s'agit d'un rapport d' Andrei Alexandrescu ), mais après avoir regardé une partie et cliqué sur le reste, je n'y ai pas vu de mesures comparatives de recherche binaire et linéaire.
Mais je me suis souvenu qu'à notre conférence DotNext, le même Alexandrescu avait également parlé de performance. J'ai ouvert la version texte de son rapport, que nous avons faite pour Habr, et j'ai cherché le mot "linéaire". Il s'est avéré, entre autres, qu'il donnait juste un exemple d'un scénario curieux dans lequel cette recherche serait beaucoup plus efficace qu'une recherche binaire (recherche d'éléments correspondants de deux ensembles dans le cas où ces ensembles sont identiques) - mais c'est un cas très spécifique, pour lequel il n'y a pas de conclusion générale " la recherche linéaire est sous-estimée. "
Googlé ce que l'Internet moderne dit à ce sujet - mais a essentiellement trouvé des réponses à Stack Overflow, où ils écrivent simplement «utilisez le binaire, moins d'itérations». Il y a aussi eu des cas où ils ont essayé de se comparer, mais qui ne m'ont pas semblé très convaincants.
Ici, bien sûr, l'option prie "vous devez vous évaluer afin de tout voir vous-même sur du vrai matériel".
Mais si pour toutes mes visites à DotNext, j'ai appris quelque chose de deux Andreev soucieux de la performance (Alexandrescu et Akinshina ), c'est une prise de conscience de la fréquence à laquelle les gens comparent incorrectement et de combien ils ne prennent pas en compte. Par conséquent, j'ai une faible confiance dans les publications Internet aléatoires avec des repères, mais pour moi-même encore plus bas.
Heureusement, il y a des gens sur Habr qui comprennent beaucoup plus que moi (par exemple, le même Andrey DreamWalker Akinshin, qui a écrit un livre entier sur l'analyse comparative). Par conséquent, si vous comprenez le sujet - veuillez nous dire dans les commentaires comment tout est vraiment. À quelle taille de données une approche linéaire peut-elle toujours être un bon choix? Quelle est la probabilité que Richard ait tout fait correctement, même si lui-même n'est pas prêt à le défendre?
Et s'il n'y a pas de commentateurs avertis, je devrai attacher Akinshin à la batterie du prochain DotNext et faire le test.