introduzione

Man mano che la logica aziendale si sposta sempre di più dalla parte posteriore in avanti, la competenza in Frontend Engineering diventa sempre più cruciale. In qualità di ingegneri frontend , dipendiamo da librerie di visualizzazioni come React per essere produttivi. Le librerie di visualizzazione a loro volta dipendono dalle librerie di stato come Redux per la gestione dei dati. Insieme, React e Redux sottoscrivono il paradigma di programmazione reattiva in cui gli aggiornamenti dell'interfaccia utente reagiscono alle modifiche dei dati. Sempre più spesso, i backend agiscono semplicemente come server API, fornendo endpoint solo per recuperare e aggiornare i dati. In effetti, il backend si limita a "inoltrare" il databaseal frontend, aspettandosi che l'ingegnere frontend gestisca tutta la logica del controller. La crescente popolarità dei microservizi e di GraphQL testimonia questa tendenza in crescita.

Ora, oltre ad avere una comprensione estetica di HTML e CSS, ci si aspetta che gli ingegneri frontend padroneggino anche JavaScript. Man mano che i datastore sul client diventano "repliche" dei database sul server, la conoscenza approfondita delle strutture dati idiomatiche diventa fondamentale. In effetti, il livello di esperienza di un ingegnere può essere dedotto dalla sua capacità di distinguere quando e perché utilizzare una particolare struttura dati.

I cattivi programmatori si preoccupano del codice. I bravi programmatori si preoccupano delle strutture dei dati e delle loro relazioni.

- Linus Torvalds, creatore di Linux e Git

Ad un livello elevato, esistono fondamentalmente tre tipi di strutture dati. Le pile e le code sono strutture simili a matrici che differiscono solo per il modo in cui gli elementi vengono inseriti e rimossi. Liste collegate , alberi , e grafici sono strutture con i nodi che mantengono riferimenti ad altri nodi. Le tabelle hash dipendono dalle funzioni hash per salvare e individuare i dati.

In termini di complessità, Stackse Queuessono i più semplici e possono essere costruiti Linked Lists. Treese Graphssono le più complesse perché estendono il concetto di lista concatenata. Hash Tablesè necessario utilizzare queste strutture di dati per funzionare in modo affidabile. In termini di efficienza, gli elenchi collegati sono i più ottimali per la registrazione e l' archiviazione dei dati, mentre le tabelle hash sono più performanti per la ricerca e il recupero dei dati.

Per spiegare perché e illustrare quando , questo articolo sarà conforme all'ordine di queste dipendenze. Cominciamo!

Pila

Probabilmente il più importante Stackin JavaScript è lo stack di chiamate in cui inseriamo nell'ambito di a functionogni volta che lo eseguiamo. A livello di codice, è solo un arraycon due operazioni di principio: pushe pop. Push aggiunge elementi in cima all'array, mentre Pop li rimuove dalla stessa posizione. In altre parole, gli stack seguono il protocollo "Last In, First Out" (LIFO).

Di seguito è riportato un esempio di Stackin code. Notare che possiamo invertire l'ordine della pila: il fondo diventa il massimo e il massimo diventa il fondo. Pertanto, possiamo utilizzare i metodi unshifte dell'array shiftal posto di pushe pop, rispettivamente.

Man mano che il numero di elementi cresce, push/ popdiventa sempre più performante di unshift/ shiftperché ogni elemento deve essere reindicizzato in quest'ultimo ma non nel primo.

Coda

JavaScript è un linguaggio di programmazione basato sugli eventi che consente di supportare operazioni non bloccanti . Internamente, il browser gestisce solo un thread per eseguire l'intero codice JavaScript, utilizzando la coda degli eventi per accodarelisteners e il ciclo di eventi per ascoltare per la sede events. Per supportare l'asincronicità in un ambiente a thread singolo (per risparmiare risorse della CPU e migliorare l'esperienza web), listener functions rimuovi dalla coda ed esegui solo quando lo stack di chiamate è vuoto. Promisesdipendono da questa architettura basata sugli eventi per consentire un'esecuzione in "stile sincrono" di codice asincrono che non blocchi altre operazioni.

A livello di codice, Queuessono solo array con due operazioni principali: unshifte pop. Unshift accoda gli elementi alla fine dell'array, mentre Pop li rimuove dall'inizio dell'array. In altre parole, le code seguono il protocollo FIFO (First In, First Out). Se la direzione è invertita, possiamo sostituire unshifte popcon pushe shift, rispettivamente.

Un esempio di Queuein codice:

Lista collegata

Come gli array, Linked Listsmemorizza gli elementi di dati in ordine sequenziale . Invece di mantenere gli indici, gli elenchi collegati contengono puntatori ad altri elementi. Il primo nodo è chiamato la testa mentre l' ultimo nodo è chiamato la coda . In un elenco collegato singolarmente , ogni nodo ha un solo puntatore al nodo successivo . Qui, la testa è dove iniziamo la nostra passeggiata lungo il resto della lista. In un elenco a doppio collegamento , viene mantenuto anche un puntatore al nodo precedente . Pertanto, possiamo anche partire dalla coda e camminare "all'indietro" verso la testa.

Gli elenchi collegati hanno inserimenti e cancellazioni a tempo costante perché possiamo semplicemente cambiare i puntatori. Per eseguire le stesse operazioni negli array è necessario un tempo lineare perché gli elementi successivi devono essere spostati. Inoltre, gli elenchi collegati possono aumentare finché c'è spazio. Tuttavia, anche gli array "dinamici" che si ridimensionano automaticamente potrebbero diventare inaspettatamente costosi. Ovviamente c'è sempre un compromesso. Per cercare o modificare un elemento in un elenco collegato, potremmo dover percorrere l'intera lunghezza che equivale al tempo lineare. Con gli indici di array, tuttavia, tali operazioni sono banali.

Come gli array, gli elenchi collegati possono funzionare come stack . È semplice come avere la testa l'unico posto per l'inserimento e la rimozione. Gli elenchi collegati possono anche funzionare come code . Ciò può essere ottenuto con una lista doppiamente collegata, in cui l'inserimento avviene in coda e la rimozione avviene in testa, o viceversa. Per un gran numero di elementi, questo modo di implementare le code è più performante rispetto all'utilizzo di array perché le operazioni shifte unshiftall'inizio degli array richiedono un tempo lineare per reindicizzare ogni elemento successivo.

Gli elenchi collegati sono utili sia sul client che sul server. Sul client, le librerie di gestione dello stato come Redux strutturano la logica del middleware in modo da elenchi collegati. Quando le azioni vengono inviate, vengono convogliate da un middleware al successivo fino a quando non vengono tutte visitate prima di raggiungere i riduttori . Sul server, anche i framework web come Express strutturano la logica del middleware in modo simile. Quando viene ricevuta una richiesta, viene inviata tramite pipe da un middleware al successivo fino a quando non viene emessa una risposta .

Un esempio di Doubly-Linked Listin codice:

Albero

A Treeè come un elenco collegato , tranne per il fatto che mantiene i riferimenti a molti nodi figlio in una struttura gerarchica . In altre parole, ogni nodo non può avere più di un genitore. Il Document Object Model (DOM) è una struttura di questo tipo, con un htmlnodo radice che si dirama nei nodi heade body, che si suddividono ulteriormente in tutti i tag html familiari . Sotto il cofano, l' ereditarietà prototipale e la composizione con i componenti React producono anche strutture ad albero. Ovviamente, come rappresentazione in memoria del DOM, anche il DOM virtuale di React è una struttura ad albero.

L' albero di ricerca binario è speciale perché ogni nodo non può avere più di due figli . Il figlio sinistro deve avere un valore minore o uguale al suo genitore, mentre il figlio destro deve avere un valore maggiore . Strutturato ed equilibrato in questo modo, possiamo cercare qualsiasi valore nel tempo logaritmico perché possiamo ignorare metà della ramificazione ad ogni iterazione. L'inserimento e l' eliminazione possono anche avvenire in tempo logaritmico. Inoltre, il valore più piccolo e quello più grande possono essere facilmente trovati rispettivamente sulla foglia più a sinistra e più a destra .

L'attraversamento dell'albero può avvenire con una procedura verticale o orizzontale . In Depth-First Traversal (DFT) in direzione verticale, un algoritmo ricorsivo è più elegante di uno iterativo. I nodi possono essere attraversati in pre-ordine , in ordine o in post-ordine . Se abbiamo bisogno di esplorare le radici prima di ispezionare le foglie, dovremmo scegliere il preordine . Ma se dobbiamo esplorare le foglie prima delle radici, dovremmo scegliere il post-ordine . Come suggerisce il nome, in-order ci consente di attraversare i nodi in ordine sequenziale . Questa proprietà rende gli alberi di ricerca binari ottimali per l' ordinamento .

In Breadth-First Traversal (BFT) in direzione orizzontale, un approccio iterativo è più elegante di uno ricorsivo. Ciò richiede l'uso di a queueper tenere traccia di tutti i nodi figli con ogni iterazione. Tuttavia, la memoria necessaria per una tale coda potrebbe non essere banale. Se la forma di un albero è più larga che profonda, BFT è una scelta migliore di DFT. Inoltre, il percorso che BFT prende tra due nodi qualsiasi è il più breve possibile.

Un esempio di Binary Search Treein codice:

Grafico

Se un albero è libero di avere più di un genitore, diventa un Graph. I bordi che collegano i nodi insieme in un grafico possono essere diretti o non orientati , pesati o non ponderati . I bordi che hanno sia direzione che peso sono analoghi ai vettori .

Eredità multiple sotto forma di Mixin e oggetti dati che hanno relazioni molti-a-molti producono strutture grafiche. Anche un social network e Internet stesso sono grafici. Il grafico più complicato in natura è il nostro cervello umano, che le reti neurali tentano di replicare per fornire alle macchine una superintelligenza .

Un esempio di Graphin codice:

TK

Tabella hash

Una tabella hash è una struttura simile a un dizionario che abbina chiavi a valori . La posizione in memoria di ciascuna coppia è determinata da a hash function, che accetta una chiave e restituisce l' indirizzo dove la coppia deve essere inserita e recuperata. Possono verificarsi collisioni se due o più chiavi vengono convertite nello stesso indirizzo. Per robustezza getterse settersdovrebbe anticipare questi eventi per garantire che tutti i dati possano essere ripristinati e nessun dato venga sovrascritto. Di solito, linked listsoffri la soluzione più semplice. Anche avere tavoli molto grandi aiuta.

Se sappiamo che i nostri indirizzi saranno in sequenze di numeri interi, possiamo semplicemente usarli Arraysper memorizzare le nostre coppie chiave-valore. Per mappature di indirizzi più complesse, possiamo usare Mapso Objects. Le tabelle hash hanno in media l' inserimento e la ricerca di tempo costante . A causa delle collisioni e del ridimensionamento, questo costo trascurabile potrebbe aumentare fino a raggiungere il tempo lineare. In pratica, tuttavia, possiamo presumere che le funzioni hash siano sufficientemente intelligenti da rendere le collisioni e il ridimensionamento rari ed economici. Se le chiavi rappresentano gli indirizzi e quindi non è necessario alcun hashing, object literalpuò essere sufficiente un semplice . Ovviamente c'è sempre un compromesso. La semplice corrispondenza tra chiavi e valori, e la semplice associatività tra chiavi e indirizzi, sacrifica le relazioni tra i dati. Pertanto, le tabelle hash non sono ottimali per la memorizzazione dei dati.

Se una decisione di compromesso favorisce il recupero rispetto all'archiviazione, nessun'altra struttura di dati può eguagliare la velocità delle tabelle hash per la ricerca , l' inserimento e l' eliminazione . Non sorprende, quindi, che sia usato ovunque . Dal database, al server, al client, le tabelle hash e in particolare le funzioni hash sono fondamentali per le prestazioni e la sicurezza delle applicazioni software. La velocità delle query sul database dipende fortemente dalla conservazione di tabelle di indici che puntano ai record in ordine ordinato . In questo modo, le ricerche binarie possono essere eseguite in tempo logaritmico , un'enorme vittoria in termini di prestazioni soprattutto per i Big Data .

Sia sul client che sul server, molte librerie popolari utilizzano la memorizzazione per massimizzare le prestazioni. Mantenendo un record degli input e degli output in una tabella hash, le funzioni vengono eseguite solo una volta per gli stessi input. La popolare libreria Reselect utilizza questa strategia di memorizzazione nella cache per ottimizzare le mapStateToPropsfunzioni nelle applicazioni abilitate per Redux . In effetti, sotto il cofano, il motore JavaScript utilizza anche tabelle hash chiamate heap per archiviare tutto variablese primitivescreiamo. Sono accessibili da puntatori sullo stack di chiamate .

La stessa Internet si basa anche su algoritmi di hashing per funzionare in modo sicuro. La struttura di Internet è tale che qualsiasi computer può comunicare con qualsiasi altro computer attraverso una rete di dispositivi interconnessi. Ogni volta che un dispositivo accede a Internet, diventa anche un router attraverso il quale possono viaggiare flussi di dati. Tuttavia, è un'arma a doppio taglio. Un decentrati mezzi architettura qualsiasi dispositivo nella rete possono ascoltare e tamper con i pacchetti di dati che aiuta a relè. Le funzioni hash come MD5 e SHA256 svolgono un ruolo fondamentale nella prevenzione di tali attacchi man-in-the-middle . L'e-commerce su HTTPS è sicuro solo perché vengono utilizzate queste funzioni di hashing.

Ispirate da Internet, le tecnologie blockchain cercano di rendere open source la struttura stessa del web a livello di protocollo . Utilizzando le funzioni hash per creare impronte digitali immutabili per ogni blocco di dati , essenzialmente l'intero database può esistere apertamente sul Web affinché chiunque possa vederlo e a cui contribuire. Strutturalmente, le blockchain sono solo elenchi collegati singolarmente di alberi binari di hash crittografici. L'hashing è così criptico che chiunque può creare e aggiornare un database di transazioni finanziarie allo scoperto ! L'incredibile implicazione è l'incredibile potere di creare denaro stesso. Ciò che una volta era possibile solo per i governi e le banche centrali, ora chiunque può creare in modo sicuro la propria valuta ! Questa è la visione chiave realizzata dal fondatore di Ethereum e dallo pseudonimo fondatore di Bitcoin .

Man mano che un numero sempre maggiore di database si sposta allo scoperto, aumenterà anche la necessità di ingegneri frontend in grado di astrarre tutte le complessità crittografiche di basso livello. In questo futuro, il principale elemento di differenziazione sarà l' esperienza dell'utente .

Un esempio di Hash Tablein codice:

Per gli esercizi sugli algoritmi che utilizzano queste strutture dati e altro, controlla: Algoritmi in JavaScript: 40 problemi, soluzioni e spiegazioni

Conclusione

Man mano che la logica si sposta sempre più dal server al client, il livello dati sul frontend diventa fondamentale. La corretta gestione di questo livello implica la padronanza delle strutture dati su cui poggia la logica. Nessuna struttura dati è perfetta per ogni situazione perché ottimizzare per una proprietà equivale sempre a perderne un'altra. Alcune strutture sono più efficienti nella memorizzazione dei dati, mentre altre sono più efficienti per la ricerca attraverso di esse. Di solito, uno viene sacrificato per l'altro. Ad un estremo, gli elenchi collegati sono ottimali per l'archiviazione e possono essere trasformati in pile e code ( tempo lineare ). Dall'altro, nessun'altra struttura può eguagliare la velocità di ricerca delle tabelle hash ( tempo costante ). Le strutture degli alberi si trovano da qualche parte nel mezzo ( tempo logaritmico ) e solo un grafico può rappresentare la struttura più complessa della natura: il cervello umano ( tempo polinomiale ). Avere la capacità di distinguere quando e articolare perché è un segno distintivo di un ingegnere rockstar.

Esempi di queste strutture di dati possono essere trovati ovunque . Dal database, al server, al client, e anche il motore JavaScript in sé, queste strutture di dati concretizzano quello che essenzialmente sono solo on e off “interruttori” a chip di silicio in realistiche “oggetti”. Sebbene solo digitale, l'impatto di questi oggetti sulla società è enorme. La tua capacità di leggere questo articolo in modo libero e sicuro attesta la straordinaria architettura di Internet e la struttura dei suoi dati. Tuttavia, questo è solo l'inizio. L'intelligenza artificiale e le blockchain decentralizzate nei prossimi decenni ridefiniranno cosa significa essere umani e il ruolo delle istituzioni che governano le nostre vite. Le intuizioni esistenziali e la disintermediazione istituzionale saranno caratteristiche di un Internet finalmente maturato.

Per aiutare la transizione verso questo futuro più equo, noi di HeartBank® canalizziamo reti di neuroni artificiali per infondere nei nostri Kiitos il potere di emettere denaro sulla blockchain, insieme alla capacità di empatizzare la condizione umana. Dai ringraziamenti anonimi che diamo e riceviamo scrivendo a Kiitos , Kiitos apprende le nostre gentilezze e i loro effetti , premiandoci in modo tale da ridurre le disuguaglianze economiche tra di noi, in un processo graduale e misterioso che preserva la nostra libertà e libertà personali. Forse l'ultima struttura del grafico in natura non è il cervello umano, ma l'umano ❤️, se solo possiamo vedere le corde del cuore che ci connettono tutti.

Interessato alla blockchain ? Impara Ethereum e vieni a lavorare per noi!

Un modello mentale completo per lo sviluppo di dApp Ethereum