Askel kohti tietojenkäsittelyä tieteenä

Yksinkertaiset algoritmit ja tietorakenteet JS: ssä

Kuva J. Craig on Un-splash

Algoritmi on ongelman ratkaisemiseksi toteutetut vaiheet. Tietorakenne on tehokasta käyttöä varten järjestetty data. Voit käyttää algoritmia kaikenlaisten ongelmien ratkaisemiseksi (ts. Tietyn kappaleen etsimiseen tai tietokokoelman lajitteluun) tietylle tietorakenteelle.

Joten tietokoneisiin, algoritmi on menetelmä, jota teet (ts. Lineaarinen haku, binaarihaku, kuplalajittelu, valintalaji, lisäyslajittelu jne.), Kun taas tietorakenne on asia, jota teet (eli taulukko, avain-arvo-pariksi muodostetut objektit jne.). Joten voit etsiä, lajitella tai luoda järjestetyn aineiston metodologisesti.

Yksinkertainen tietorakenne

ryhmä

Matriisi on kuin numeroitu ruutu (hakemisto), joka on järjestetty alimmasta (0) korkeimpaan (2) tarraan. Jokainen laatikko on kiinnitetty paikoilleen ja pysyy merkinnänsä mukaisesti.

Voit siirtyä mihin tahansa merkittyyn ruutuun tarkastellaksesi sen sisältöä (arrayName [2]), lisätäksesi sisältöä tai korvataksesi sen sisällön (arrayName [2] = “Sherlock Holmes”). Voit viedä juuri laatikoidun sisällön kokoelmasi loppuun (arrayName.push (“Sherlock Holmesin muistelmat”)).

Tämä antaa tulevalle laatikolle seuraavan tarran sarjassa (3). Voit palata alkuperäiseen laatikkokoelmaansa napsauttamalla loppua (arrayName.pop ()).

Voit myös siirtää ensimmäisen laatikkosi (arrayName.shift ()), mutta tämä edellyttää kaikkien muiden laatikoiden uudelleensijoittamista.

Sherlock Holmes -kokoelmasi on nyt laatikossa, jonka otsikko on 1. Jos poistat laatikkokokoelmasi siirtämisestä, voit lisätä kokoelman alkuun uuden sisältölaatikon (arrayName.shift (“Dr. Strange”)).

Tämä antaa meille Dr. Strange & Sherlock Holmes -kokoelman laatikoihin, joissa on merkintä 0 ja 2.

Tietorakenteen etsiminen

Lineaarinen haku

Lineaarinen haku on kuin käveleminen ryhmää laatikoita (eli 0-16) ja kunkin kannen avaaminen nähdäksesi, ovatko sen sisällöt etsimäsi (ts. 37).

lähde

Joten hakemistolle, joka vaihtelee kokoelman alusta (sanotaan 0) sen loppuun (sen pituus vähennettynä yhdellä), voimme etsiä haluaman sisällön laatikosta ja siirtyä seuraavaan. Voimme siirtyä laatikosta toiseen, kunnes löydämme vastaavuuden.

Binaarihaku

Binaarihaku on kuin etsiminen joukosta laatikoita, joiden sisältö on järjestetty (ts. Numeerinen tai aakkosellinen), hyppäämällä puoliväliin keskikentään ja tarkistamalla sen sisältö haluamasi kohteen suhteen. Jos ylität, hyppää taaksepäin, puoliväliin nykyisen sijaintisi ja lähtöpisteen välillä. Muuten hypät eteenpäin, puolivälissä nykyisen sijaintisi ja päätepisteen välillä.

lähde

Joten mitä voit tehdä, on seurata alhaista (alun perin 0), keskimmäistä (8) ja korkeaa (alun perin 16) indeksipaikkaasi. Keskiasento on aina puoli alhaisten ja korkeiden indeksien summaa. Tarkastat, että keskikentässä on ottelu (ts. 37). Jos se on vähemmän kuin odotit (<37), hyppää eteenpäin. Palautit matalamman indeksin, jotta nykyinen keskiasento siirtyy yhdellä (8 + 1 = 9). Laske sitten uudelleen uusi keskiasento ((9 + 16) / 2 ≈ 12).

Toisin sanoen, voit siirtyä eteenpäin haussa nollaamalla matala indeksi ja laskemalla uudelleen uusi keskimääräinen indeksi. Toisaalta, jos ylität, voit hypätä taaksepäin nollaamalla korkean indeksin ja laskemalla uudelleen uuden keskimääräisen indeksin.

Toisin kuin lineaarinen haku, tämä tyyppi on binaarinen. Arvaat aina, sijaitseeko esineesi pakatun kokoelman 1. tai 2. puoliskolla.

Tietorakenteen lajittelu

Kuplalajittelu

Kuplalajittelu lajittelee kokoelman vaihtamalla jatkuvasti korkeampaa arvoa viereisen pienemmän kanssa, mikä johtaa suurimman arvon kuplittamiseen yläosaan.

lähde

Joten vaihdat kokoelmasi ajan, indeksistä 0 alkaen, vaihdat nykyisen hakemiston (i) sisällön myöhemmän hakemiston (i + 1) sisällölle, jos aikaisempi on arvokkaampi. Sitten siirrytään seuraavaan hakemistojoukkoon (i + 1 vs. i + 2) ja niin edelleen.

Jossain vaiheessa olet saapunut laatikkoosi, jolla on korkein arvo kokoelmassa. Ja niin, sisältöä jatketaan vaihtamalla eteenpäin. Siksi se kupli ylöspäin. Toistat tätä prosessia, kunnes kokoelmasi on lajiteltu alhaisesta arvoon.

Koska jokaisen iteraation viimeinen ruutu loppuu suurimmalla arvolla, toista prosessi sulkemalla pois viimeiset ruudut.

Valinta Lajittele

Valintalajittelu on lajittelu kokoelmaan valitsemalla jatkuvasti alhaisin arvo ja vaihtamalla se toiseen päähän.

lähde

Joten, täällä voit skannata koko kokoelmasi löytääksesi pienimman arvon. Kun se on löydetty, vaihdat sen sisällön laatikolla, jolla on alin indeksi (alun perin indeksi 0). Toistat tämän prosessin alkamalla seuraavalla alimmalla indeksillä (hakemisto 1), koska alin arvo on oikeassa paikassa. Jokaisen iteraation avulla skannauksen pituusalue pienenee yhdellä, kunnes koko kokoelma on lajiteltu alimmasta korkeimpaan arvoon.

Lisäyslajittelu

Lisäyslajittelu lajittelee kokoelman lisäämällä jokainen havaittu arvo oikeaan sijaintiin.

lähde

Joten täällä, sen sijaan, että skannaat koko kokoelman iteraatiota (ts. Bubble & Selection Sorts), aloitat indeksistä 0 & 1 vertaillaksesi niiden arvoja. Jos myöhempi arvo on alhaisempi, jos hakemiston 1 sisältö on arvoltaan alhaisempi kuin indeksi 0, vaihdat niiden sisällön. Siirryt seuraavaan ruutuun hakemistossa 2 ja vertaat aiemmin lajiteltuihin ruutuihin (hakemisto 1, sitten hakemisto 0).

Aina kun kohtaat suuremman arvon, vaihdat sen sisällön oikealle. Kun olet löytänyt oikean paikan, lisäät sisällön (aiemmin hakemistossa 2) oikeaan ruutuun. Joten, se on kuin “vetämällä” myöhemmän laatikon sisällön ja kävellemällä aikaisempaan laatikkoon.

Jos aikaisemman ruudun arvo on suurempi kuin mitä pidät, siirrät sen sisällön myöhempään ruutuun. Jatkat tätä, kunnes löydät oikean paikan sijoittaaksesi pidät.

Toinen yksinkertainen tietorakenne

Avain - arvo parilliset objektit

Avainarvon pariksi muodostettu esine on kuin merkitsemätön säilytyslaatikoiden sarja. Jokainen ainutlaatuinen avain avaa tietyn osan. Toisin kuin taulukko, se on järjestämätöntä dataa, johon pääsee yksilöllisillä avaimilla.

lähde

Joten pääset talletuslaatikkoon käyttämällä sen avainta (objectName ['s'), vaihdat sen sisältöä tai luot avaimen, joka avautuu määrättyyn sisältöön (objectName ['s'] = “Sherlock Holmes”). Voit käyttää kaikkia avaimia, jotka on tehty tai kaikille talletettuihin laatikoihin tallennettua sisältöä (Object.keys (objectName) tai Object.values ​​(objectName)).

johtopäätös

Perusalgoritmit (lineaariset ja binaariset haut; kupla-, valinta- ja lisäyslajit) ja tietorakenteet (taulukko- ja avain-arvoobjektit) johtavat ajan ja tilan kysymyksiin tiedonhallinnan suhteen. Tietojen etsimiseen, lajitteluun tai käyttämiseen kuluva aika ja näihin prosesseihin tarvittava muistitila voivat nostaa ohjelmistokehittäjän tietokoneohjelmoinnista tietotekniikkaan. Se vie ajattelemisen tehokkuuden ohjelmoinnista tehokkuuden ohjelmointiin.