Žingsnis į kompiuterį kaip mokslą

Paprasti algoritmai ir duomenų struktūros JS

J. Craigo nuotrauka „Un-splash“

Algoritmas yra veiksmai, kurių imamasi norint išspręsti problemą. Duomenų struktūra - tai duomenys, organizuoti siekiant veiksmingos prieigos. Galite naudoti algoritmą, kad išspręstumėte visų rūšių problemas (t. Y. Ieškote duomenų rinkinio arba rūšiuotumėte duomenų rinkinį) pagal tam tikrą duomenų struktūrą.

Taigi kalbant apie kompiuterius, algoritmas yra jūsų atliekamas metodas (ty, linijinė paieška, dvejetainė paieška, burbulų rūšiavimas, atrankos rūšiavimas, įterpimo rūšiavimas ir tt), tuo tarpu duomenų struktūra yra dalykas, kurį jūs darote. į (ty masyvas, raktų reikšmės suporuoti objektai ir kt.). Taigi galite metodiškai ieškoti, rūšiuoti ar sukurti organizuotą duomenų rinkinį.

Paprasta duomenų struktūra

Masyvas

Masyvas yra tarsi sunumeruoti langeliai (rodyklė), išdėstyti nuo žemiausios (0) iki didžiausios (2) etiketės. Kiekviena dėžutė yra pritvirtinta savo vietoje ir lieka pagal etiketę.

Galite pereiti prie bet kurio pažymėto langelio, norėdami pamatyti jo turinį (arrayName [2]), pridėti turinį arba pakeisti jo turinį (arrayName [2] = „Sherlock Holmes“). Naujai įdėtą turinį galite perkelti į savo kolekcijos pabaigą (arrayName.push („Šerloko Holmso memuarai“)).

Gaunamai dėžutei suteikiama sekanti etiketė iš eilės (3). Norėdami grįžti į originalią dėžutėje esančią kolekciją, galite nubrėžti jos pabaigą (arrayName.pop ()).

Taip pat galite perkelti pirmąjį langelį (arrayName.shift ()), tačiau tam reikės žymėti visas kitas dėžutes.

Dabar jūsų „Sherlock Holmes“ kolekcija yra dėžutėje, pažymėtoje 1. Jei nepanaikinsite savo dėžutės kolekcijos, rinkinio pradžioje galite pridėti naują turinio dėžutę (arrayName.shift („Dr. Strange“)).

Tai suteikia mums „Dr. Strange & Sherlock Holmes“ kolekciją dėžutėse, pažymėtose 0 ir 2.

Duomenų struktūros paieška

Linijinė paieška

Linijinė paieška yra tarsi vaikščiojimas po daugybę dėžių (t. Y. Nuo 0 iki 16) ir atidarius kiekvieną dangtelį, kad pamatytumėte, ar jo turinys yra tai, ko ieškote (t. Y. 37).

šaltinis

Taigi rodyklę nuo kolekcijos pradžios (sakykime 0) iki jos pabaigos (jos ilgis atėmus vieną) galime ieškoti norimo turinio dėžutėje ir pereiti prie kito. Mes galime padidinti nuo vieno langelio prie kito, kol rasime atitiktį.

Dvejetainė paieška

Dvejetainė paieška yra tarsi paieška per daugybę dėžučių, kurių turinys yra išdėstytas (t. Y. Skaitine ar abėcėlės tvarka), peršokant į pusę iki vidurinio langelio ir patikrinant, ar jame nėra jūsų norimo elemento. Jei viršijote, peršokite atgal, pusiaukelėje tarp dabartinės padėties ir pradinio taško. Priešingu atveju jūs peršoksite į priekį, pusiaukelėje tarp dabartinės padėties ir galinio taško.

šaltinis

Taigi, ką galite padaryti, tai sekti savo žemą (iš pradžių 0), vidurinę (8) ir aukštą (iš pradžių 16) indekso pozicijas. Vidurinė pozicija visada yra pusė žemų ir aukštų indeksų sumos. Jūs pažymite vidurinį langelį, ar nėra rungtynių (t. Y. 37). Jei jo vertė mažesnė, nei tikėjotės (<37), tada jūs šuolis į priekį. Jūs iš naujo nustatėte žemą indeksą, kad galėtumėte peržengti dabartinę vidurinę poziciją viena (8 + 1 = 9). Tada perskaičiuokite naują vidurinę padėtį ((9 + 16) / 2 ≈ 12).

Kitaip tariant, galite pereiti į priekį paieškoje iš naujo nustatydami žemą indeksą ir perskaičiuodami naują vidutinį indeksą. Priešingai, jei peržengėte, galite grįžti atgal nustatydami aukštą indeksą ir perskaičiuodami naują vidutinį indeksą.

Skirtingai nuo tiesinės paieškos, šis tipas yra dvejetainis. Jūs visada atspėjote, ar jūsų daiktas yra dėžutės kolekcijos pirmoje ar antroje pusėje.

Duomenų struktūros rūšiavimas

Burbulas Rūšiuoti

„Burbulas“ rūšiuoja kolekciją, nuolat keisdami didesnę vertę su greta esančia mažesne, todėl didžiausia vertė burbuliuoja iki viršaus.

šaltinis

Taigi visą savo kolekcijos ilgį, pradedant nuo rodyklės 0, jūs keičiate dabartinio rodyklės (i) turinį į vėlesnio rodyklės (i + 1) turinį, jei ankstesnis yra didesnis. Tada pereisite prie kito indeksų rinkinio (i + 1 ir i + 2) ir pan.

Tam tikru metu jūs būsite atvykę į dėžutę, kurios vertė yra didžiausia jūsų kolekcijoje. Taigi turinys bus keičiamas į priekį. Taigi jis burbuliuoja aukštyn. Kartojate šį procesą, kol jūsų kolekcija bus rūšiuojama nuo mažos iki didelės.

Kadangi paskutinis kiekvienos iteracijos langelis baigsis didžiausia verte, pakartokite procesą, neįtraukdami paskutinių langelių.

Pasirinkimas Rūšiuoti

Pasirinkimo rūšiavimas yra rūšiuojantis kolekciją, nuolat pasirenkant mažiausią vertę ir sukeičiant ją į vieną galą.

šaltinis

Taigi, jūs nuskaitote visą savo kolekciją, kad surastumėte mažiausią vertę. Kai jis bus rastas, jūs pakeisite jo turinį langeliu, pažymėtu žemiausiu indeksu (iš pradžių indeksu 0). Jūs pakartokite šį procesą, pradėdami nuo kito žemiausio indekso (1 rodyklė), nes mažiausia jūsų vertė yra teisingoje padėtyje. Su kiekviena kartojimu nuskaitymo ilgio intervalas sumažėja 1, kol visa kolekcija bus rūšiuojama nuo žemiausios iki didžiausios vertės.

Įterpimas Rūšiuoti

Įterpimo rūšis rūšiuoja kolekciją, įterpiant kiekvieną vertę į teisingą vietą.

šaltinis

Taigi čia, užuot nuskaitydami visą kolekciją per iteraciją (t. Y. „Bubble & Selection Sorts“), jūs pradedate nuo 0 ir 1 rodyklės, kad palygintumėte jų vertes. Jei vėlesnė vertė yra mažesnė, jei 1 rodyklės turinys yra mažesnės vertės nei rodyklė 0, pakeisite jų turinį. Jūs pereisite prie kito 2 rodyklės langelio ir palyginsite su anksčiau rūšiuotais laukeliais (1 rodyklė, tada 0 rodyklė).

Kiekvieną kartą susidūrę su didesne verte, jūs pakeisite jos turinį į dešinę. Suradę teisingą vietą, turinį (anksčiau buvę 2 rodyklėje) įterpiate į tinkamą langelį. Taigi, tarsi „ištrauktumėte“ vėlesnės dėžutės turinį ir eitumėte į ankstesnę dėžę.

Jei ankstesnio langelio vertė yra didesnė nei jūsų laikoma, jo turinį perkelsite į vėlesnį langelį. Jūs tai darote tol, kol rasite tinkamą vietą įterpti tai, ką laikote.

Kita paprasta duomenų struktūra

Raktas - vertės suporuoti objektai

Raktų vertės poruotas objektas yra tarsi nepaženklintas indėlių rinkinys. Kiekvienas unikalus raktas atveria tam tikrus duomenis. Skirtingai nuo masyvo, tai yra netvarkingi duomenys, prieinami unikaliais klavišais.

šaltinis

Taigi, jūs pasiekiate depozitinę dėžę naudodamiesi jos raktu (objectName ['s']), pakeisdami jos turinį arba sukurdami raktą, kuris atsiveria nurodytam turiniui (objectName ['s'] = 'Sherlock Holmes'). Galite pasiekti visus raktus, skirtus visų turimų daiktų dėžutėms, arba turinį, saugomą visose saugyklose (Object.keys (objectName) arba Object.values ​​(objectName)).

Išvada

Pagrindiniai algoritmai (linijinės ir dvejetainės paieškos; burbulas, atrankos ir įterpimo rūšys) ir duomenų struktūros (masyvo ir rakto vertės objektai) sukelia laiko ir erdvės klausimus, susijusius su duomenų valdymu. Atsižvelgiant į tai, kiek laiko reikia duomenų paieškai, rūšiavimui ar prieigai prie jų, ir šiems procesams reikalingos atminties vietos, gali paversti programinės įrangos kūrėją nuo kompiuterio programavimo iki informatikos. Tai trunka nuo efektyvumo programavimo iki efektyvumo programavimo.