Esittely

Erilaisiin tietorakenteisiin tallennetun datan etsiminen on tärkeä osa lähes jokaista sovellusta.

Haun tekemiseen on käytettävissä monia erilaisia algoritmeja, joista jokaisella on erilainen toteutus ja jotka perustuvat erilaisiin tietorakenteisiin.

Kyky valita tietty algoritmi tiettyä tehtävää varten on tärkeä taito kehittäjille, ja se voi merkitä eroa nopean, luotettavan ja vakaan sovelluksen ja sovelluksen välillä, joka murenee yksinkertaisesta pyynnöstä.

• Jäsenoperaattorit
• Lineaarinen haku
• Binäärinen haku
• Hyppyhaku
• Fibonacci-haku
• Exponentiaalinen haku
• Interpolointihaku

Jäsenyysoperaattorit

Algoritmit kehittyvät ja optimoituvat ajan mittaan jatkuvan kehityksen ja tarpeen löytää tehokkaimmat ratkaisut taustalla oleviin ongelmiin eri aloilla.

Yksi yleisimmistä ongelmista tietojenkäsittelytieteen alalla on etsiä kokoelman läpi ja määrittää, onko jokin tietty objekti kokoelmassa vai ei.

Lähes jokaisella ohjelmointikielellä on oma toteutuksensa perushakualgoritmille, yleensä funktiona, joka palauttaa Boolean-arvon True tai False, kun kohde löytyy tietystä kokoelmasta.

Pythonissa helpoin tapa etsiä kohdetta on käyttää jäsenyysoperaattoreita, jotka on nimetty näin, koska niiden avulla voidaan määrittää, onko tietty kohde kokoelman jäsen.

Näitä operaattoreita voidaan käyttää minkä tahansa Pythonissa olevan iteroituvan tietorakenteen kanssa, mukaan lukien merkkijonot, luettelot ja monisteet.

• in – Palauttaa arvon True, jos annettu alkio kuuluu rakenteeseen.
• not in – Palauttaa True, jos annettu elementti ei ole osa rakennetta.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Membership-operaattorit riittävät silloin, kun halutaan vain selvittää, onko tietyn merkkijonon sisällä osajono, tai määritellä, leikkaavatko kaksi merkkijonoa, listaa tai tuplea niiden sisältämien objektien suhteen.

Useimmissa tapauksissa tarvitsemme kohteen sijainnin sarjassa sen lisäksi, että määrittelemme, onko se olemassa vai ei; jäsenyysoperaattorit eivät täytä tätä vaatimusta.

On olemassa monia hakualgoritmeja, jotka eivät ole riippuvaisia sisäänrakennetuista operaattoreista ja joita voidaan käyttää arvojen nopeampaan ja/tai tehokkaampaan etsimiseen. Lisäksi ne voivat tuottaa enemmän tietoa, kuten elementin sijainnin kokoelmassa, sen sijaan, että pystyttäisiin vain määrittämään sen olemassaolo.

Lineaarinen haku

Lineaarinen haku on yksi yksinkertaisimmista hakualgoritmeista ja helpoin ymmärtää. Voimme ajatella sitä rampattuna versiona Pythonin in-operaattorin omasta toteutuksesta.

Algoritmi koostuu joukkojen iteroinnista ja palauttaa kohteen ensimmäisen esiintymän indeksin, kun se on löydetty:

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Jos siis käytämme funktiota laskemiseen:

>>> print(LinearSearch(, 2))

Koodia suoritettaessa meitä tervehtii:

1

Tämä on etsimämme kohteen ensimmäisen esiintymän indeksi – pitäen mielessä, että Pythonin indeksit ovat 0-pohjaisia.

Lineaarisen haun aikakompleksisuus on O(n), mikä tarkoittaa, että suoritukseen kuluva aika kasvaa syöttöluettelomme lys kohtien määrän myötä.

Lineaarihakua ei käytetä käytännössä usein, koska sama tehokkuus voidaan saavuttaa käyttämällä sisäänrakennettuja menetelmiä tai olemassa olevia operaattoreita, eikä se ole yhtä nopea tai tehokas kuin muut hakualgoritmit.

Lineaarinen haku sopii hyvin silloin, kun on löydettävä lajittelemattomasta kokoelmasta kohteen ensimmäinen esiintymä, koska toisin kuin useimmat muut hakualgoritmit, se ei edellytä, että kokoelma on lajiteltu ennen haun aloittamista.

Binäärinen haku

Binäärinen haku noudattaa hajota ja hallitse -menetelmää. Se on nopeampi kuin lineaarinen haku, mutta vaatii, että joukko on lajiteltu ennen algoritmin suorittamista.

Emme etsi arvoa val lajitellusta joukosta, algoritmi vertaa arvoa val joukon keskimmäisen alkion arvoon, jota kutsumme nimellä mid.

• Jos mid on etsimämme alkio (paras tapaus), palautamme sen indeksin.
• Jos ei, tunnistamme, kummalla puolella mid val on todennäköisemmin sen perusteella, onko val pienempi vai suurempi kuin mid, ja hylkäämme joukon toisen puolen.
• Selvitämme sitten rekursiivisesti tai iteratiivisesti samat vaiheet valitsemalla uuden arvon mid:lle, vertaamalla sitä arvoon val ja hylkäämällä puolet mahdollisista osumista jokaisessa algoritmin iteraatiossa.

Binäärihakualgoritmi voidaan kirjoittaa joko rekursiivisesti tai iteratiivisesti. Rekursio on Pythonissa yleensä hitaampi, koska se vaatii uusien pinokehysten varaamista.

Koska hyvän hakualgoritmin pitäisi olla mahdollisimman nopea ja tarkka, tarkastellaan binäärihaun iteratiivista toteutusta:

Jos laskemme funktiolla:

>>> BinarySearch(, 20)

Saatamme tulokseksi:

1

Joka on haettavan arvon indeksi.

Toiminto, jonka algoritmi suorittaa seuraavaksi jokaisessa iteraatiossa, on yksi useista mahdollisuuksista:

• Palautamme nykyisen elementin indeksin
• Haemme läpi matriisin vasemman puoliskon
• Haemme läpi matriisin oikean puoliskon

Voimme valita vain yhden vaihtoehdon kutakin iteraatiota kohti, ja mahdollisten täsmäämismahdollisuuksiemme varasto jaetaan kahdella jokaisella iteraatiolla. Tämä tekee binäärihaun aikakompleksisuudesta O(log n).

Yksi binäärihaun haittapuoli on se, että jos jokin elementti esiintyy joukossa useaan kertaan, se ei palauta ensimmäisen elementin indeksiä, vaan keskimmäistä lähinnä olevan elementin indeksin:

>>> print(BinarySearch(, 4))

Tämän koodinpätkän suorittaminen antaa tulokseksi keskimmäisen elementin indeksin:

1

Vertauksena lineaarisen haun suorittaminen samalle joukolle antaisi tulokseksi:

0

Joka on ensimmäisen elementin indeksi. Emme kuitenkaan voi kategorisesti sanoa, että binäärihaku ei toimi, jos joukossa on sama elementti kahdesti – se voi toimia aivan kuten lineaarihaku ja palauttaa elementin ensimmäisen esiintymän joissakin tapauksissa.

Jos suoritamme binäärihaun esimerkiksi joukolle ja etsimme hakusanalla 4, saisimme tulokseksi 3.

Binäärihakua käytetään käytännössä melko yleisesti, koska se on tehokas ja nopea verrattuna lineaarihakuun. Sillä on kuitenkin joitakin puutteita, kuten sen riippuvuus //-operaattorista. On olemassa monia muitakin hajota ja hallitse -hakualgoritmeja, jotka on johdettu binäärihausta, tarkastellaan seuraavaksi muutamia niistä.

Hyppyhaku

Hyppyhaku on samankaltainen kuin binäärihaku siinä mielessä, että se työskentelee lajitellulla joukolla ja käyttää samankaltaista hajota ja hallitse -lähestymistapaa etsiessään sen läpi.

Se voidaan luokitella lineaarisen hakualgoritmin parannukseksi, koska se on riippuvainen lineaarisesta hausta suorittaessaan varsinaista vertailua arvoa etsittäessä.

Lajitellun matriisin annettuna, sen sijaan, että hakisimme matriisin elementtien läpi inkrementaalisesti, etsimme hyppäyksittäin. Jos siis syöttöluettelossamme lys on hyppykoko hyppy, algoritmimme tarkastelee elementtejä järjestyksessä lys, lys, lys, lys, lys ja niin edelleen.

Kullakin hypyllä tallennamme edellisen tarkastelemamme arvon ja sen indeksin. Kun löydämme arvojoukon, jossa lys<elementti<lys, suoritamme lineaarisen haun, jossa lys on hakujoukkomme vasemmanpuoleisin elementti ja lys on hakujoukkomme oikeanpuoleisin elementti:

Koska tämä on monimutkainen algoritmi, tarkastellaan hyppyhakujen vaiheittaista laskentaa tällä syötteellä:

>>> print(JumpSearch(, 5))

• Hyppyhakujen tarkoituksena olisi aluksi määrittää hyppyjen koon lasku laskemalla math.sqrt(len(lys)). Koska meillä on 9 elementtiä, hyppykoko olisi √9 = 3.
• Seuraavaksi lasketaan muuttujan right arvo, joka on matriisin pituuden minimi miinus 1 tai left+jump arvo, joka meidän tapauksessamme olisi 0+3= 3. Koska 3 on pienempi kuin 8, käytämme right:n arvona 3:a.
• Nyt tarkistamme, onko hakuelementtimme 5 lys ja lys välissä. Koska 5 ei ole 1:n ja 4:n välissä, siirrymme eteenpäin.
• Seuraavaksi suoritamme laskutoimitukset uudelleen ja tarkistamme, onko hakuelementtimme lys ja lys välissä, jossa 6 on 3+hyppy. Koska 5 on 4:n ja 7:n välissä, teemme lineaarisen haun lys ja lys välissä oleville elementeille ja palautamme elementtimme indeksin seuraavasti:

4

Hyppyhakujen aikakompleksisuus on O(√n), missä √n on hyppyjen koko ja n on listan pituus, mikä sijoittaa hyppyhakuja lineaarisen haun ja binäärisen haun algoritmien välimaastoon tehokkuuden suhteen.

Hyppyhaun tärkein yksittäinen etu binäärihakuun verrattuna on se, että se ei ole riippuvainen jako-operaattorista (/).

Useimmissa suorittimissa jako-operaattorin käyttäminen on kallista verrattuna muihin aritmeettisiin perusoperaatioihin (yhteenlasku, vähennyslasku ja kertolasku), koska jakoalgoritmin toteutus on iteratiivinen.

Kustannus sinänsä on hyvin pieni, mutta kun läpikäytävien elementtien määrä on hyvin suuri ja suoritettavien jako-operaatioiden määrä lisääntyy, kustannus voi kasvaa asteittain. Siksi hyppyhaku on parempi kuin binäärihaku, kun järjestelmässä on suuri määrä elementtejä, jolloin pienelläkin nopeuden lisäyksellä on merkitystä.

Tehdäksemme hyppyhakua nopeammaksi, voisimme käyttää binäärihakua tai jotain muuta sisäistä hyppyhakua lohkojen läpikäyntiin sen sijaan, että luottaisimme paljon hitaampaan lineaarihakuun.

Fibonacci-haku

Fibonacci-haku on toinen jako- ja hallinta-algoritmi, joka omaa yhtäläisyyksiä sekä binäärihaun että hyppyhakuun kanssa. Se on saanut nimensä siitä, että se käyttää Fibonacci-lukuja lohkokoon tai hakualueen laskemiseen jokaisessa vaiheessa.

Fibonacci-luvut alkavat nollasta ja noudattavat kaavaa 0, 1, 1, 1, 2, 3, 5, 8, 13, 21…, jossa kukin alkio on sitä välittömästi edeltävien kahden luvun yhteenlasku.

Algoritmi työskentelee kolmella Fibonacci-luvulla kerrallaan. Kutsutaan näitä kolmea lukua fibM, fibM_minus_1 ja fibM_minus_2, missä fibM_minus_1 ja fibM_minus_2 ovat ne kaksi lukua, jotka ovat välittömästi ennen fibM järjestyksessä:

fibM = fibM_minus_1 + fibM_minus_2

Alkuperäistämme arvot arvoihin 0,1 ja 1 tai kolmeen ensimmäiseen Fibonaccin järjestyksen numeroon, jotta vältetään indeksivirheen saaminen siinä tapauksessa, että etsintämatriisissamme lys on hyvin pieni määrä elementtejä.

Valitaan sitten Fibonacci-sarjan pienin luku, joka on suurempi tai yhtä suuri kuin hakumassamme lys olevien elementtien lukumäärä, arvoksi fibM, ja kaksi sitä välittömästi edeltävää Fibonacci-lukua arvoiksi fibM_minus_1 ja fibM_minus_2. Kun matriisissa on jäljellä elementtejä ja fibM:n arvo on suurempi kuin yksi, me:

• Vertaamme val:n arvoon lohkon arvoon alueella fibM_minus_2 asti ja palautamme elementin indeksin, jos se täsmää.
• Jos arvo on suurempi kuin tarkasteltavana oleva alkio, siirretään fibM, fibM_minus_1 ja fibM_minus_2:n arvot Fibonacci-sekvenssissä kaksi askelta alaspäin ja palautetaan indeksi alkion indeksiin.
• Jos arvo on pienempi kuin tarkasteltavana oleva alkio, siirretään fibM:n, fibM_minus_1:n ja fibM_minus_2:n arvot yhden askeleen alemmas Fibonacci-sekvenssissä.

Katsotaanpa tämän algoritmin Python-toteutusta:

Jos käytämme FibonacciSearch-funktiota laskemiseen:

>>> print(FibonacciSearch(, 6))

Katsotaanpa tämän haun vaiheittaista prosessia:

• Pienimmän Fibonacciluvun määrittäminen, joka on suurempi tai yhtä pitkä kuin listan pituus fibM; tässä tapauksessa pienin vaatimuksemme täyttävä Fibonacciluku on 13.
• Arvot annettaisiin seuraavasti:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • indeksi = -1
• Seuraavaksi tarkastetaan alkio lys, jossa 4 on pienin -1+5 . Koska lys:n arvo on 5, joka on pienempi kuin etsimämme arvo, siirretään Fibonacci-lukuja yhden askeleen alaspäin järjestyksessä, jolloin arvot:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • indeksi = 4
• Seuraavaksi tarkistamme alkion lys, jossa 7 on minimi 4+3. Koska lys:n arvo on 8, joka on suurempi kuin etsimämme arvo, siirretään Fibonaccin numerot kaksi askelta alaspäin järjestyksessä.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • indeksi = 4
• Tarkistamme nyt alkion lys, jossa 5 on minimi 4+1 . lys:n arvo on 6, joka on etsimämme arvo!

Tulos on odotetusti:

5

Fibonacci-haun aikakompleksisuus on O(log n); sama kuin binäärihaun. Tämä tarkoittaa, että algoritmi on nopeampi kuin lineaarinen haku ja hyppyhaku useimmissa tapauksissa.

Fibonacci-hakua voidaan käyttää silloin, kun meillä on hyvin suuri määrä elementtejä haettavana ja haluamme vähentää tehottomuutta, joka liittyy jako-operaattoriin tukeutuvan algoritmin käyttöön.

Fibonacci-haun käytön lisäetuna on se, että se pystyy käsittelemään syöttömatriiseja, jotka ovat liian suuria CPU:n välimuistiin tai RAM-muistiin mahtuakseen, koska se hakee elementtejä kasvavin askelin eikä kiinteässä koossa.

Exponentiaalinen haku

Exponentiaalinen haku on toinen hakualgoritmi, joka voidaan toteuttaa melko yksinkertaisesti Pythonissa verrattuna hyppyhakuun ja Fibonacci-hakuun, jotka molemmat ovat hieman monimutkaisia. Se tunnetaan myös nimillä gallup-haku, tuplaushaku ja Struzik-haku.

Exponentiaalinen haku on riippuvainen binäärihausta arvojen lopullisen vertailun suorittamiseksi. Algoritmi toimii seuraavasti:

• Määritetään alue, jossa etsimämme elementti todennäköisesti on
• Käytetään binäärihakua alueen osalta elementin tarkan indeksin löytämiseksi

Exponentiaalisen hakualgoritmin Python-toteutus on:

Jos käytämme funktiota löytääksemme arvon:

>>> print(ExponentialSearch(,3))

Algoritmi toimii seuraavasti:

• Tarkistamme, vastaako listan ensimmäinen elementti etsimäämme arvoon – koska lys on 1 ja etsimme arvoa 3, asetamme indeksin arvoksi 1 ja jatkamme eteenpäin.
• Käymme läpi kaikki listan elementit, ja kun indeksin sijalla oleva elementti on pienempi tai yhtä suuri kuin arvomme, kasvatamme eksponentiaalisesti index:n arvoa kahden kerrannaisina:
  • indeksi = 1, lys on 2, joka on pienempi kuin 3, joten indeksi kerrotaan 2:lla ja asetetaan arvoon 2.
  • indeksi = 2, lys on 3, joka on yhtä suuri kuin 3, joten indeksi kerrotaan 2:lla ja asetetaan arvoon 4.
  • indeksi = 4, lys on 5, mikä on suurempi kuin 3; silmukka katkaistaan tässä vaiheessa.
• Sen jälkeen suoritetaan binäärihaku viipaloimalla lista; arr. Pythonissa tämä tarkoittaa, että alilista sisältää kaikki elementit 4. elementtiin asti, joten itse asiassa kutsumme:

>>> BinarySearch(, 3)

joka palauttaisi:

2

mikä on etsimämme elementin indeksi sekä alkuperäisessä listassa että viipaloidussa listassa, jonka välitämme binäärihakualgoritmille.

Eksponentiaalinen haku toimii O(log i) ajassa, missä i on etsimämme elementin indeksi. Pahimmassa tapauksessa aikakompleksisuus on O(log n), kun viimeinen elementti on etsimämme elementti (n on joukon pituus).

Exponentiaalihaku toimii paremmin kuin binäärihaku, kun etsimämme elementti on lähempänä joukon alkua. Käytännössä käytämme eksponenttihakua, koska se on yksi tehokkaimmista hakualgoritmeista rajoittamattomille tai äärettömille matriiseille.

Interpolointihaku

Interpolointihaku on toinen hajota ja hallitse -algoritmi, joka on samanlainen kuin binäärihaku. Toisin kuin binäärihaku, se ei aina aloita hakua keskeltä. Interpolointihaku laskee etsittävän elementin todennäköisen sijainnin kaavalla:

index = low + )*(high-low) / (lys-lys)]

Jossa muuttujat ovat:

• lys – syötemassamme
• val – elementti, jota etsimme
• index – etsittävän elementin todennäköinen indeksi. Tämä lasketaan suuremmaksi, kun val on arvoltaan lähempänä joukon lopussa olevaa elementtiä (lys), ja pienemmäksi, kun val on arvoltaan lähempänä joukon alussa olevaa elementtiä (lys)
• low – joukon alkuindeksi
• high – joukon viimeinen indeksi

Algoritmi tekee hakuja laskemalla index:n arvon:

• Jos vastaavuus löytyy (kun lys == val), palautetaan indeksi
• Jos val:n arvo on pienempi kuin lys, indeksin arvo lasketaan uudelleen käyttäen vasemmanpuoleisen alaruudun kaavaa
• Jos val:n arvo on suurempi kuin lys, indeksin arvo lasketaan uudelleen käyttäen oikean alaruudun kaavaa

Mennään eteenpäin ja toteutetaan interpolointihaku Pythonilla:

Jos laskemme funktion avulla:

>>> print(InterpolationSearch(, 6))

Alkuarvomme olisivat:

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Koska lys on 6, joka on etsimämme arvo, lopetamme suorituksen ja palautamme tuloksen:

5

Jos meillä on suuri määrä elementtejä, eikä indeksiä voida laskea yhdessä iteraatiossa, jatkamme indeksin arvojen laskemista uudelleen sen jälkeen, kun olemme säätäneet kaavan high- ja low-arvoja.

Interpolointihaun aikakompleksisuus on O(log log n), kun arvot ovat tasaisesti jakautuneita. Jos arvot eivät ole tasaisesti jakautuneita, pahimmassa tapauksessa aikakompleksisuus on O(n), eli sama kuin lineaarisessa haussa.

Interpolointihaku toimii parhaiten tasaisesti jakautuneilla, lajitelluilla matriiseilla. Siinä missä binäärihaku aloittaa keskeltä ja jakaa aina kahtia, interpolointihaku laskee elementin todennäköisen sijainnin ja tarkistaa indeksin, jolloin elementti löytyy todennäköisemmin pienemmällä määrällä iteraatioita.

Miksi käyttää Pythonia hakuun?

Python on erittäin helppolukuinen ja tehokas verrattuna vanhoihin ohjelmointikieliin, kuten Javaan, Fortraniin, C:hen, C++:aan jne. Yksi keskeinen etu Pythonin käyttämisessä hakualgoritmien toteuttamiseen on se, että sinun ei tarvitse huolehtia castingista tai eksplisiittisestä tyypityksestä.

Pythonissa useimmat käsittelemistämme hakualgoritmeista toimivat yhtä hyvin, jos etsimme merkkijonoa. Muista, että joudumme tekemään muutoksia koodiin algoritmeille, jotka käyttävät hakuelementtiä numeerisiin laskutoimituksiin, kuten interpolointihakualgoritmi.

Python on myös hyvä paikka aloittaa, jos haluat vertailla eri hakualgoritmien suorituskykyä aineistollesi; prototyypin rakentaminen Pythonissa on helpompaa ja nopeampaa, koska voit tehdä enemmän vähemmillä koodiriveillä.

Voidaksemme verrata toteuttamiemme hakualgoritmien suorituskykyä tietokokonaisuuteen, voimme käyttää Pythonin aikakirjastoa:

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Johtopäätös

On monia mahdollisia tapoja etsiä elementtiä kokoelmasta. Tässä artikkelissa yritimme käsitellä muutamia hakualgoritmeja ja niiden toteutuksia Pythonissa.

Käytettävän algoritmin valinta perustuu etsittävään dataan; syötemäärään, jota olemme kutsuneet lys kaikissa toteutuksissamme.

• Jos haluat etsiä lajittelemattoman array:n läpi tai löytää hakumuuttujan ensimmäisen esiintymän, paras vaihtoehto on lineaarinen haku.
• Jos haluat etsiä lajitellun array:n läpi, on monia vaihtoehtoja, joista yksinkertaisin ja nopein menetelmä on binäärihaku.
• Jos sinulla on lajiteltu joukko, jonka haluat hakea läpi ilman jako-operaattoria, voit käyttää joko hyppyhakua tai Fibonacci-hakua.
• Jos tiedät, että etsimäsi alkio on todennäköisesti lähempänä joukon alkua, voit käyttää eksponenttihakua.
• Jos lajiteltu joukkosi on myös tasaisesti jakautunut, nopein ja tehokkain hakualgoritmi olisi interpolointihaku.

Jos et ole varma, mitä algoritmia käyttäisit lajitellun joukon kanssa, kokeile kutakin niistä yhdessä Pythonin aikakirjaston kanssa ja valitse se, joka toimii parhaiten aineistollasi.