Algoritmit Javascriptissa - binaarihaku selitetty

Jos haluat hankkia uusia ongelmanratkaisutaitoja ja tasoittaa tietojenkäsittelytietojasi, älä katso Scrimban ilmaista yhden tunnin kurssia The Working Developer's Guide to Algorithms. Se on suunniteltu niille, joilla ei ole tietojenkäsittelytaustaa ja jotka kokevat hyötyvänsä oppimisesta ajatella algoritmisesti.

Mitä kurssi tekee?

Oppaamme opastaa kuuden erilaisen binaarihakualgoritmin luomisessa. Klassisessa Scrimba-tyylissä se sisältää joukon haasteita matkan varrella, joten saat lihasmuistin, jota tarvitset parantamaan taitojasi ohjelmistokehittäjänä ja toimimaan paremmin algoritmien kanssa.

Opit:

  • Binaarihaku
  • Iso O-merkintä
  • Pakollinen koodi
  • Rekursio
  • Hännän rekursio
  • Taulukon jakaminen
  • Taulukonäkymä
  • Osio

Kutakin algoritmia opetetaan kolmessa vaiheessa:

  • Läpikäynti: Jonathan esittelee algoritmin käsitteellisesti.
  • Toteutus: Likaamme kätemme luomalla omat algoritmin versiot.
  • Ratkaisu: Jonathan näyttää meille toteutuksensa vertailua varten.

Edellytykset

Saat kaiken irti tästä kurssista, jos sinulla on hyvä käsitys Javascriptista ja jos ihannetapauksessa jo työskentelet kehittäjänä tai olet valmistunut Bootcampista.

Jos et ole vielä siellä, tutustu Scrimban upeisiin ilmaisiin opetusohjelmiin Johdanto JavaScriptiin ja Johdanto ES6 +: een.

Johdanto ohjaajalle

Jonathan Lee Martin on ohjelmistokehittäjä, verkkokouluttaja, puhuja ja kirjoittaja. Hän auttaa muita kehittäjiä saavuttamaan ammatilliset ja henkilökohtaiset tavoitteensa kirjoittamalla, puhumalla, mukaansatempaavilla Bootcampeilla, työpajoilla ja online-opetusohjelmilla.

Asiakkaiden, kuten NASA: n ja HP: n kaltaisten asiakkaiden kanssa, hän on vain henkilö, joka vie sinut oppimatkalle. Joten aloitetaan!

Binaarihaku

Kaavio Sweeper vs Splitter -haut.

Napsauta kuvaa päästäksesi kurssille.

Ensimmäisessä näyttelijässä Jonathan esittelee Big-O-notaation ja binäärihaun käsitteet , algoritmin, jonka kanssa työskentelemme.

Big-O-notaatio on tapa kuvata algoritmin pahimmassa tapauksessa suorituskykyä. O: n (n) iso O sanoo, että jos matriisilla on n elementin pituus, ajoaika on verrannollinen n: ään. Toisin sanoen seitsemän merkinnän joukko vie 7 haun pahimmassa tapauksessa, samoin kuin seitsemän miljoonan merkinnän joukko ottaa 7 miljoonaa merkintää pahimmassa tapauksessa. Voimme myös sanoa, että tämän algoritmin ajonaika on lineaarinen, kuten yllä olevassa kaaviossa on esitetty.

Binaarihaku on yksi monista strategioista vastata kysymykseen "Missä tämä elementti näkyy luettelossa?"

Kysymykseen vastattaessa on kaksi pääasiallista lähestymistapaa:

  • Lakaisukone : Tarkistetaan luettelon jokaisen kohteen läpi, kunnes oikea tuote löytyy.
  • Jakaja / binaarihaku : Lista jakaminen kahtia, tarkistamalla, oletko mennyt liian pitkälle vai ei tarpeeksi pitkälle kohteen löytämiseksi, etsimällä joko oikealta tai vasemmalta puolelta ja toistamalla, kunnes kohde löytyy.

Voimme ajatella näitä lähestymistapoja vanhan koulun paperisen puhelinluettelon tarkistamisen kannalta. Lakaisukoneen lähestymistapa edellyttäisi jokaisen merkinnän katsomista alusta asti, kunnes oikea löytyy. Jakaja-lähestymistapa on useimmat ihmiset käyttävät - avaamalla kirjan satunnaisesti ja nähdä, onko sinun mennä eteenpäin vai takaisin, kunnes merkintä on löydetty.

Binaarihaku on tehokkaampi kuin lakaista lähestymistapa, etenkin suuremmissa luetteloissa. Mutta se toimii vain, kun luettelo on jo lajiteltu.

Vaikka lakaisukoneella on lineaarinen käyntiaika (katso yllä oleva kaavio) ja O: n iso O (n), jakajan lähestymistavassa on sublineaarinen ajoaika ja iso O: n O (log n).

Pakollinen

Ensimmäisessä haastattelussa Jonathan kannustaa meitä likaantumaan toteuttamalla binäärihakua perinteiseen tyyliin, eli O: n (O) isolla O: lla, käyttämällä kiinteää määrää muistia ja silmukoita.

Jonathan tarjoaa meille testipaketin, jolla voimme varmistaa ratkaisumme onnistumisen, ja kannustaa meitä kokeilemaan haastetta itse ennen kuin tarkistamme hänen toteutuksensa. Ei spoilereita täällä, joten mene näyttelijöille kokeilemaan itseäsi.

Vaikka tämä ratkaisu on lyhyt ja lähellä binäärihaun alkuperäistä muotoilua, olet todennäköisesti huomannut, että ratkaisua oli vaikea kirjoittaa eikä se ollut paras ratkaisu ohjelmiston käsityötaidon näkökulmasta. Lue lisää tapoja tasoittaa ratkaisua ...

Rekursio

Tässä näyttelijässä tarkastelemme binäärihaun parantamista toteuttamalla uuden version muutamalla rajoituksella. Vaikka ratkaisumme pitäisi silti olla iso O: sta O (n), sen ei tulisi käyttää silmukoita ja sen on käytettävä rekursiota. Kaikki muuttujat tulisi alustaa constoperaattorin kanssa, jotta niitä ei voi mutatoida.

Jonanthan aloittaa meidät ratkaisun luurankoversiolla ja kannustaa sitten kokeilemaan haastetta yksin:

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

Jos olet suorittanut tämän haasteen, olet luultavasti nähnyt, että tämä ratkaisu on paljon helpompi lukea, mutta on melko yksityiskohtainen. Pahimmassa tapauksessa se voi johtaa myös loputtomaan rekursioon. Jatka kurssilla nähdäksesi, onko ratkaisun virtaviivaistamiseksi tapoja ...

Hännän rekursio

Seuraavan näyttelijöiden haasteena on parantaa aiempaa toteutustamme vähentämällä päällekkäisyyksiä.

Jonathan varoittaa, että ratkaisu näyttää huonommalta kuin kaksi edellistä ratkaisua, mutta se kuitenkin asettaa meidät parempiin optimointeihin. Suuntaa kurssille nyt kokeilla haastetta itse ja nähdä Jonathanin ratkaisu.

Taulukon jakaminen

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.

Suuntaa kurssille nyt ja kokeile itse haastetta. Kuten Jonathan huomauttaa, tämä haaste on hankala, joten on ok siirtyä hänen ratkaisuunsa, jos juutut liian kauan, mutta annat sen mennä ensin yksin.

Paketoida

Olet päässyt kurssin loppuun - hyvää työtä! Olemme käsitelleet useita lähestymistapoja binaarihakuun, joilla kaikilla on omat edut ja haitat, ja olemme rakentaneet hienon lihasmuistin tehokkaaseen työskentelyyn algoritmien kanssa.

Nyt kun olet nähnyt kuusi erilaista lähestymistapaa binäärihakuun, huomaat todennäköisesti, että se tulee esiin monissa eri paikoissa ohjelmoinnissa.

Jonathanin koko kurssi, jossa on 10 algoritmia, ilmestyy vuoden lopulla, mutta sillä välin toivon, että voit hyödyntää uutta löytämääsi binäärihakutaitoa.

Hyvää koodausta :)