Een stap op weg naar computing als wetenschap

Eenvoudige algoritmen en gegevensstructuren in JS

Foto door J. Craig op Un-splash

Een algoritme zijn de stappen die zijn genomen om een ​​probleem op te lossen. Een gegevensstructuur is gegevens die zijn georganiseerd voor efficiënte toegang. U kunt een algoritme gebruiken om allerlei problemen op te lossen (d.w.z. het zoeken naar een stuk gegevens of het sorteren van een verzameling gegevens) voor een bepaalde gegevensstructuur.

Met betrekking tot computers is een algoritme de methode waarmee u bezig bent (bijvoorbeeld lineair zoeken, binair zoeken, bellen sorteren, selecteren sorteren, invoegen sorteren, enz.), Terwijl een datastructuur het ding is dat u doet tot (bijv. array, gepaarde sleutel-waarde objecten, etc.). U kunt dus systematisch een georganiseerde gegevensset doorzoeken, sorteren of maken.

Een eenvoudige gegevensstructuur

reeks

Een array is als genummerde vakjes (index) gerangschikt van laagste (0) tot zijn hoogste (2) label. Elke doos is vastgezet en blijft geordend op het etiket.

U kunt naar elk gelabeld vak gaan om de inhoud ervan te bekijken (arrayName [2]), inhoud toe te voegen of de inhoud ervan te vervangen (arrayName [2] = "Sherlock Holmes"). U kunt nieuw ingesloten inhoud naar het einde van uw verzameling duwen (arrayName.push ("The Memoirs of Sherlock Holmes")).

Dit geeft de binnenkomende doos het volgende label in de reeks (3). Om terug te keren naar uw oorspronkelijke verzameling in dozen, kunt u het einde verwijderen (arrayName.pop ()).

U kunt ook uw eerste vak (arrayName.shift ()) uitschakelen, maar hiervoor moeten al uw andere vakjes opnieuw worden geëtiketteerd.

Uw Sherlock Holmes-collectie bevindt zich nu in het vak met het label 1. Als u uw boxverzameling ongedaan maakt, kunt u een nieuw inhoudsgedeelte (arrayName.shift ("Dr. Strange")) toevoegen aan het begin van uw verzameling.

Dit geeft ons onze Dr. Strange & Sherlock Holmes-collectie in dozen met het label 0 & 2.

Zoeken in een gegevensstructuur

Lineair zoeken

Een lineaire zoekopdracht lijkt op het lopen langs een reeks vakken (d.w.z. 0 - 16) en het openen van elke omslag om te zien of de inhoud is wat u zoekt (d.w.z. 37).

bron

Dus voor een index die varieert van het begin van een verzameling (laten we zeggen 0) tot het einde ervan (de lengte minus één), kunnen we zoeken naar de gewenste inhoud in een vak en doorgaan naar de volgende. We kunnen van het ene vak naar het volgende gaan totdat we een overeenkomst vinden.

Binaire zoekopdracht

Een binaire zoekopdracht is als zoeken in een reeks vakken waarvan de inhoud is geordend (d.w.z. numeriek of alfabetisch), door halverwege naar een middelste vak te springen en de inhoud ervan te controleren op het gewenste item. Als je overstapt, spring je achteruit, halverwege tussen je huidige positie en het startpunt. Anders spring je vooruit, halverwege tussen je huidige positie en het eindpunt.

bron

Wat u dus kunt doen, is uw lage (aanvankelijk 0), midden (8) & hoge (aanvankelijk 16) indexposities bijhouden. De middelste positie is altijd de helft van de som van lage en hoge indexen. Je vinkt het middelste vakje aan voor een wedstrijd (d.w.z. 37). Als het minder is dan je had verwacht (<37), spring je vooruit. U stelt uw lage index opnieuw in om uw huidige middenpositie met één te passeren (8 + 1 = 9). Bereken vervolgens een nieuwe middenpositie ((9 + 16) / 2 ≈ 12).

Met andere woorden, u kunt vooruit springen in uw zoekopdracht door uw lage index opnieuw in te stellen en een nieuwe middenindex opnieuw te berekenen. Omgekeerd kun je achteruit springen door je hoge index opnieuw in te stellen en een nieuwe middenindex opnieuw te berekenen.

In tegenstelling tot lineair zoeken is dit type binair. U raadt altijd of uw item zich in de eerste of tweede helft van uw verzameling in dozen bevindt.

Een gegevensstructuur sorteren

Bubble Sort

Een bubbelsoort sorteert een verzameling door continu een hogere waarde te verwisselen met een aangrenzende kleinere waarde, wat resulteert in het effect van de hoogste waarde die naar boven borrelt.

bron

Dus voor de lengte van uw verzameling, beginnend bij index 0, verwisselt u de inhoud van een huidige index (i) met de inhoud van een latere index (i + 1), als de eerdere waarde groter is. Vervolgens gaat u naar de volgende set indexen (i + 1 versus i + 2), enzovoort.

Op een gegeven moment bent u bij een doos met de hoogste waarde in uw verzameling. En dus zal het de inhoud zijn die steeds verder wordt verwisseld. Daarom borrelt het omhoog. U herhaalt dit proces totdat uw verzameling is gesorteerd, van laag naar hoog in waarde.

Aangezien het laatste vak van elke iteratie eindigt met de hoogste waarde, herhaalt u het proces door de laatste vakken uit te sluiten.

Selectie sorteren

Een selectie sorteert een verzameling door continu te selecteren voor de laagste waarde en deze naar een einde te wisselen.

bron

Dus, hier doorzoek je je hele verzameling om de laagste waarde te vinden. Zodra het is gevonden, ruilt u de inhoud ervan met het vak met het label met de laagste index (aanvankelijk index 0). U herhaalt dit proces beginnend met de volgende laagste index (index 1) omdat uw laagste waarde op de juiste positie staat. Bij elke iteratie neemt het lengtebereik voor uw scan met 1 af, totdat uw hele verzameling is gesorteerd van de laagste tot de hoogste waarde.

Invoegsortering

Een invoegsortering sorteert een verzameling door elke aangetroffen waarde in de juiste positie in te voegen.

bron

Dus hier, in plaats van een hele verzameling per iteratie (d.w.z. Bubble & Selection Sorts) te scannen, begint u bij index 0 & 1 om hun waarden te vergelijken. Als de latere waarde lager is, als de inhoud van index 1 lager is in waarde dan index 0, verwisselt u de inhoud ervan. U gaat naar het volgende vak op index 2 en vergelijkt dit met uw eerder gesorteerde dozen (index 1, dan index 0).

Telkens wanneer u een hogere waarde tegenkomt, wisselt u de inhoud ervan naar rechts. Wanneer u de juiste positie hebt gevonden, plaatst u de inhoud (eerder op index 2) in het juiste vak. Het is dus alsof je de inhoud van een latere doos "uittrekt" en naar een eerdere doos loopt.

Als het eerdere vak een hogere waarde heeft dan wat u vasthoudt, verplaatst u de inhoud ervan naar het latere vak. Je blijft dit doen totdat je de juiste plek vindt om in te voegen wat je vasthoudt.

Nog een eenvoudige gegevensstructuur

Sleutel - Waarde gepaarde objecten

Een gepaarde sleutelwaardeobject is als een niet-geëtiketteerde set stortingsboxen. Elke unieke sleutel opent naar een specifiek stuk gegevens. In tegenstelling tot een array zijn het ongeordende gegevens die toegankelijk zijn via unieke sleutels.

bron

U hebt dus toegang tot een stortingsvak met behulp van de sleutel (objectName [’s’]), wijzigt de inhoud of maakt een sleutel die wordt geopend voor een opgegeven inhoud (objectName [’s’] = "Sherlock Holmes"). U hebt toegang tot alle sleutels die zijn gemaakt voor of alle inhoud die is opgeslagen in al uw stortingsboxen (Object.keys (objectName) of Object.values ​​(objectName)).

Gevolgtrekking

Basisalgoritmen (lineaire en binaire zoekopdrachten; bellen, selectie en invoegsoorten) & gegevensstructuren (array- en sleutelwaardeobjecten) leiden tot vragen over tijd en ruimte met betrekking tot gegevensbeheer. Overwegingen van de tijd die nodig is om gegevens te zoeken, te sorteren of te openen en de geheugenruimte die nodig is voor deze processen, kunnen een softwareontwikkelaar verheffen van computerprogrammering naar computerwetenschap. Het gaat van denken aan programmeren voor efficiëntie naar programmeren voor efficiëntie.