introduction

Alors que la logique métier passe de plus en plus de l'arrière vers l'avant, l'expertise en ingénierie frontale devient de plus en plus cruciale. En tant qu'ingénieurs frontend , nous dépendons des bibliothèques de vues comme React pour être productifs. Les bibliothèques de vues dépendent à leur tour des bibliothèques d'état comme Redux pour gérer les données. Ensemble, React et Redux souscrivent au paradigme de programmation réactive dans lequel les mises à jour de l'interface utilisateur réagissent aux changements de données. De plus en plus, les backends agissent simplement comme des serveurs API, fournissant des points de terminaison uniquement pour récupérer et mettre à jour les données. En effet, le backend «transfère» simplement la base de donnéesau frontend, en attendant que l'ingénieur frontend gère toute la logique du contrôleur. La popularité croissante des microservices et de GraphQL témoigne de cette tendance croissante.

Désormais, en plus d'avoir une compréhension esthétique du HTML et du CSS, les ingénieurs frontend doivent également maîtriser JavaScript. À mesure que les banques de données sur le client deviennent des «répliques» des bases de données sur le serveur, une connaissance approfondie des structures de données idiomatiques devient essentielle. En fait, le niveau d'expérience d'un ingénieur peut être déduit de sa capacité à distinguer quand et pourquoi utiliser une structure de données particulière.

Les mauvais programmeurs s'inquiètent du code. Les bons programmeurs s'inquiètent des structures de données et de leurs relations.

- Linus Torvalds, créateur de Linux et Git

À un niveau élevé, il existe essentiellement trois types de structures de données. Les piles et les files d'attente sont des structures de type tableau qui ne diffèrent que par la manière dont les éléments sont insérés et supprimés. Listes chaînées , arbres , et les graphiques sont des structures avec des noeuds qui maintiennent des références à d' autres nœuds. Les tables de hachage dépendent des fonctions de hachage pour enregistrer et localiser les données.

En termes de complexité, Stackset Queuessont les plus simples et peuvent être construits à partir de Linked Lists. Treeset Graphssont les plus complexes car ils étendent le concept de liste chaînée. Hash Tablesbesoin d'utiliser ces structures de données pour fonctionner de manière fiable. En termes d'efficacité, les listes liées sont les plus optimales pour l' enregistrement et le stockage des données, tandis que les tables de hachage sont les plus performantes pour la recherche et la récupération de données.

Pour expliquer pourquoi et illustrer quand , cet article se conformera à l'ordre de ces dépendances. Commençons!

Empiler

Le plus important Stacken JavaScript est sans doute la pile d'appels où nous poussons dans la portée de a functionchaque fois que nous l'exécutons. Par programme, c'est juste un arrayavec deux opérations de principe: pushet pop. Push ajoute des éléments en haut du tableau, tandis que Pop les supprime du même emplacement. En d'autres termes, les piles suivent le protocole «Last In, First Out» (LIFO).

Voici un exemple de Stackcode in. Notez que nous pouvons inverser l'ordre de la pile: le bas devient le haut et le haut devient le bas. En tant que tel, nous pouvons utiliser les méthodes unshiftet les tableaux shiftà la place de pushet pop, respectivement.

Au fur et à mesure que le nombre d'éléments augmente, push/ popdevient de plus en plus performant que unshift/ shiftparce que chaque élément doit être réindexé dans ce dernier mais pas dans le premier.

Queue

JavaScript est un langage de programmation événementiel qui permet de prendre en charge des opérations non bloquantes . En interne, le navigateur gère un seul thread pour exécuter l'intégralité du code JavaScript, en utilisant la file d' attente d'événements pour mettre en file d' attentelisteners et la boucle d'événements pour écouter les inscrits events. Pour prendre en charge l'asynchronicité dans un environnement à thread unique (pour économiser les ressources du processeur et améliorer l'expérience Web), listener functions retirez la file d'attente et exécutez-la uniquement lorsque la pile d'appels est vide. Promisesdépendent de cette architecture événementielle pour permettre une exécution de «style synchrone» de code asynchrone qui ne bloque pas les autres opérations.

Par programme, ne Queuessont que des tableaux avec deux opérations principales: unshiftet pop. Unshift met les éléments en file d' attente à la fin du tableau, tandis que Pop les supprime du début du tableau. En d'autres termes, les files d'attente suivent le protocole «premier entré, premier sorti» (FIFO). Si la direction est inversée, nous pouvons remplacer unshiftet poppar pushet shift, respectivement.

Un exemple de Queuecode dans:

Liste liée

Comme les tableaux, Linked Listsstockez les éléments de données dans un ordre séquentiel . Au lieu de conserver des index, les listes liées contiennent des pointeurs vers d'autres éléments. Le premier nœud est appelé la tête tandis que le dernier nœud est appelé la queue . Dans une liste à liaison unique , chaque nœud n'a qu'un seul pointeur vers le nœud suivant . Ici, la tête est l'endroit où nous commençons notre marche sur le reste de la liste. Dans une liste à double lien , un pointeur vers le nœud précédent est également conservé. Par conséquent, nous pouvons également partir de la queue et marcher «en arrière» vers la tête.

Les listes liées ont des insertions et des suppressions à temps constant car nous pouvons simplement changer les pointeurs. Pour effectuer les mêmes opérations dans des tableaux, il faut un temps linéaire car les éléments suivants doivent être décalés. En outre, les listes liées peuvent s'agrandir tant qu'il y a de l'espace. Cependant, même les tableaux «dynamiques» qui se redimensionnent automatiquement peuvent devenir inopinément coûteux. Bien sûr, il y a toujours un compromis. Pour rechercher ou modifier un élément dans une liste liée, nous pourrions avoir à parcourir toute la longueur, ce qui équivaut au temps linéaire. Avec les index de tableau, cependant, ces opérations sont simples.

Comme les tableaux, les listes liées peuvent fonctionner comme des piles . C'est aussi simple que d'avoir la tête comme seul endroit pour l'insertion et le retrait. Les listes liées peuvent également fonctionner comme des files d' attente . Ceci peut être réalisé avec une liste à double lien, où l'insertion se produit à la queue et la suppression se produit à la tête, ou vice versa. Pour un grand nombre d'éléments, cette façon d'implémenter les files d'attente est plus performante que l'utilisation de tableaux car shiftet les unshiftopérations au début des tableaux nécessitent un temps linéaire pour réindexer chaque élément suivant.

Les listes liées sont utiles à la fois sur le client et sur le serveur. Sur le client, les bibliothèques de gestion d'état comme Redux structurent sa logique middleware dans un mode de liste chaînée. Lorsque les actions sont distribuées, elles sont acheminées d'un middleware au suivant jusqu'à ce que tout soit visité avant d'atteindre les réducteurs . Sur le serveur, les frameworks Web comme Express structurent également sa logique middleware de la même manière. Lorsqu'une demande est reçue, elle est acheminée d'un middleware au suivant jusqu'à ce qu'une réponse soit émise.

Un exemple de Doubly-Linked Listcode dans:

Arbre

A Treeest comme une liste chaînée , sauf qu'il garde des références à de nombreux nœuds enfants dans une structure hiérarchique . En d'autres termes, chaque nœud ne peut avoir plus d'un parent. Le modèle d'objet de document (DOM) est une telle structure, avec un htmlnœud racine qui se ramifie dans les nœuds headet body, qui se subdivisent davantage en toutes les balises HTML familières . Sous le capot, l' héritage et la composition prototypiques avec les composants React produisent également des structures arborescentes. Bien sûr, en tant que représentation en mémoire du DOM, le DOM virtuel de React est également une structure arborescente.

L' arbre de recherche binaire est spécial car chaque nœud ne peut pas avoir plus de deux enfants . L' enfant gauche doit avoir une valeur inférieure ou égale à son parent, tandis que l' enfant droit doit avoir une valeur supérieure . Structuré et équilibré de cette manière, nous pouvons rechercher n'importe quelle valeur en temps logarithmique car nous pouvons ignorer la moitié du branchement à chaque itération. L'insertion et la suppression peuvent également se produire en temps logarithmique. De plus, la valeur la plus petite et la plus grande peut facilement être trouvée sur la feuille la plus à gauche et la plus à droite , respectivement.

La traversée de l'arbre peut se produire selon une procédure verticale ou horizontale . En profondeur d'abord (DFT) dans la direction verticale, un algorithme récursif est plus élégant qu'un algorithme itératif. Les nœuds peuvent être traversés en pré-commande , en ordre ou en post-ordre . Si nous devons explorer les racines avant d'inspecter les feuilles, nous devons choisir la pré-commande . Mais, si nous devons explorer les feuilles avant les racines, nous devons choisir la post-commande . Comme son nom l'indique, dans l'ordre nous permet de parcourir les nœuds dans un ordre séquentiel . Cette propriété rend les arbres de recherche binaires optimaux pour le tri .

Dans la traversée en largeur d'abord (BFT) dans la direction horizontale, une approche itérative est plus élégante qu'une approche récursive. Cela nécessite l'utilisation de a queuepour suivre tous les nœuds enfants à chaque itération. La mémoire nécessaire pour une telle file d'attente n'est peut-être pas triviale, cependant. Si la forme d'un arbre est plus large que profonde, le BFT est un meilleur choix que le DFT. De plus, le chemin emprunté par BFT entre deux nœuds est le plus court possible.

Un exemple de Binary Search Treecode dans:

Graphique

Si un arbre est libre d'avoir plus d'un parent, il devient un Graph. Les arêtes qui relient les nœuds dans un graphique peuvent être dirigées ou non, pondérées ou non pondérées . Les arêtes qui ont à la fois une direction et un poids sont analogues aux vecteurs .

Les héritages multiples sous la forme de mixins et d'objets de données qui ont des relations plusieurs à plusieurs produisent des structures de graphes. Un réseau social et Internet lui-même sont également des graphiques. Le graphique le plus compliqué dans la nature est notre cerveau humain, que les réseaux de neurones tentent de reproduire pour donner aux machines une superintelligence .

Un exemple de Graphcode dans:

TK

Table de hachage

Une table de hachage est une structure de type dictionnaire qui associe des clés à des valeurs . L'emplacement en mémoire de chaque paire est déterminé par a hash function, qui accepte une clé et renvoie l' adresse où la paire doit être insérée et récupérée. Des collisions peuvent survenir si deux clés ou plus sont converties en la même adresse. Pour plus de robustesse, getterset settersdoit anticiper ces événements pour s'assurer que toutes les données peuvent être récupérées et qu'aucune donnée n'est écrasée. Offrez généralement linked listsla solution la plus simple. Avoir de très grandes tables aide également.

Si nous savons que nos adresses seront dans des séquences d'entiers, nous pouvons simplement les utiliser Arrayspour stocker nos paires clé-valeur. Pour des mappages d'adresses plus complexes, nous pouvons utiliser Mapsou Objects. Les tables de hachage ont une insertion et une recherche de temps constant en moyenne. En raison des collisions et du redimensionnement, ce coût négligeable pourrait devenir linéaire. En pratique, cependant, nous pouvons supposer que les fonctions de hachage sont suffisamment intelligentes pour que les collisions et le redimensionnement soient rares et bon marché. Si les clés représentent des adresses et qu'aucun hachage n'est donc nécessaire, un simple object literalpeut suffire. Bien sûr, il y a toujours un compromis. La simple correspondance entre les clés et les valeurs, et la simple associativité entre les clés et les adresses sacrifient les relations entre les données. Ainsi, les tables de hachage ne sont pas optimales pour le stockage des données.

Si une décision de compromis favorise la récupération par rapport au stockage, aucune autre structure de données ne peut égaler la vitesse des tables de hachage pour la recherche , l' insertion et la suppression . Il n'est donc pas surprenant qu'il soit utilisé partout . De la base de données au serveur, en passant par le client, les tables de hachage , et en particulier les fonctions de hachage , sont essentielles pour les performances et la sécurité des applications logicielles. La vitesse des requêtes de base de données dépend fortement de la conservation des tables d' index qui pointent vers les enregistrements dans un ordre trié . De cette façon, les recherches binaires peuvent être effectuées en temps logarithmique , un gain de performances énorme, en particulier pour le Big Data .

Sur le client et le serveur, de nombreuses bibliothèques populaires utilisent la mémorisation pour maximiser les performances. En conservant un enregistrement des entrées et des sorties dans une table de hachage, les fonctions ne s'exécutent qu'une seule fois pour les mêmes entrées. La bibliothèque populaire Reselect utilise cette stratégie de mise en cache pour optimiser les mapStateToPropsfonctions dans les applications compatibles Redux . En fait, sous le capot, le moteur JavaScript utilise également des tables de hachage appelées tas pour stocker tout ce variablesque primitivesnous créons. Ils sont accessibles à partir de pointeurs sur la pile d'appels .

L' Internet lui - même repose également sur des algorithmes de hachage pour fonctionner en toute sécurité. La structure d'Internet est telle que n'importe quel ordinateur peut communiquer avec n'importe quel autre ordinateur via un réseau d'appareils interconnectés. Chaque fois qu'un appareil se connecte à Internet, il devient également un routeur à travers lequel les flux de données peuvent voyager. Cependant, c'est une épée à double tranchant. Une architecture décentralisée signifie que tout appareil du réseau peut écouter et altérer les paquets de données qu'il aide à relayer. Les fonctions de hachage telles que MD5 et SHA256 jouent un rôle essentiel dans la prévention de telles attaques de type " man-in-the-middle" . Le commerce électronique sur HTTPS n'est sûr que parce que ces fonctions de hachage sont utilisées.

Inspirées d'Internet, les technologies de la blockchain cherchent à open source la structure même du web au niveau du protocole . En utilisant des fonctions de hachage pour créer des empreintes digitales immuables pour chaque bloc de données , la base de données entière peut essentiellement exister ouvertement sur le Web pour que quiconque puisse la voir et y contribuer. Structurellement, les blockchains ne sont que des listes à lien unique d'arbres binaires de hachages cryptographiques. Le hachage est tellement cryptique qu'une base de données de transactions financières peut être créée et mise à jour à l'air libre par n'importe qui! L'implication incroyable est le pouvoir impressionnant de créer de l' argent lui-même. Ce qui n'était autrefois possible que pour les gouvernements et les banques centrales, tout le monde peut désormais créer en toute sécurité sa propre monnaie ! C'est la vision clé réalisée par le fondateur d' Ethereum et le fondateur pseudonyme de Bitcoin .

Au fur et à mesure que de plus en plus de bases de données se déplacent à l'air libre, le besoin d'ingénieurs frontaux capables d'abstraire toutes les complexités cryptographiques de bas niveau s'aggravera également. Dans ce futur, le principal différenciateur sera l' expérience utilisateur .

Un exemple de Hash Tablecode dans:

Pour des exercices d'algorithmes utilisant ces structures de données et plus, consultez: Algorithmes en JavaScript: 40 problèmes, solutions et explications

Conclusion

À mesure que la logique passe de plus en plus du serveur au client, la couche de données sur le frontend devient primordiale. La bonne gestion de cette couche passe par la maîtrise des structures de données sur lesquelles repose la logique. Aucune structure de données n'est parfaite pour chaque situation car l'optimisation d'une propriété équivaut toujours à en perdre une autre. Certaines structures sont plus efficaces pour stocker des données tandis que d'autres sont plus performantes pour les rechercher. Habituellement, l'un est sacrifié pour l'autre. À un extrême, les listes liées sont optimales pour le stockage et peuvent être transformées en piles et en files d'attente ( temps linéaire ). De l'autre, aucune autre structure ne peut égaler la vitesse de recherche des tables de hachage ( temps constant ). Les structures arborescentes se trouvent quelque part au milieu ( temps logarithmique ), et seul un graphique peut représenter la structure la plus complexe de la nature: le cerveau humain ( temps polynomial ). Avoir les compétences nécessaires pour distinguer quand et expliquer pourquoi est une caractéristique d'un ingénieur rockstar.

Des exemples de ces structures de données peuvent être trouvés partout . De la base de données, au serveur, au client, et même le moteur JavaScript lui - même, ces structures de données essentiellement ce sont concrétisent juste sur et hors « interrupteurs » sur des puces de silicium dans des « objets » réalistes. Bien qu'ils soient uniquement numériques, l'impact de ces objets sur la société est énorme. Votre capacité à lire cet article librement et en toute sécurité atteste de la formidable architecture d'Internet et de la structure de ses données. Pourtant, ce n'est que le début. L'intelligence artificielle et les blockchains décentralisées dans les décennies à venir redéfiniront ce que signifie être humain et le rôle des institutions qui gouvernent nos vies. Les perspectives existentielles et la désintermédiation institutionnelle seront les caractéristiques d'un Internet qui a finalement mûri.

Pour nous aider à faire la transition vers cet avenir plus équitable, chez HeartBank® , nous canalisons les réseaux de neurones artificiels pour donner à nos Kiitos le pouvoir d'émettre de l'argent sur la blockchain, associé à la capacité de faire preuve d'empathie envers la condition humaine. À partir des remerciements anonymes que nous donnons et recevons en écrivant à Kiitos , Kiitos apprend nos bienfaits et leurs effets , nous récompensant d'une manière qui réduit les inégalités économiques entre nous, dans un processus graduel et mystérieux qui préserve notre liberté et notre liberté personnelles. Peut-être que la structure graphique ultime dans la nature n'est pas le cerveau humain, mais l'humain ❤️, si seulement nous pouvons voir les cordes sensibles qui nous relient tous.

Intéressé par la blockchain ? Apprenez Ethereum et venez travailler pour nous!