Bevezetés

A különböző adatstruktúrákban tárolt adatok keresése szinte minden egyes alkalmazás fontos része.

A keresés során számos különböző algoritmus áll rendelkezésre, és mindegyiknek különböző implementációi vannak, és különböző adatstruktúrákra támaszkodnak a feladat elvégzéséhez.

Az adott feladathoz egy adott algoritmus kiválasztásának képessége kulcsfontosságú készség a fejlesztők számára, és ez jelentheti a különbséget egy gyors, megbízható és stabil alkalmazás és egy olyan alkalmazás között, amely egy egyszerű kéréstől összeomlik.

• Tagsági operátorok
• Lineáris keresés
• Bináris keresés
• Ugráskeresés
• Fibonacci keresés
• Exponenciális keresés
• Interpolációs keresés

.

Tagsági operátorok

Az algoritmusok a folyamatos fejlődés és a különböző területek mögöttes problémáira a leghatékonyabb megoldások megtalálásának igénye miatt idővel fejlődnek és optimalizálódnak.

A számítástechnika területén az egyik leggyakoribb probléma egy gyűjteményben való keresés és annak meghatározása, hogy egy adott objektum jelen van-e a gyűjteményben vagy sem.

Majdnem minden programozási nyelv rendelkezik egy alapvető keresési algoritmus saját implementációjával, általában egy olyan függvény formájában, amely Boolean True vagy False értéket ad vissza, ha egy elemet találtunk egy adott gyűjteményben.

A Pythonban egy objektum keresésének legegyszerűbb módja a tagsági operátorok használata – azért nevezték el így, mert lehetővé teszik számunkra annak megállapítását, hogy egy adott objektum tagja-e egy gyűjteménynek.

Az operátorok bármely iterálható adatstruktúrával használhatók a Pythonban, beleértve a stringeket, listákat és a tuplikat.

• in – True értéket ad vissza, ha az adott elem a struktúra része.
• not in – True-t ad vissza, ha az adott elem nem része a struktúrának.

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

A tagsági operátorok elegendőek, ha csak azt kell megtudnunk, hogy létezik-e egy részlánc egy adott karakterláncon belül, vagy meg kell határoznunk, hogy két String, Lista vagy Tuple metszi-e egymást a bennük lévő objektumok szempontjából.

A legtöbb esetben szükségünk van az elem pozíciójára a sorozatban, amellett, hogy meghatározzuk, hogy létezik-e vagy sem; a tagsági operátorok nem felelnek meg ennek a követelménynek.

Számos olyan keresési algoritmus létezik, amely nem függ a beépített operátoroktól, és amelyekkel gyorsabban és/vagy hatékonyabban kereshetünk értékeket. Ráadásul több információt is szolgáltathatnak, például az elem pozícióját a gyűjteményben, ahelyett, hogy csak a létezését tudnák meghatározni.

Lineáris keresés

A lineáris keresés az egyik legegyszerűbb keresési algoritmus, és a legkönnyebben érthető. Gondolhatunk rá úgy is, mint a Python in operátor in saját implementációjának felturbózott változatára.

Az algoritmus egy tömbön való iterálásból áll, és egy elem első előfordulásának indexét adja vissza, amint megtaláljuk:

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

Ha tehát a függvényt használjuk a számításhoz:

>>> print(LinearSearch(, 2))

A kód végrehajtásakor a következő eredményt kapjuk:

1

Ez a keresett elem első előfordulásának indexe – szem előtt tartva, hogy a Python indexek 0-alapúak.

A lineáris keresés időbonyolultsága O(n), ami azt jelenti, hogy a végrehajtáshoz szükséges idő a bemeneti listánk lys elemeinek számával növekszik.

A lineáris keresést a gyakorlatban nem gyakran használják, mert ugyanolyan hatékonyságot lehet elérni beépített módszerekkel vagy meglévő operátorokkal, és nem olyan gyors és hatékony, mint más keresési algoritmusok.

A lineáris keresés jól alkalmazható, amikor egy elem első előfordulását kell megtalálnunk egy rendezetlen gyűjteményben, mert a legtöbb más keresési algoritmussal ellentétben nem követeli meg, hogy a gyűjteményt rendezni kell a keresés megkezdése előtt.

Bináris keresés

A bináris keresés az oszd meg és uralkodj módszert követi. Gyorsabb, mint a lineáris keresés, de megköveteli, hogy az algoritmus végrehajtása előtt a tömb legyen rendezve.

Tegyük fel, hogy egy val értéket keresünk egy rendezett tömbben, az algoritmus összehasonlítja a val értéket a tömb középső elemének értékével, amit mid-nak fogunk hívni.

• Ha mid a keresett elem (legjobb esetben), akkor visszaadjuk az indexét.
• Ha nem, akkor azonosítjuk, hogy mid melyik oldalán van nagyobb valószínűséggel val az alapján, hogy val kisebb vagy nagyobb, mint mid, és elvetjük a tömb másik oldalát.
• Ezután rekurzívan vagy iteratívan követjük ugyanazokat a lépéseket, kiválasztva egy új értéket mid számára, összehasonlítva azt val-vel, és az algoritmus minden egyes iterációjában elvetjük a lehetséges egyezések felét.

A bináris keresési algoritmus megírható rekurzívan vagy iteratívan. A rekurzió általában lassabb Pythonban, mert új veremkeretek kiosztását igényli.

Mivel egy jó keresőalgoritmusnak minél gyorsabbnak és pontosabbnak kell lennie, nézzük a bináris keresés iteratív megvalósítását:

Ha a függvény segítségével kiszámítjuk:

>>> BinarySearch(, 20)

Az eredményt kapjuk:

1

Mely a keresett érték indexe.

A művelet, amit az algoritmus minden iterációban legközelebb végrehajt, több lehetőség közül választhat:

• Az aktuális elem indexének visszaadása
• A tömb bal felének átkutatása
• A tömb jobb felének átkutatása

Iterációnként csak egy lehetőséget választhatunk, és a lehetséges találatok tárháza minden iterációban ketté válik. Ezáltal a bináris keresés időbonyolultsága O(log n).

A bináris keresés egyik hátránya, hogy ha egy elemnek több előfordulása van a tömbben, akkor nem az első elem indexét adja vissza, hanem a középsőhöz legközelebbi elem indexét:

>>> print(BinarySearch(, 4))

Ez a kódrészlet lefuttatásával a középső elem indexét kapjuk:

1

Ezzel összehasonlításképpen egy lineáris keresés végrehajtása ugyanezen a tömbön a következőt adná vissza:

0

Ami az első elem indexe. Nem mondhatjuk azonban kategorikusan, hogy a bináris keresés nem működik, ha egy tömb kétszer tartalmazza ugyanazt az elemet – ugyanúgy működhet, mint a lineáris keresés, és bizonyos esetekben az elem első előfordulását adja vissza.

Ha például bináris keresést végzünk a tömbön, és 4-et keresünk, akkor 3 lenne az eredmény.

A bináris keresést a gyakorlatban elég gyakran használják, mert a lineáris kereséshez képest hatékony és gyors. Van azonban néhány hiányossága, például az // operátorra való támaszkodás. Számos más oszd meg és uralkodj keresési algoritmus létezik, amelyek a bináris keresésből származnak, ezek közül vizsgáljunk meg néhányat a következőkben.

Ugráskeresés

Az ugráskeresés abban hasonlít a bináris kereséshez, hogy egy rendezett tömbön dolgozik, és hasonló oszd meg és uralkodj megközelítést használ a kereséshez.

A lineáris keresési algoritmus továbbfejlesztésének tekinthető, mivel a lineáris kereséstől függ, hogy egy érték keresésekor a tényleges összehasonlítást elvégezze.

Adva egy rendezett tömböt, ahelyett, hogy a tömb elemein inkrementálisan keresnénk, ugrásokban keresünk. Tehát a lys bemeneti listánkban, ha az ugrásméretünk ugrás, az algoritmusunk a lys, lys, lys, lys, lys és így tovább sorrendben fogja megvizsgálni az elemeket.

Minden ugrásnál tároljuk az előzőleg megnézett értéket és annak indexét. Ha találunk egy olyan értékhalmazt, ahol lys<elem<lys, akkor lineáris keresést végzünk úgy, hogy lys a keresési halmazunk bal szélső eleme és lys a jobb szélső eleme:

Mivel ez egy összetett algoritmus, nézzük meg az ugrókeresés lépésről lépésre történő kiszámítását ezzel a bemenettel:

>>> print(JumpSearch(, 5))

• Az ugrókeresés először az math.sqrt(len(lys)) kiszámításával határozná meg az ugrásméretet. Mivel 9 elemünk van, az ugrásméret √9 = 3 lenne.
• Ezután kiszámítjuk a right változó értékét, ami a tömb hosszának mínusz 1, vagy a left+jump értékének minimuma, ami a mi esetünkben 0+3= 3 lenne. Mivel 3 kisebb, mint 8, ezért a right értékeként 3-at használjuk.
• Most ellenőrizzük, hogy a keresett elemünk, az 5, lys és lys között van-e. Mivel 5 nem 1 és 4 között van, továbblépünk.
• A következő lépésben ismét elvégezzük a számításokat, és ellenőrizzük, hogy a keresett elemünk lys és lys között van-e, ahol 6 3+ugrás. Mivel 5 4 és 7 között van, lineáris keresést végzünk a lys és lys közötti elemeken, és így adjuk vissza az elemünk indexét:

4

Az ugrókeresés időbonyolultsága O(√n), ahol √n az ugrás mérete, n pedig a lista hossza, így az ugrókeresés hatékonyságát tekintve a lineáris és a bináris keresési algoritmusok közé kerül.

Az ugrókeresés legfontosabb előnye a bináris kereséssel szemben az, hogy nem támaszkodik az osztás operátorra (/).

A legtöbb CPU-n az osztás operátor használata költséges a többi alapvető aritmetikai művelethez (összeadás, kivonás és szorzás) képest, mivel az osztási algoritmus végrehajtása iteratív.

A költség önmagában nagyon kicsi, de ha a keresendő elemek száma nagyon nagy, és az elvégzendő osztási műveletek száma nő, a költségek fokozatosan nőhetnek. Ezért az ugrókeresés jobb, mint a bináris keresés, ha nagy elemszámú rendszerről van szó, ahol már egy kis sebességnövekedés is számít.

Az ugrókeresés gyorsabbá tételéhez használhatunk bináris keresést vagy egy másik belső ugrókeresést a blokkok átkutatására, ahelyett, hogy a sokkal lassabb lineáris keresésre támaszkodnánk.

Fibonacci keresés

A fibonacci keresés egy másik oszd meg és uralkodj algoritmus, amely hasonlóságot mutat a bináris kereséssel és az ugrókereséssel is. Nevét onnan kapta, hogy Fibonacci-számokat használ a blokkméret vagy keresési tartomány kiszámításához minden egyes lépésben.

A Fibonacci-számok a nullával kezdődnek, és a 0, 1, 1, 1, 2, 3, 5, 8, 13, 21… mintát követik, ahol minden elem az azt közvetlenül megelőző két szám összeadásából áll.

Az algoritmus egyszerre három Fibonacci-számmal dolgozik. Nevezzük a három számot fibM, fibM_minus_1 és fibM_minus_2, ahol fibM_minus_1 és fibM_minus_2 a sorozatban a fibM előtt közvetlenül lévő két szám:

fibM = fibM_minus_1 + fibM_minus_2

Az értékeket 0,1 és 1, illetve a Fibonacci-sorozat első három számának inicializáljuk, hogy ne kapjunk indexhibát abban az esetben, ha a lys keresőtömbünk nagyon kevés elemet tartalmaz.

Ezután a Fibonacci-sorozat legkisebb olyan számát választjuk fibM értéknek, amely nagyobb vagy egyenlő a lys keresőtömbünk elemeinek számával, és az azt közvetlenül megelőző két Fibonacci-számot fibM_minus_1 és fibM_minus_2 értéknek. Amíg a tömbben vannak még elemek, és a fibM értéke nagyobb, mint egy, addig:

• Verseljük a val értékét a fibM_minus_2-ig terjedő tartományban lévő tömb értékével, és ha egyezik, akkor visszaadjuk az elem indexét.
• Ha az érték nagyobb, mint az éppen vizsgált elem, akkor a fibM, fibM_minus_1 és fibM_minus_2 értékeit a Fibonacci-sorozatban két lépéssel lefelé mozgatjuk, és az indexet az elem indexére állítjuk vissza.
• Ha az érték kisebb, mint az éppen vizsgált elem, akkor a fibM, fibM_minus_1 és fibM_minus_2 értékeit a Fibonacci-sorozatban egy lépéssel lefelé mozgatjuk.

Nézzük meg ennek az algoritmusnak a Python implementációját:

Ha a FibonacciSearch függvényt használjuk a számításhoz:

>>> print(FibonacciSearch(, 6))

Nézzük meg ennek a keresésnek a lépésenkénti folyamatát:

• Meghatározzuk a legkisebb Fibonacci-számot, amely nagyobb vagy egyenlő a lista hosszával, mint fibM; ebben az esetben a legkisebb Fibonacci-szám, amely megfelel a követelményeinknek, a 13.
• Az értékeket a következőképpen rendelnénk hozzá:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• A következő lépésben a lys elemet vizsgáljuk, ahol a 4 a -1+5 legkisebb értéke . Mivel az lys értéke 5, ami kisebb, mint a keresett érték, ezért a Fibonacci-számokat egy lépéssel lejjebb mozgatjuk a sorozatban, így az értékek:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Ezután a lys elemet vizsgáljuk, ahol 7 a 4+3 minimuma. Mivel az lys értéke 8, ami nagyobb, mint a keresett érték, ezért a Fibonacci-számokat két lépéssel lejjebb helyezzük a sorozatban.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Most megnézzük az lys elemet, ahol 5 a 4+1 minimuma . Az lys értéke 6, ami a keresett érték!

Az eredmény a várakozásoknak megfelelően:

5

A Fibonacci-keresés időbonyolultsága O(log n); ugyanaz, mint a bináris keresésé. Ez azt jelenti, hogy az algoritmus a legtöbb esetben gyorsabb, mint a lineáris keresés és az ugrásos keresés.

A Fibonacci-keresés akkor használható, ha nagyon sok elemet kell átkutatnunk, és csökkenteni akarjuk az osztásoperátorra támaszkodó algoritmus használatával járó gazdaságtalanságot.

A Fibonacci-keresés használatának további előnye, hogy olyan bemeneti tömböket is képes kezelni, amelyek túl nagyok ahhoz, hogy a CPU gyorsítótárában vagy a RAM-ban tároljuk őket, mivel az elemeket növekvő lépésméretben keresi át, és nem fix méretben.

Exponenciális keresés

Az exponenciális keresés egy másik keresési algoritmus, amely meglehetősen egyszerűen megvalósítható Pythonban, szemben az ugrásos kereséssel és a Fibonacci-kereséssel, amelyek mindketten kissé bonyolultak. Galoppáló keresés, duplázó keresés és Struzik keresés néven is ismert.

Az exponenciális keresés az értékek végső összehasonlításának elvégzéséhez a bináris kereséstől függ. Az algoritmus a következőképpen működik:

• Meghatározzuk azt a tartományt, ahol a keresett elem valószínűleg található
• A tartomány bináris keresését használjuk az elem pontos indexének megtalálására

Az exponenciális keresési algoritmus Python implementációja:

Ha a függvény segítségével megkeressük:

>>> print(ExponentialSearch(,3))

Az algoritmus a következőképpen működik:

• Vizsgáljuk, hogy a lista első eleme megegyezik-e a keresett értékkel – mivel lys 1, és mi 3-at keresünk, az indexet 1-re állítjuk, és továbblépünk.
• A lista összes elemén végigmegyünk, és amíg az index’th pozícióban lévő elem kisebb vagy egyenlő a keresett értékünkkel, addig exponenciálisan növeljük a index értékét kettővel többszörösen:
  • index = 1, lys 2, ami kisebb, mint 3, ezért az indexet megszorozzuk 2-vel és 2-re állítjuk.
  • index = 2, lys3, ami egyenlő 3-mal, ezért az indexet megszorozzuk 2-vel és 4-re állítjuk.
  • index = 4, lys 5, ami nagyobb, mint 3; a ciklus ezen a ponton megszakad.
• Ezután bináris keresést végez a lista felszeletelésével; arr. Pythonban ez azt jelenti, hogy a részlista minden elemet tartalmazni fog a 4. elemig, tehát valójában a:

>>> BinarySearch(, 3)

hívjuk, ami visszaadná:

2

Ami a keresett elem indexe mind az eredeti listában, mind a felszeletelt listában, amit átadunk a bináris kereső algoritmusnak.

Az exponenciális keresés O(log i) idő alatt fut, ahol i a keresett elem indexe. A legrosszabb esetben az időbonyolultság O(log n), ha az utolsó elem a keresett elem (n a tömb hossza).

Az exponenciális keresés jobban működik, mint a bináris keresés, ha a keresett elem közelebb van a tömb elejéhez. A gyakorlatban azért használjuk az exponenciális keresést, mert ez az egyik leghatékonyabb keresési algoritmus korlátlan vagy végtelen tömbök esetén.

Interpolációs keresés

A bináris kereséshez hasonlóan az interpolációs keresés egy másik oszd meg és uralkodj algoritmus. A bináris kereséssel ellentétben nem mindig a közepén kezdi a keresést. Az interpolációs keresés a keresett elem valószínű pozícióját a következő képlet segítségével számítja ki:

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

Ahol a változók:

• lys – a bemeneti tömbünk
• val – a keresett elem
• index – a keresett elem valószínű indexe. Ezt úgy számoljuk ki, hogy magasabb értéket kap, ha val értékben közelebb van a tömb végén lévő elemhez (lys), és alacsonyabbat, ha val értékben közelebb van a tömb elején lévő elemhez (lys)
• low – a tömb kezdőindexe
• high – a tömb utolsó indexe

Az algoritmus a index értékének kiszámításával keres:

• Ha találunk egyezést (amikor lys == val), az indexet visszaadjuk
• Ha a val értéke kisebb, mint lys, az index értékét újra kiszámítjuk a bal oldali altömbre vonatkozó képlet segítségével
• Ha a val értéke nagyobb, mint lys, az index értékét újra kiszámítjuk a jobb oldali altömb képletével

Lépjünk tovább, és implementáljuk az interpolációs keresést Python segítségével:

Ha a függvény segítségével kiszámítjuk:

>>> print(InterpolationSearch(, 6))

A kezdeti értékeink a következők lennének:

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

Mivel lys 6, ami a keresett érték, megállítjuk a végrehajtást és visszaadjuk az eredményt:

5

Ha nagyszámú elemünk van, és az indexünket nem tudjuk egy iterációban kiszámítani, akkor a képletünkben a high és low értékek beállítása után folyamatosan újraszámoljuk az index értékeit.

Az interpolációs keresés időbonyolultsága O(log log n), ha az értékek egyenletesen vannak elosztva. Ha az értékek nem egyenletesen elosztottak, akkor a legrosszabb esetben az időbonyolultság O(n), ami megegyezik a lineáris kereséssel.

Az interpolációs keresés legjobban egyenletesen elosztott, rendezett tömbökön működik. Míg a bináris keresés középen kezdődik és mindig kettéoszt, addig az interpolációs keresés kiszámítja az elem valószínű pozícióját és ellenőrzi az indexet, így nagyobb valószínűséggel találja meg az elemet kisebb számú iterációban.

Miért használjuk a Pythont keresésre?

A Python rendkívül olvasható és hatékony a régebbi programozási nyelvekhez, mint a Java, Fortran, C, C++ stb. képest. A Python használatának egyik legfontosabb előnye a keresési algoritmusok megvalósításához az, hogy nem kell aggódnunk a casting vagy az explicit tipizálás miatt.

A Pythonban a legtöbb keresési algoritmus, amit tárgyaltunk, ugyanolyan jól működik, ha egy karakterláncot keresünk. Ne feledjük, hogy az olyan algoritmusok esetében, amelyek a keresőelemet numerikus számításokhoz használják, például az interpolációs keresőalgoritmusnál, változtatnunk kell a kódon.

A Python akkor is jó kiindulópont, ha különböző keresőalgoritmusok teljesítményét szeretnénk összehasonlítani az adathalmazunkhoz; a prototípus készítése Pythonban egyszerűbb és gyorsabb, mert kevesebb kódsorral többet tudunk elérni.

A megvalósított keresőalgoritmusaink teljesítményének összehasonlításához egy adathalmazzal szemben használhatjuk a Pythonban található time könyvtárat:

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

Következtetés

Egy gyűjteményen belüli elem keresésének számos lehetséges módja van. Ebben a cikkben megpróbáltunk néhány keresési algoritmust és azok Pythonban való megvalósítását tárgyalni.

Az, hogy melyik algoritmust használjuk, a keresendő adatokon alapul; a bemeneti tömbünkön, amelyet minden megvalósításunkban lys neveztünk el.

• Ha egy rendezetlen tömbben szeretnénk keresni, vagy egy keresett változó első előfordulását szeretnénk megtalálni, akkor a legjobb megoldás a lineáris keresés.
• Ha egy rendezett tömbben szeretnénk keresni, akkor több lehetőség is van, amelyek közül a legegyszerűbb és leggyorsabb módszer a bináris keresés.
• Ha van egy rendezett tömb, amelyet az osztás operátor használata nélkül szeretnénk átkutatni, akkor használhatjuk az ugrásos keresést vagy a Fibonacci-keresést.
• Ha tudjuk, hogy a keresett elem valószínűleg közelebb van a tömb elejéhez, akkor használhatjuk az exponenciális keresést.
• Ha a rendezett tömböd is egyenletes eloszlású, akkor a leggyorsabb és leghatékonyabb keresési algoritmus az interpolációs keresés.

Ha nem vagy biztos benne, hogy melyik algoritmust használd egy rendezett tömb esetén, egyszerűen próbáld ki mindegyiket a Python időkönyvtárával együtt, és válaszd ki azt, amelyik a legjobban teljesít az adatállományoddal.