Algoritmai „Javascript“ - paaiškinta dvejetainė paieška

Jei norite įgyti naujų problemų sprendimo įgūdžių ir išplėsti savo kompiuterių mokslo žinias, nežiūrėkite toliau į nemokamus vienos valandos „Scrimba“ kursus „The Working Developer's Guide to Algorithms“. Jis buvo sukurtas tiems, kurie neturi informatikos išsilavinimo ir jaučia, kad jiems būtų naudinga mokytis algoritmiškai mąstyti.

Ką daro kursas?

Mūsų vadovas padės jums sukurti šešis skirtingus dvejetainius paieškos algoritmus. Klasikiniu „Scrimba“ stiliumi joje yra daugybė iššūkių, todėl įgysite reikiamą raumenų atmintį, kad galėtumėte patobulinti savo, kaip programinės įrangos kūrėjo, įgūdžius ir geriau dirbti su algoritmais.

Sužinosite:

  • Dvejetainė paieška
  • Didelis O žymėjimas
  • Privalomas kodas
  • Rekursija
  • Uodegos rekursija
  • Masyvo padalijimas
  • Masyvo vaizdas
  • Padalijimas

Kiekvienas algoritmas mokomas trimis etapais:

  • Apžvalga: Jonathanas konceptualiai pristato algoritmą.
  • Įgyvendinimas: mes susitepame rankas, sukurdami savo algoritmo versijas.
  • Sprendimas: Jonathanas rodo mums savo įgyvendinimą palyginimui.

Būtinos sąlygos

Jūs išnaudosite visas šio kurso galimybes, jei gerai suprasite „Javascript“ ir idealiu atveju jau dirbate kaip kūrėjas arba esate „Bootcamp“ absolventas.

Jei dar nesate ten, peržiūrėkite „Scrimba“ puikias nemokamas „JavaScript“ įvadas ir „ES6 +“ įvadas.

Įvadas į instruktorių

Jonathanas Lee Martinas yra programinės įrangos kūrėjas, žiniatinklio pedagogas, pranešėjas ir autorius. Jis padeda kitiems kūrėjams pasiekti savo profesinius ir asmeninius tikslus rašydamas, kalbėdamas, įtraukdamas „Bootcamps“, dirbtuves ir internetines pamokas.

Su klientais, įskaitant tokias kompanijas kaip NASA ir HP, jis yra tik tas asmuo, kuris padės jus mokytis. Taigi pradėkime!

Dvejetainė paieška

„Sweeper“ ir „Splitter“ paieškų grafikas.

Spustelėkite vaizdą, kad pasiektumėte kursą.

Pirmoje grupėje Jonathanas supažindina su „ Big-O“ žymėjimo ir dvejetainės paieškos sąvokomis - algoritmu, su kuriuo dirbsime.

„Big-O“ žymėjimas yra priemonė apibūdinti blogiausią algoritmo našumą. Didelis O iš O (n) sako, kad jei masyvas turi n elementų ilgį, vykdymo laikas bus proporcingas n. Kitaip tariant, septynių įrašų masyvas blogiausiu atveju atliks 7 paieškas, lygiai taip pat, kaip 7 milijonų įrašų masyvas blogiausiu atveju atliks 7 milijonus įrašų. Taip pat galime pasakyti, kad šio algoritmo vykdymo laikas yra tiesinis, kaip parodyta aukščiau pateiktame grafike.

Dvejetainė paieška yra viena iš kelių strategijų, kaip atsakyti į klausimą "Kur šis elementas rodomas sąraše?"

Atsakant į klausimą yra du pagrindiniai metodai:

  • Šlavimo mašina : tikrina kiekvieną sąrašo elementą, kol bus rastas tinkamas elementas.
  • Skirstytuvas / dvejetainė paieška : padalykite sąrašą per pusę, patikrinkite, ar per toli ar ne per toli, kad rastumėte elementą, ieškokite atitinkamai dešinėje arba kairėje pusėje ir kartokite, kol elementas bus.

Mes galime galvoti apie šiuos metodus tikrindami senosios mokyklos popierinę telefonų knygą. Šlavimo metodas apims kiekvieną įrašą nuo pat pradžių, kol bus surastas teisingas. Skirstytuvo metodas yra tas, kurį dažniausiai naudotų žmonės - atsitiktinai atidarydami knygą ir pamatę, ar reikia eiti pirmyn, ar atgal, kol bus įrašas.

Dvejetainė paieška yra efektyvesnė už šlavimo metodą, ypač didesnių sąrašų atveju. Bet tai veikia tik tada, kai sąrašas jau surūšiuotas.

Nors „sweeper“ metodas turi tiesinį vykdymo laiką (žr. Aukščiau pateiktą grafiką) ir O didįjį O (n), skirstytuvo metodas turi po linijinį vykdymo laiką ir O didelį O (log n).

Privaloma

Pirmame iššūkyje Jonathanas ragina mus susitepti rankas, įgyvendinant dvejetainę paiešką tradiciniu stiliumi, tai yra su dideliu O iš O (n), naudojant fiksuotą atminties kiekį ir kilpas.

Jonathanas pateikia mums testų rinkinį, kurį galime naudoti norėdami užtikrinti, kad mūsų sprendimas būtų sėkmingas, ir skatina mus pačius išbandyti iššūkį prieš patikrinant jo įgyvendinimą. Čia nėra spoilerių, todėl eikite į aktorių grupę, kad išbandytumėte patys.

Nors šis sprendimas yra trumpas ir artimas pradinei dvejetainės paieškos formuluotei, tikriausiai pastebėjote, kad sprendimą buvo sunku parašyti ir jis nebuvo geriausias programinės įrangos meistriškumo požiūriu. Skaitykite toliau, kad sužinotumėte būdus, kaip išlyginti sprendimą ...

Rekursija

Šioje grupėje mes stengiamės patobulinti dvejetainę paiešką, įdiegdami naują versiją su keliais apribojimais. Nors mūsų sprendime vis tiek turėtų būti didelis O iš O (n), jis neturėtų naudoti kilpų ir turi naudoti rekursiją. Visi kintamieji turėtų būti inicializuoti su constoperatoriumi, kad jų nebūtų galima mutuoti.

Jonanthanas pradeda mus su karkasine sprendimo versija ir paskui skatina išbandyti iššūkį savarankiškai:

let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion; 

Jei įvykdėte šį iššūkį, tikriausiai matėte, kad šį sprendimą yra daug lengviau perskaityti, tačiau jis yra gana kalbantis. Blogiausiu atveju tai taip pat gali sukelti begalinį recidyvą. Tęskite kursą, kad sužinotumėte, ar yra būdų, kaip supaprastinti sprendimą ...

Uodegos rekursija

Kitos grupės iššūkis yra pagerinti ankstesnį įgyvendinimą mažinant dubliavimą.

Jonathanas perspėja mus, kad sprendimas atrodys blogiau nei du ankstesni sprendimai, tačiau tai leidžia mums atlikti geresnes optimizavimo galimybes toliau. Dabar eikite į kursą, kad išbandytumėte iššūkį ir pamatytumėte Jonathano sprendimą.

Masyvo padalijimas

If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.

We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.

To help us achieve this, Jonathan starts us off with some skeleton code:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; }; 

Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.

Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...

Array View

In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.

Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.

export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args) 

Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.

Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...

Array Partition

In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.

For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:

export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), }); 

Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:

let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args); 

Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.

Dabar eikite į kursą ir išbandykite iššūkį patys. Kaip pabrėžia Jonathanas, šis iššūkis yra keblus, todėl gerai praleisti jo sprendimą, jei užstrigsite per ilgai, bet pirmiausia leisite jam pačiam.

Apvyniojimas

Jūs pasiekėte kurso pabaigą - puikus darbas! Apžvelgėme keletą dvejetainės paieškos būdų, kurie visi turi savo privalumų ir trūkumų, ir sukūrėme puikią raumenų atmintį, kad galėtume efektyviai dirbti su algoritmais.

Dabar, kai pamatėte šešis skirtingus dvejetainės paieškos būdus, tikriausiai pastebėsite, kad jie atsiranda daugelyje skirtingų programavimo vietų.

Metų pabaigoje pasirodys visas Jonathano kursas, kuriame bus 10 algoritmų, tačiau tuo tarpu tikiuosi, kad galėsite gerai panaudoti savo naujai atrastus dvejetainės paieškos įgūdžius.

Laimingo kodavimo :)