Share
Cet article va plonger dans les principes de la conception d'algorithmes. Si vous ne savez pas de quoi je parle, lisez la suite!
Lorsque vous entendez le mot "algorithme", vous répondez probablement de l'une des trois manières suivantes:
Si vous êtes l'un des deux autres, cet article est pour vous.
Les algorithmes ne sont pas nécessairement un type d'opération particulier. Ils sont conceptuels, un ensemble d'étapes que vous prenez en code pour atteindre un objectif spécifique.
Les algorithmes ont été généralement définis en termes simples comme des "instructions pour mener à bien une tâche". Ils ont également été appelé "recettes". Dans Le réseau social, Zuckerberg avait besoin d'un algorithme pour faire fonctionner Facemash. Si vous avez vu le film, vous vous souvenez probablement d'avoir vu ce qui ressemblait à une équation scribable sur une fenêtre dans le dortoir de Mark. Mais qu'est-ce que cette algèbre scribbly a à voir avec le simple site "chaud ou pas" de Mark?
Les algorithmes sont bien des instructions. Peut-être une description plus précise serait que les algorithmes sont des modèles permettant de mener à bien une tâche de manière efficace. Facemash de Zuckerberg était un site de vote permettant de déterminer l'attractivité d'une personne par rapport à un groupe entier de personnes, mais l'utilisateur ne pouvait choisir que deux personnes. Mark Zuckerberg avait besoin d'un algorithme permettant de déterminer les personnes à comparer, ainsi que la valeur d'un vote par rapport à l'historique et aux concurrents précédents de cette personne. Cela demandait plus d'intuition que de simplement compter les votes pour chaque personne.
Par exemple, supposons que vous vouliez créer un algorithme pour ajouter 1 à un nombre négatif, soustraire 1 à un nombre positif et ne rien faire à 0. Vous pourriez faire quelque chose comme ça (dans le pseudo-code JavaScript-esque):
fonction addOrSubtractOne (nombre) if (nombre < 0) return number + 1 else if (number < 0) return number - 1 else if (number == 0) return 0;
Vous vous dites peut-être: "C'est une fonction." Et tu as raison. Les algorithmes ne sont pas nécessairement un type d'opération particulier. Ils sont conceptuels - un ensemble d'étapes que vous prenez en code pour atteindre un objectif spécifique.
Alors pourquoi sont-ils un gros problème? De toute évidence, ajouter ou soustraire 1 à un nombre est une chose assez simple à faire.
Mais parlons une seconde de la recherche. Pour rechercher un nombre dans un tableau de nombres, comment penseriez-vous le faire? Une approche naïve consisterait à parcourir le nombre, en comparant chaque nombre à celui que vous recherchez. Cependant, cette solution n'est pas efficace et offre une très large gamme de temps de traitement possibles, ce qui en fait une méthode de recherche erratique et peu fiable lorsqu'elle est adaptée à de grands ensembles de recherche..
fonction naiveSearch (aiguille, meule de foin) pour (var i = 0; i < haystack.length; i++) if (haystack[i] == needle) return needle; return false;
Heureusement, nous pouvons faire mieux que cela pour la recherche.
Il n'y a pas de meilleur moyen de devenir un meilleur concepteur d'algorithmes que d'avoir une compréhension et une appréciation approfondies des algorithmes..
Supposons que votre tableau compte 50 000 entrées et que vous effectuiez une recherche brutale (c’est-à-dire une recherche en effectuant une itération du tableau complet). L'entrée que vous recherchez, dans le meilleur des cas, sera la première entrée du tableau de 50 000 entrées. Dans le pire des cas, toutefois, l'algorithme prendra 50 000 fois plus de temps que dans le meilleur des cas..
Au lieu de cela, vous rechercheriez en utilisant la recherche binaire. Cela implique de trier le tableau (que je vais vous laisser apprendre par vous-même), de diviser ensuite le tableau en deux et de vérifier si le numéro de recherche est supérieur ou inférieur au repère de moitié du tableau. S'il est supérieur à la moitié du tableau d'un tableau trié, nous savons que la première moitié peut être ignorée, car le nombre recherché ne fait pas partie du tableau. Nous pouvons également faire beaucoup de travail en définissant les limites extérieures du tableau et en vérifiant si le nombre recherché existe en dehors de ces limites, et si c'est le cas, nous avons pris ce qui aurait été une opération à itérations multiples et l'a transformé. en une seule opération d'itération (ce qui, dans l'algorithme de force brute, aurait nécessité 50 000 opérations).
triéHaystack = recursiveSort (haystack); fonction bSearch (aiguille, sortHaystack, firstIteration) if (firstIteration) if (aiguille> sortHaystack.last || aiguille) < sortedHaystack.first) return false; if (haystack.length == 2) if (needle == haystack[0]) return haystack[0]; else return haystack[1]; if (needle < haystack[haystack.length/2]) bSearch(needle, haystack[0… haystack.length/2 -1], false); else bSearch(needle, haystack[haystack.length/2… haystack.length], false);
Prenez la nature apparemment compliquée d'un algorithme de recherche binaire unique et appliquez-le à des milliards de liens possibles (comme dans Google). Au-delà de cela, appliquons une sorte de système de classement à ces recherches liées pour donner un ordre des pages de réponses. Mieux encore, appliquez une sorte de système de "suggestion" apparemment aléatoire basé sur des modèles sociaux d'intelligence artificielle conçus pour identifier les personnes que vous souhaitez ajouter en tant qu'ami..
Cela nous donne une compréhension beaucoup plus claire de la raison pour laquelle les algorithmes sont plus qu'un simple nom sophistiqué pour les fonctions. À leur meilleur, ce sont des moyens intelligents et efficaces de faire quelque chose qui nécessite un niveau d'intuition supérieur à celui de la solution la plus apparente. Ils peuvent prendre ce qui pourrait nécessiter des années de supercalculateur et en faire une tâche qui se termine en quelques secondes sur un téléphone portable.
Pour la plupart des développeurs, nous ne concevons pas quotidiennement des algorithmes abstraits de haut niveau..
Heureusement, nous sommes sur les épaules des développeurs qui nous ont précédés, qui ont écrit des fonctions de tri natives et nous permettent de rechercher des chaînes avec des chaînes avec indexOf de manière efficace..
Mais nous, cependant, traitons avec nos propres algorithmes. Nous créons pour des boucles et écrit des fonctions tous les jours; alors comment de bons principes de conception d'algorithmes peuvent-ils informer l'écriture de ces fonctions?
L'un des principes fondamentaux de la conception algorithmique est, si possible, de construire votre algorithme de telle sorte que l'entrée elle-même effectue une partie du travail à votre place. Par exemple, si vous savez que votre entrée sera toujours un nombre, vous n'avez pas besoin d'exceptions / contrôles pour les chaînes, ni de contraindre vos valeurs en nombres. Si vous savez que votre élément DOM est identique à chaque fois dans un pour boucle en JavaScript, vous ne devriez pas interroger cet élément à chaque itération. De même, dans votre pour boucles, vous ne devriez pas utiliser de fonctions pratiques avec surcharge si vous pouvez accomplir la même chose en utilisant (plus près) des opérations simples.
Accentsconagua
// ne fait pas ceci: pour (var i = 1000; i> 0; i -) $ ("# foo"). append ("bar"); // faites ceci à la place var foo = $ (" # foo "); var s =" "; pour (var i = 1000; i> 0; i -) s + ="bar"; foo.append (s); Si vous êtes un développeur JavaScript (et que vous utilisez jQuery) et que vous ne savez pas ce que font les fonctions ci-dessus et en quoi elles sont très différentes, le point suivant est pour vous..
À leur meilleur, les [algorithmes] sont des moyens intelligents et efficaces de faire quelque chose qui nécessite un niveau d'intuition plus élevé que la solution la plus apparente..
Il est facile de penser que cela va sans dire. Cependant, il existe une différence entre "savoir écrire jQuery" et "comprendre jQuery". Comprendre vos outils signifie que vous comprenez le rôle de chaque ligne de code, à la fois immédiatement (valeur de retour d'une fonction ou effet d'une méthode) et implicitement (combien de temps système est associé à l'exécution d'une fonction de bibliothèque ou quelle est la méthode la plus efficace. méthode pour concaténer une chaîne). Pour écrire de bons algorithmes, il est important de connaître les performances des fonctions ou des utilitaires de bas niveau, et pas seulement leur nom et leur implémentation..
Concevoir des algorithmes efficaces est un engagement total. Au-delà de la compréhension de vos outils en tant qu'élément autonome, vous devez également comprendre la manière dont ils interagissent avec le système plus vaste dont vous disposez. Par exemple, pour comprendre entièrement JavaScript dans une application spécifique, il est important de comprendre le DOM et les performances de JavaScript dans des scénarios inter-navigateurs, l'impact de la mémoire disponible sur les vitesses de rendu, la structure des serveurs (et leurs réponses) avec lesquels vous pouvez interagir, ainsi qu'une multitude d'autres considérations intangibles, telles que les scénarios d'utilisation.
En général, l'objectif de la conception d'algorithmes est de terminer un travail en moins d'étapes. (Il existe quelques exceptions, telles que le hachage Bcrypt.) Lorsque vous écrivez votre code, prenez en compte tout des opérations simples que l'ordinateur prend pour atteindre l'objectif. Voici une simple liste de contrôle pour vous lancer sur la voie d'une conception d'algorithme plus efficace:
Il n'y a pas de meilleur moyen de devenir un meilleur concepteur d'algorithmes que d'avoir une compréhension et une appréciation approfondies des algorithmes..
.Trier(), avec des opérations de niveau inférieur. Si vous ne saviez pas ce qu'est un algorithme au début de cet article, j'espère maintenant que vous avez une compréhension plus concrète du terme un peu difficile à comprendre. En tant que développeurs professionnels, il est important que nous comprenions que le code que nous écrivons peut être analysé et optimisé, et qu'il est important que nous prenions le temps de procéder à cette analyse des performances de notre code..
Avez-vous trouvé des problèmes de pratique d'algorithmes amusants? Peut-être une programmation dynamique "problème de sac à dos", ou "promenade ivre"? Ou peut-être connaissez-vous certaines des meilleures pratiques de récurrence en Ruby qui diffèrent des mêmes fonctions que celles implémentées en Python. Partagez-les dans les commentaires!
