Une introduction aux algorithmes et aux structures de données (Javascript Edition)

Introduction

Comprendre les algorithmes et les structures de données est crucial pour améliorer vos performances 10 fois plus que vos pairs qui ne le font pas. En effet, vous analysez les problèmes de manière critique et concevez les meilleurs moyens de les résoudre. Cela peut signifier accélérer les délais de requête du serveur ou trouver le meilleur moyen de stocker de grands ensembles de données avec un espace disque minimal.

Cet article vise à vous aider à comprendre les concepts de base des algorithmes et des structures de données et comment les mettre en œuvre à l'aide de JavaScript.

Qu'est-ce qu'un algorithme ? Un algorithme est un ensemble d'instructions étape par étape pour accomplir une tâche. Supposons que vous ayez du mal à vous réveiller tôt et que vous ne respectiez pas les échéances. Comment résolvez-vous cela? Ah ! Réglez les alarmes. Voilà à quoi ressemble un algorithme.

Les structures de données, en revanche, sont des moyens de stocker efficacement les données.

Les structures de données et les algorithmes (DSA) sont si vitaux qu'ils sont essentiels à la performance globale d'un ordinateur. L'algorithme que vous choisirez déterminera son temps d'exécution (Big O Notation) ou son efficacité. Certains DSA populaires sont la recherche binaire, la récursivité, le tri, les tableaux, les listes chaînées et les tables de hachage.

Qu'est-ce que la recherche binaire ?

Supposons que vous recherchiez un nom dans l'annuaire d'un pays ; il commence par un J. Vous pouvez commencer par le début (à partir des pays "A") et continuer à tourner les pages jusqu'à ce que vous arriviez à la liste des pays "J" (ces pays sont triés par ordre alphabétique). Si le pays commence par un "Z", alors vous continuez à retourner à la fin du répertoire. C'est ce qu'on appelle un algorithme de recherche simple. Mais imaginez s'il s'agissait d'un annuaire téléphonique avec plus de 100 000 numéros de téléphone, c'est incroyablement difficile. Comment optimisez-vous cela ? Recherche binaire à la rescousse.

L'algorithme de recherche binaire prend une liste triée d'éléments en entrée, et si l'élément que vous recherchez est dans la liste, la recherche binaire renvoie la position où il se trouve, sinon elle renvoie null. Au lieu d'aller étape par étape pour se rendre au Japon, la recherche binaire divise ce tableau en plusieurs parties et recherche chacune d'elles en conséquence.

De cette façon, la recherche est rapide.

Tableaux

Ils sont une collection d'éléments indexés par une clé. Les éléments du tableau sont stockés séquentiellement, la clé servant d'identifiant dans la collection. Ses index commencent par 0.

Ils sont super utiles car récupérer ou trier n'importe quel élément prend un temps constant O(1). il peut également être utilisé pour implémenter de nombreuses autres structures de données qui imposent des restrictions supplémentaires sur la manière dont les données sont manipulées. Une chaîne, par exemple, peut être implémentée sous la forme d'un tableau de caractères.

Voici une implémentation des tableaux et de la recherche binaire en JavaScript.

 function binary_search(list, item) { let guess = list.find(element => element == item); if (guess) { return guess + "\ncountry index no: " + list.findIndex(country => country === guess); } return null + ": element is not in the array" } console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109 console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array

Algorithme de tri

Le tri est rarement utilisé par les programmeurs. Il est principalement déjà géré par le langage ou les bibliothèques dans lesquels ils codent. Le langage JavaScript, par exemple, trie les tableaux à l'aide du tri par insertion, du tri par tas ou du tri rapide.

Heapsort est similaire à la méthode Javascript array-filter. Il divise l'entrée en une région triée et une région non triée et déplace de manière itérative les éléments vers la région triée. Voici un exemple;

Liste liée

Une liste chaînée est une structure de données dans laquelle chaque élément contient à la fois des données et un pointeur vers l'élément suivant de la liste. Une caractéristique distinctive d'une liste chaînée est que ses éléments peuvent être dispersés n'importe où dans la mémoire. Ce n'est pas vrai pour les tableaux. Voir quelques exemples ci-dessous ;

Que sont les tables de hachage ?

Les tables de hachage sont des listes d'éléments arbitraires dans un tableau. L'élément à stocker ou sa clé est utilisé comme index dans le tableau. Voici un exemple:

La fonction de hachage convertit la clé des éléments à placer en un hachage, puis mappe les éléments hachés à un endroit spécifié dans la table. Chacun de ces éléments peut également être un sous-tableau d'éléments arbitraires dans le tableau.

Récursivité

La récursivité est une technique de codage utilisée dans de nombreux autres algorithmes. C'est un raccourci vers un code long et peut n'offrir aucun gain de performances, sauf pour le programmeur.

Supposons que vous trouviez une valise au trésor. Pour déverrouiller ce boîtier, vous devez saisir une clé dans une boîte avec d'autres boîtes plus petites, qui peuvent encore contenir d'autres boîtes.

Une approche consiste à dresser une liste de cases à parcourir, puis à parcourir chacune de ces cases. Si vous trouvez une clé, tant mieux ! Si ce n'est pas le cas, ajoutez la nouvelle case vide à la liste des piles pour effectuer une recherche ultérieure.

La récursivité supprime l'étape où vous ajoutez la nouvelle boîte vide trouvée à une liste de recherche. Il appelle immédiatement la méthode de recherche sur la nouvelle case trouvée vide. Voici un exemple en Javascript ;

 const suitCase = new Map(); suitCase.set('box-0', '') .set('box-1', '') .set('box-2', '') .set('box-3', '') .set('box-4', 'key') .set('box-5', '') .set('box-6', ''); function search (suit) { for (let [key, value] of suit) { if (value === 'key') { console.log(`Found ${value} at ${key}!`); } } } search(suitCase); // prints Found key at box-4!

Tu as trouvé la clé, Tada !

En résumé, DSA est un excellent moyen de penser efficacement en tant que programmeur. Il vous donne des outils pour résoudre des problèmes difficiles. Cliquez sur le lien du référentiel GitHub pour télécharger tous les extraits de code utilisés dans cet article. Bon piratage !

Référentiel de code GitHub