Úvod

Vyhledávání dat uložených v různých datových strukturách je důležitou součástí téměř každé aplikace.

Při vyhledávání je k dispozici mnoho různých algoritmů a každý z nich má jinou implementaci a spoléhá na jiné datové struktury.

Schopnost zvolit konkrétní algoritmus pro danou úlohu je pro vývojáře klíčovou dovedností a může znamenat rozdíl mezi rychlou, spolehlivou a stabilní aplikací a aplikací, která se rozpadne na základě jednoduchého požadavku.

• Členění operátorů
• Lineární vyhledávání
• Binární vyhledávání
• Skokové vyhledávání
• Fibonacciho vyhledávání
• Exponenciální vyhledávání
• Interpolační vyhledávání

.

Členění operátorů

Algoritmy se v průběhu času vyvíjejí a optimalizují v důsledku neustálého vývoje a potřeby nalézt co nejefektivnější řešení základních problémů v různých oblastech.

Jedním z nejčastějších problémů v oblasti informatiky je prohledávání kolekce a určování, zda se daný objekt v kolekci nachází, či nikoli.

Téměř každý programovací jazyk má vlastní implementaci základního vyhledávacího algoritmu, obvykle jako funkci, která vrací Booleanhodnotu True nebo False, když je v dané kolekci předmětů nalezen.

V jazyce Python je nejjednodušším způsobem vyhledávání objektů použití operátorů členství – jmenují se tak proto, že nám umožňují určit, zda je daný objekt členem kolekce.

Tyto operátory lze v jazyce Python použít s libovolnou iterovatelnou datovou strukturou, včetně řetězců, seznamů a tuplů.

• in – Vrací True, pokud je daný prvek součástí struktury.
• not in – Vrátí True, pokud daný prvek není součástí struktury.

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

Operátory členství postačují, pokud potřebujeme pouze zjistit, zda v daném řetězci existuje podřetězec, nebo určit, zda se dva řetězce, seznamy nebo tuply protínají z hlediska objektů, které obsahují.

Ve většině případů potřebujeme kromě určení, zda položka v posloupnosti existuje, také její pozici; operátory členství tento požadavek nesplňují.

Existuje mnoho vyhledávacích algoritmů, které nejsou závislé na vestavěných operátorech a lze je použít k rychlejšímu a/nebo efektivnějšímu vyhledávání hodnot. Kromě toho mohou poskytnout více informací, například pozici prvku v kolekci, než jen možnost určit jeho existenci.

Lineární vyhledávání

Lineární vyhledávání je jedním z nejjednodušších vyhledávacích algoritmů a je nejsnazší na pochopení. Můžeme si ho představit jako rozšířenou verzi vlastní implementace operátoru in jazyka Python.

Algoritmus spočívá v iteraci nad polem a vrácení indexu prvního výskytu položky, jakmile je nalezena:

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

Použijeme-li tedy funkci pro výpočet:

>>> print(LinearSearch(, 2))

Po provedení kódu nás přivítá:

1

Toto je index prvního výskytu hledané položky – mějme na paměti, že indexy v jazyce Python mají hodnotu 0.

Časová složitost lineárního vyhledávání je O(n), což znamená, že čas potřebný k provedení roste s počtem položek v našem vstupním seznamu lys.

Lineární vyhledávání se v praxi často nepoužívá, protože stejné efektivity lze dosáhnout použitím vestavěných metod nebo existujících operátorů a není tak rychlé a efektivní jako jiné vyhledávací algoritmy.

Lineární vyhledávání se hodí v případech, kdy potřebujeme najít první výskyt položky v netříděné kolekci, protože na rozdíl od většiny ostatních vyhledávacích algoritmů nevyžaduje, aby byla kolekce před zahájením vyhledávání roztříděna.

Binární vyhledávání

Binární vyhledávání se řídí metodikou rozděl a panuj. Je rychlejší než lineární vyhledávání, ale vyžaduje, aby bylo pole před provedením algoritmu setříděno.

Předpokládáme-li, že hledáme hodnotu val v setříděném poli, algoritmus porovná val s hodnotou prostředního prvku pole, který nazveme mid.

• Je-li mid hledaným prvkem (nejlepší případ), vrátíme jeho index.
• Pokud ne, určíme, na které straně mid se val s větší pravděpodobností nachází, podle toho, zda je val menší nebo větší než mid, a druhou stranu pole zahodíme.
• Poté postupujeme rekurzivně nebo iterativně stejně, přičemž v každé iteraci algoritmu vybereme novou hodnotu pro mid, porovnáme ji s val a polovinu možných shod vyřadíme.

Algoritmus binárního vyhledávání lze zapsat rekurzivně nebo iterativně. Rekurze je v jazyce Python obecně pomalejší, protože vyžaduje alokaci nových zásobníkových rámců.

Protože dobrý vyhledávací algoritmus by měl být co nejrychlejší a nejpřesnější, uvažujme iterativní implementaci binárního vyhledávání:

Použijeme-li funkci pro výpočet:

>>> BinarySearch(, 20)

Dostaneme výsledek:

1

Který je indexem hledané hodnoty.

Akce, kterou algoritmus v každé iteraci provede jako další, je jedna z několika možností:

• Vrácení indexu aktuálního prvku
• Prohledání levé poloviny pole
• Prohledání pravé poloviny pole

V každé iteraci můžeme vybrat pouze jednu možnost a náš fond možných shod se v každé iteraci vydělí dvěma. Díky tomu je časová složitost binárního prohledávání O(log n).

Jednou z nevýhod binárního vyhledávání je, že pokud se v poli vyskytuje více prvků, nevrací index prvního prvku, ale index prvku nejblíže středu:

>>> print(BinarySearch(, 4))

Při spuštění této části kódu bude výsledkem index prostředního prvku:

1

Pro srovnání, při lineárním prohledávání stejného pole by se vrátil:

0

Což je index prvního prvku. Nelze však kategoricky říci, že binární vyhledávání nefunguje, pokud pole obsahuje stejný prvek dvakrát – může fungovat stejně jako lineární vyhledávání a v některých případech vrátit první výskyt prvku.

Pokud bychom například provedli binární vyhledávání na poli a hledali 4, dostali bychom jako výsledek 3.

Binární vyhledávání se v praxi používá poměrně často, protože je ve srovnání s lineárním vyhledáváním efektivní a rychlé. Má však některé nedostatky, například závislost na operátoru //. Existuje mnoho dalších vyhledávacích algoritmů typu “rozděl a panuj”, které jsou odvozeny od binárního vyhledávání, prozkoumejme jich několik příště.

Skákací vyhledávání

Skákací vyhledávání je podobné binárnímu vyhledávání v tom, že pracuje se setříděným polem a k jeho prohledávání používá podobný přístup “rozděl a panuj”.

Můžeme jej klasifikovat jako vylepšení algoritmu lineárního prohledávání, protože při hledání hodnoty závisí na lineárním prohledávání, které provádí vlastní porovnávání.

Při daném setříděném poli místo postupného prohledávání prvků pole prohledáváme skokově. Takže v našem vstupním seznamu lys, pokud máme velikost skoku skok, bude náš algoritmus posuzovat prvky v pořadí lys, lys, lys, lys, lys a tak dále.

Při každém skoku uložíme předchozí hledanou hodnotu a její index. Když najdeme množinu hodnot, kde lys<prvek<lys, provedeme lineární prohledávání s lys jako nejlevějším prvkem a lys jako nejpravějším prvkem v naší prohledávané množině:

Protože se jedná o složitý algoritmus, uvažujme postupný výpočet skokového prohledávání s tímto zadáním:

>>> print(JumpSearch(, 5))

• Skokové prohledávání by nejprve určilo velikost skoku výpočtem math.sqrt(len(lys)). Protože máme 9 prvků, velikost skoku by byla √9 = 3.
• Následuje výpočet hodnoty proměnné right, což je minimum délky pole minus 1, neboli hodnota left+jump, která by v našem případě byla 0+3= 3. Protože 3 je menší než 8, použijeme jako hodnotu proměnné right hodnotu 3.
• Nyní zkontrolujeme, zda se náš hledaný prvek, 5, nachází mezi lys a lys. Protože 5 není mezi 1 a 4, pokračujeme dále.
• Další výpočet provedeme znovu a zkontrolujeme, zda náš hledaný prvek je mezi lys a lys, kde 6 je 3+skok. Protože 5 je mezi 4 a 7, provedeme lineární prohledávání prvků mezi lys a lys a vrátíme index našeho prvku jako:

4

Časová složitost skokového prohledávání je O(√n), kde √n je velikost skoku a n je délka seznamu, což skokové prohledávání z hlediska efektivity řadí mezi lineární prohledávání a binární prohledávací algoritmy.

Nejdůležitější výhodou skokového prohledávání ve srovnání s binárním prohledáváním je, že se nespoléhá na operátor dělení (/).

Ve většině procesorů je použití operátoru dělení ve srovnání s ostatními základními aritmetickými operacemi (sčítání, odčítání a násobení) nákladné, protože implementace algoritmu dělení je iterativní.

Náklady samy o sobě jsou velmi malé, ale pokud je počet prvků, které je třeba prohledat, velmi velký a počet operací dělení, které musíme provést, se zvyšuje, náklady se mohou postupně sčítat. Proto je skokové prohledávání lepší než binární prohledávání při velkém počtu prvků v systému, kde záleží i na malém zvýšení rychlosti.

Chceme-li skokové prohledávání zrychlit, mohli bychom k prohledávání bloků použít binární prohledávání nebo jiné interní skokové prohledávání, místo abychom se spoléhali na mnohem pomalejší lineární prohledávání.

Fibonacciho prohledávání

Fibonacciho prohledávání je další algoritmus typu rozděl a panuj, který vykazuje podobnost s binárním prohledáváním i skokovým prohledáváním. Svůj název získal proto, že k výpočtu velikosti bloku nebo rozsahu hledání v každém kroku používá Fibonacciho čísla.

Fibonacciho čísla začínají nulou a postupují podle vzoru 0, 1, 1, 2, 3, 5, 8, 13, 21…, kde každý prvek je součtem dvou čísel, která mu bezprostředně předcházejí.

Algoritmus pracuje vždy se třemi Fibonacciho čísly. Nazvěme tato tři čísla fibM, fibM_minus_1 a fibM_minus_2, kde fibM_minus_1 a fibM_minus_2 jsou dvě čísla bezprostředně před fibM v posloupnosti:

fibM = fibM_minus_1 + fibM_minus_2

Incializujeme hodnoty 0,1 a 1 nebo první tři čísla Fibonacciho posloupnosti, abychom se vyhnuli chybě indexu v případě, že naše vyhledávací pole lys obsahuje velmi malý počet prvků.

Poté zvolíme nejmenší číslo Fibonacciho posloupnosti, které je větší nebo rovno počtu prvků v našem vyhledávacím poli lys, jako hodnotu fibM a dvě Fibonacciho čísla bezprostředně před ním jako hodnoty fibM_minus_1 a fibM_minus_2. Dokud v poli zbývají prvky a hodnota fibM je větší než jedna, provedeme:

• Porovnáme val s hodnotou bloku v rozsahu do fibM_minus_2 a vrátíme index prvku, pokud se shoduje.
• Je-li hodnota větší než prvek, na který se právě díváme, posuneme hodnoty fibM, fibM_minus_1 a fibM_minus_2 o dva stupně dolů ve Fibonacciho posloupnosti a vrátíme index na index prvku.
• Je-li hodnota menší než prvek, na který se právě díváme, posuneme hodnoty fibM, fibM_minus_1 a fibM_minus_2 o jeden stupeň dolů ve Fibonacciho posloupnosti.

Podívejme se na implementaci tohoto algoritmu v jazyce Python:

Použijeme-li k výpočtu funkci FibonacciSearch:

>>> print(FibonacciSearch(, 6))

Podívejme se na postup tohoto hledání krok za krokem:

• Určení nejmenšího Fibonacciho čísla většího nebo rovného délce seznamu jako fibM; v tomto případě je nejmenším Fibonacciho číslem splňujícím naše požadavky číslo 13.
• Hodnoty by byly přiřazeny takto:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Dále zkontrolujeme prvek lys, kde 4 je minimum -1+5 . Protože hodnota prvku lys je 5, což je menší než hodnota, kterou hledáme, posuneme Fibonacciho čísla v posloupnosti o jeden stupeň dolů, takže hodnoty:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Dále zkontrolujeme prvek lys, kde 7 je minimum 4+3 . Protože hodnota prvku lys je 8, což je větší než hodnota, kterou hledáme, posuneme Fibonacciho čísla v posloupnosti o dva stupně níže.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Nyní zkontrolujeme prvek lys, kde 5 je minimum 4+1 . Hodnota lys je 6, což je hodnota, kterou hledáme!

Výsledek je podle očekávání:

5

Časová složitost Fibonacciho hledání je O(log n); stejná jako binární hledání. To znamená, že algoritmus je ve většině případů rychlejší než lineární prohledávání i skokové prohledávání.

Fibonacciho prohledávání lze použít v případě, že máme k prohledání velmi velký počet prvků a chceme snížit neefektivitu spojenou s použitím algoritmu, který je závislý na operátoru dělení.

Další výhodou použití Fibonacciho hledání je, že se může přizpůsobit vstupním polím, která jsou příliš velká na to, aby se vešla do mezipaměti procesoru nebo do paměti RAM, protože prohledává prvky v rostoucích krocích, a ne v pevně dané velikosti.

Exponenciální hledání

Exponenciální hledání je další vyhledávací algoritmus, který lze v Pythonu implementovat poměrně jednoduše, ve srovnání se skokovým hledáním a Fibonacciho hledáním, které jsou oba poněkud složitější. Je známý také pod názvy galoping search, doubling search a Struzik search.

Exponenciální hledání závisí na binárním hledání, které provádí konečné porovnání hodnot. Algoritmus funguje tak, že:

• určíme rozsah, ve kterém se pravděpodobně nachází hledaný prvek
• použijeme binární vyhledávání pro tento rozsah, abychom našli přesný index prvku

Implementace exponenciálního vyhledávacího algoritmu v jazyce Python je následující:

Použijeme-li funkci k nalezení hodnoty:

>>> print(ExponentialSearch(,3))

Algoritmus funguje tak, že:

• Zkontrolujeme, zda první prvek v seznamu odpovídá hledané hodnotě – protože lys je 1 a my hledáme 3, nastavíme index na 1 a pokračujeme dál.
• Projdeme všechny prvky seznamu a dokud je prvek na pozici indexu menší nebo roven naší hodnotě, exponenciálně zvýšíme hodnotu index na násobky dvou:
  • index = 1, lysje 2, což je méně než 3, takže index je vynásoben 2 a nastaven na 2.
  • index = 2, lysje 3, což je rovno 3, takže index je vynásoben 2 a nastaven na 4.
  • index = 4, lysje 5, což je větší než 3; v tomto bodě se smyčka přeruší.
• Poté se provede binární vyhledávání rozřezáním seznamu; arr. V jazyce Python to znamená, že dílčí seznam bude obsahovat všechny prvky až do 4. prvku, takže vlastně voláme:

>>> BinarySearch(, 3)

což by vrátilo:

2

Což je index prvku, který hledáme jak v původním seznamu, tak v rozřezaném seznamu, který předáváme algoritmu binárního vyhledávání.

Exponenciální hledání probíhá v čase O(log i), kde i je index prvku, který hledáme. V nejhorším případě je časová složitost O(log n), když je posledním prvkem prvek, který hledáme (n je délka pole).

Exponenciální hledání pracuje lépe než binární hledání, když je prvek, který hledáme, blíže začátku pole. V praxi používáme exponenciální vyhledávání, protože je to jeden z nejefektivnějších vyhledávacích algoritmů pro neohraničená nebo nekonečná pole.

Interpolační vyhledávání

Interpolační vyhledávání je další algoritmus typu rozděl a panuj, podobný binárnímu vyhledávání. Na rozdíl od binárního prohledávání nezačíná prohledávání vždy uprostřed. Interpolační hledání počítá pravděpodobnou pozici hledaného prvku podle vzorce:

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

Kde jsou proměnné:

• lys – naše vstupní pole
• val – hledaný prvek
• index – pravděpodobný index hledaného prvku. Ten se vypočítá jako vyšší hodnota, pokud je val blíže hodnotě prvku na konci pole (lys), a nižší, pokud je val blíže hodnotě prvku na začátku pole (lys)
• low – počáteční index pole
• high – poslední index pole

Algoritmus hledá výpočtem hodnoty index:

• Je-li nalezena shoda (při lys == val), je vrácen index
• Je-li hodnota val menší než lys, je hodnota indexu přepočítána podle vzorce pro levé dílčí pole
• Je-li hodnota val větší než lys, hodnota indexu se přepočítá pomocí vzorce pro pravé dílčí pole

Pokračujme a implementujme interpolační vyhledávání pomocí jazyka Python:

Pokud použijeme funkci pro výpočet:

>>> print(InterpolationSearch(, 6))

Naše počáteční hodnoty budou:

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

Protože lys je 6, což je hodnota, kterou hledáme, zastavíme provádění a vrátíme výsledek:

5

Pokud máme velký počet prvků a náš index nelze vypočítat v jedné iteraci, pokračujeme v přepočítávání hodnot indexu po úpravě hodnot high a low v našem vzorci.

Časová složitost interpolačního hledání je O(log log n), pokud jsou hodnoty rovnoměrně rozloženy. Pokud hodnoty nejsou rovnoměrně rozděleny, je časová složitost v nejhorším případě O(n), tedy stejná jako u lineárního hledání.

Interpolační hledání funguje nejlépe na rovnoměrně rozdělených, setříděných polích. Zatímco binární vyhledávání začíná uprostřed a vždy se rozdělí na dvě části, interpolační vyhledávání počítá pravděpodobnou pozici prvku a kontroluje index, takže je pravděpodobnější, že prvek najde v menším počtu iterací.

Proč používat Python pro vyhledávání?

Python je vysoce čitelný a efektivní ve srovnání se staršími programovými jazyky, jako jsou Java, Fortran, C, C++ atd. Jednou z klíčových výhod použití jazyka Python pro implementaci vyhledávacích algoritmů je, že se nemusíte starat o odlévání nebo explicitní psaní.

V jazyce Python bude většina vyhledávacích algoritmů, které jsme probrali, fungovat stejně dobře, pokud budeme hledat řetězec. Mějte na paměti, že u algoritmů, které používají vyhledávací prvek pro numerické výpočty, jako je například vyhledávací algoritmus interpolace, musíme provést změny v kódu.

Python je také dobrým místem pro začátek, pokud chcete porovnat výkonnost různých vyhledávacích algoritmů pro vaši datovou sadu; sestavení prototypu v Pythonu je jednodušší a rychlejší, protože můžete udělat více s menším počtem řádků kódu.

Pro porovnání výkonnosti námi implementovaných vyhledávacích algoritmů s datovou sadou můžeme v Pythonu použít knihovnu času:

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

Závěr

Existuje mnoho možných způsobů, jak vyhledat prvek v kolekci. V tomto článku jsme se pokusili probrat několik vyhledávacích algoritmů a jejich implementace v jazyce Python.

Výběr algoritmu, který použijeme, závisí na datech, která máme prohledat; na vstupním poli, které jsme ve všech našich implementacích nazvali lys.

• Pokud chcete prohledat nesetříděné pole nebo najít první výskyt hledané proměnné, je nejlepší volbou lineární prohledávání.
• Pokud chcete prohledat setříděné pole, existuje mnoho možností, z nichž nejjednodušší a nejrychlejší metodou je binární prohledávání.
• Pokud máte seřazené pole, které chcete prohledat bez použití operátoru dělení, můžete použít skokové vyhledávání nebo Fibonacciho vyhledávání.
• Pokud víte, že hledaný prvek bude pravděpodobně blíže začátku pole, můžete použít exponenciální vyhledávání.
• Pokud je vaše setříděné pole také rovnoměrně rozložené, nejrychlejším a nejefektivnějším vyhledávacím algoritmem bude interpolační vyhledávání.

Pokud si nejste jisti, který algoritmus použít u setříděného pole, prostě vyzkoušejte každý z nich spolu s časovou knihovnou Pythonu a vyberte ten, který se s vaším souborem dat osvědčí nejlépe.