Un passo verso l'informatica come scienza

Algoritmi semplici e strutture dati in JS

Foto di J. Craig su Un-splash

Un algoritmo è la procedura adottata per risolvere un problema. Una struttura di dati è organizzata per un accesso efficiente. È possibile utilizzare un algoritmo per risolvere tutti i tipi di problemi (vale a dire, cercare un dato o ordinare una raccolta di dati) per una determinata struttura di dati.

Quindi, per quanto riguarda i computer, un algoritmo è il metodo di ciò che stai facendo (ad esempio, ricerca lineare, ricerca binaria, ordinamento a bolle, ordinamento per selezione, ordinamento per inserzione, ecc.), Mentre una struttura di dati è la cosa che stai facendo a (ad es. array, oggetti associati a valori-chiave, ecc.). Quindi puoi cercare metodicamente, ordinare o creare un set di dati organizzato.

Una struttura dati semplice

schieramento

Un array è come caselle numerate (indice) ordinate dalla più bassa (0) alla sua più alta (2) etichetta. Ogni scatola è fissata in posizione e rimane ordinata dalla sua etichetta.

Puoi passare a qualsiasi casella etichettata per osservarne il contenuto (arrayName [2]), per aggiungere contenuto o sostituirne il contenuto (arrayName [2] = "Sherlock Holmes"). Puoi spingere il contenuto appena inscatolato alla fine della tua raccolta (arrayName.push ("The Memoirs of Sherlock Holmes")).

Questo dà alla casella in arrivo l'etichetta successiva nella sequenza (3). Per tornare alla tua raccolta in scatola originale, puoi estrarre la fine (arrayName.pop ()).

Puoi anche spostare la prima casella (arrayName.shift ()), ma ciò richiederà la rietichettatura di tutte le altre caselle.

La tua collezione Sherlock Holmes è ora nella casella etichettata 1. Se si sposta la raccolta box, è possibile aggiungere all'inizio della raccolta una nuova casella di contenuto (arrayName.shift ("Dr. Strange")).

Questo ci dà la nostra collezione Dr. Strange & Sherlock Holmes in scatole etichettate 0 e 2.

Ricerca in una struttura di dati

Ricerca lineare

Una ricerca lineare è come camminare lungo una serie di caselle (ovvero 0 - 16) e aprire ciascuna copertina per vedere se il suo contenuto è quello che stai cercando (cioè 37).

fonte

Quindi, per un indice che va dall'inizio di una raccolta (diciamo 0) alla sua fine (la sua lunghezza meno una), possiamo cercare il contenuto desiderato in una casella e passare a quello successivo. Possiamo aumentare da una casella all'altra fino a quando non troviamo una corrispondenza.

Ricerca binaria

Una ricerca binaria è come cercare attraverso una serie di riquadri, i cui contenuti sono ordinati (ad esempio, numerici o alfabetici), saltando a metà strada verso un riquadro intermedio e controllandone il contenuto per l'oggetto desiderato. Se hai oltrepassato, salti all'indietro, a metà strada tra la posizione corrente e il punto di partenza. Altrimenti, si salta in avanti, a metà strada tra la posizione corrente e l'endpoint.

fonte

Quindi, ciò che puoi fare è tenere traccia delle tue posizioni indice basse (inizialmente 0), medie (8) e alte (inizialmente 16). La posizione centrale è sempre la metà della somma degli indici bassi e alti. Controlli la casella centrale per una partita (ad es. 37). Se è inferiore a quello che ti aspettavi (<37), allora salti in avanti. Azzerate il vostro indice basso per passare la posizione media corrente di uno (8 + 1 = 9). Quindi, ricalcola una nuova posizione centrale ((9 + 16) / 2 ≈ 12).

In altre parole, puoi fare un salto in avanti nella ricerca ripristinando il tuo indice basso e ricalcolando un nuovo indice medio. Al contrario, se si è superati, è possibile saltare indietro ripristinando l'indice alto e ricalcolando un nuovo indice medio.

A differenza della ricerca lineare, questo tipo è binario. Indovina sempre se il tuo articolo si trova nella prima o nella seconda metà della tua collezione in scatola.

Ordinamento di una struttura dati

Bubble Sort

Un ordinamento a bolle sta ordinando una raccolta scambiando continuamente un valore più alto con uno minore adiacente, determinando l'effetto del valore più alto che gorgoglia verso l'alto.

fonte

Pertanto, per la lunghezza della raccolta, a partire dall'indice 0, si scambiano i contenuti di un indice corrente (i) con i contenuti di un indice successivo (i + 1), se il valore precedente è maggiore. Quindi, si passa al set di indici successivo (i + 1 vs. i + 2) e così via.

Ad un certo punto, sarai arrivato in una scatola con il valore più alto nella tua collezione. E così, sarà il contenuto che continua a essere scambiato in avanti. Quindi bolle verso l'alto. Ripeti questo processo fino a quando la tua raccolta non viene ordinata, dal più basso al più alto valore.

Poiché l'ultima casella di ogni iterazione termina con il valore più alto, si ripete il processo escludendo le ultime caselle.

Ordinamento selezione

Un ordinamento di selezione sta ordinando una raccolta selezionando continuamente il valore più basso e scambiandolo a un'estremità.

fonte

Quindi, qui esegui la scansione dell'intera raccolta per trovare il valore più basso. Una volta trovato, si scambia il suo contenuto con la casella etichettata con l'indice più basso (inizialmente indice 0). Ripetete questo processo a partire dall'indice più basso successivo (indice 1) poiché il valore più basso è nella posizione corretta. Con ogni iterazione, l'intervallo di lunghezza per la scansione diminuisce di 1, fino a quando l'intera raccolta non viene ordinata dal valore più basso a quello più alto.

Ordinamento inserzione

Un ordinamento per inserzione sta ordinando una raccolta inserendo ciascun valore rilevato nella posizione corretta.

fonte

Quindi qui, piuttosto che scansionare un'intera raccolta per iterazione (cioè Bubble & Sort Sorts), inizi dall'indice 0 & 1 per confrontare i loro valori. Se il valore successivo è inferiore, se i contenuti dell'indice 1 hanno un valore inferiore rispetto all'indice 0, si scambiano i loro contenuti. Si passa alla casella successiva all'indice 2 e si confronta con le caselle precedentemente ordinate (indice 1, quindi indice 0).

Ogni volta che si incontra un valore più elevato, si scambia il suo contenuto verso destra. Quando hai trovato la posizione corretta, inserisci il contenuto (precedentemente all'indice 2) nella casella corretta. Quindi, è come se "tirassi fuori" il contenuto di una scatola successiva e passassi a una scatola precedente.

Se la casella precedente ha un valore più elevato di quello che si tiene, si sposta il suo contenuto nella casella successiva. Continui a farlo finché non trovi il punto giusto per inserire ciò che stai trattenendo.

Un'altra semplice struttura di dati

Chiave - Valore Oggetti associati

Un oggetto associato a valore-chiave è come un insieme senza etichetta di cassette di deposito. Ogni chiave univoca si apre a un dato specifico. A differenza di un array, sono i dati non ordinati accessibili da chiavi univoche.

fonte

Quindi, accedi a una cassetta di sicurezza usando la sua chiave (objectName [’s ’)), ne cambi il contenuto o crei una chiave che si apre a un contenuto specificato (objectName [’s’] = “Sherlock Holmes”). Puoi accedere a tutte le chiavi create per o a tutti i contenuti archiviati in tutte le tue caselle di deposito (Object.keys (objectName) o Object.values ​​(objectName)).

Conclusione

Gli algoritmi di base (ricerche lineari e binarie; bolle, ordinamenti di selezione e inserimento) e strutture di dati (array e oggetti valore-chiave) portano a domande su tempo e spazio riguardanti la gestione dei dati. Le considerazioni sul tempo impiegato per la ricerca, l'ordinamento o l'accesso ai dati e lo spazio di memoria richiesto per questi processi possono elevare uno sviluppatore di software dalla programmazione informatica all'informatica. Ti porta dal pensare alla programmazione per l'efficacia alla programmazione per l'efficienza.