Vývojové diagramy – pole a binární vyhledávání – 20. díl
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Vývojové diagramy – pole a binární vyhledávání – 20. dílVývojové diagramy – pole a binární vyhledávání – 20. díl

 

Vývojové diagramy – pole a binární vyhledávání – 20. díl

Google       Google       10. 2. 2012       9 757×

Pole lze použít na ukládání velkého množství dat. Jednou z důležitých oblastí zpracování takovýchto dat je třídění a v tomto díle si ukážeme, co to vlastně třídění je, k čemu nám je dobré a proč se mu budeme věnovat několik dalších dílů.

O co vlastně jde? Minule jsme si vygenerovali tiket Sportky a na výstupu jsme dostali čísla tak, jak byla vygenerována, a nikoliv seřazená podle velikosti. Kdybychom je chtěli v takovém pořadí, tak si musíme pole setřídit. Příklad výstupu algoritmu z 19. dílu:

index [] 1 2 3 4 5 6
hodnota 10 7 45 13 34 2

A takto by vypadalo pole setříděné (vzestupně):

index [] 1 2 3 4 5 6
hodnota 2 7 10 13 34 45

Tříděním se hodnoty v jednotlivých šuplíčcích seřadí tak, že víme, v jakém jsou pořadí, tj. pokud setřídíme pole vzestupně, tak v šuplíčku s označením A je jistě číslo menší nebo rovné číslu v šuplíčku A + 1.

Poznámka: v úloze s tiketem se nám čísla opakovat nemohla, ale v jiných úlohách se hodnoty v poli opakovat mohou, a proto ta neostrá nerovnost menší nebo rovno (<=)).

Teď si asi řeknete: a k čemu je mi to dobré? Představte si, že máte nesetříděné pole, které obsahuje 100 000 čísel různých hodnot (hodnoty se mohou opakovat, ale nemusí - je to jen na vás). A teď mi zjistěte, jestli je v poli uloženo číslo 768. To je přece jednoduché, řeknete si, projdu celé pole a toto číslo najdu (nebo nenajdu).

Ano, tak se to samozřejmě řešit dá a také nic jiného nezbývá (metoda se nazývá lineární vyhledávání). Když budu mít štěstí, tak bude číslo hned první testované. Když budu mít smůlu, tak to bude až to úplně poslední, tj. při tom nejhorším scénáři musím projít celé pole a to trvá (pokud někomu 100 tisíc připadá málo, tak může slovo tisíc nahradit třeba slovem milion nebo miliard :)).

A jak nám tedy pomůže setřídění? Když si pole setřídím a začnu ho procházet, tak sice mohu třeba již v půlce říct, že tam takové číslo není, když poslední testovaný šuplíček obsahoval číslo větší, ale když to hledané číslo bude to největší v poli, tak ho stejně projdu celé, nebo ne?

Samozřejmě to lze řešit jinak, a to tzv. metodou půlení intervalu (binární vyhledávání). Řekněme, že máme to pole 100 000 hodnot a hledáme číslo 768. Vezmeme hodnotu ze šuplíčku uprostřed intervalu (index = 50 000), kde bude například hodnota 5689, takže víme, že všechny šuplíčky v poli za tímto (celá půlka pole) jsou jistě s hodnotou výše a již je nemusíme testovat. V tuto chvíli nám stačí otestovat pouze zbylých 50 000 (resp. 49 999) šuplíčků. Na ně samozřejmě můžeme použít stejnou metodu a vyřadit tak opět polovinu tohoto rozsahu. Na dvě porovnání jsme vyřadili 3/4 pole.

Složitost lineárního hledání je O(N), tj. maximálně počet prvků pole. Složitost binárního vyhledávání je O(1 + lg(N)) (kde lg je logaritmus při základu 2). Pro pole o délce 100 000 hodnot tedy potřebuje v prvním případě maximálně 100 000 porovnání. V druhém případě potřebuje maximálně 17 kroků k nalezení čísla, resp. k jeho případnému nenalezení. Efekt zrychlení je tedy více než markantní.

Pro ty, co něvěří :), je tu praktická ukázka výpisu - pole o délce 100 000 prvků a hledáme například číslo 768, které v poli není, takže je to ten nejhorší případ - až po posledním porovnání se dozvíme, že tam takové číslo není.

Ve výpisu jsou tučně vyznačené tři body, které ohraničují šuplíček, ve kterém by měla hledaná hodnota být. V šuplíčku s indexem 18862 je hodnota 780, takže naše hledané číslo musí být v šuplíčku s menším indexem (máme přeci setříděné pole). V šuplíčku 18860 je hodnota 760, takže hledané číslo musí být v šuplíčku s vyšším indexem. Z toho plyne, že jediným místem, kde by námi hledané číslo mohlo být, je šuplíček s indexem 18861 a tam takové číslo není, takže pole hledané číslo neobsahuje.

Samozřejmě platí, že máme-li pole a chceme-li pouze jednou najít nějaké číslo, tak je skoro jedno, jestli se provede setřídění nebo ne a podle toho se použije vyhledávání. Je potřeba si ovšem uvědomit, že v programech bývá nejčastější operace právě hledání, takže setřídění pole a výběr správného algoritmu vyhledávání se ve výsledné rychlosti programu projeví.

Abychom si v tomto díle udělali alespoň jeden vývojový diagram, tak si vyřešíme binární vyhledávání. Existují dva způsoby řešení: iteračně (cyklem) a rekurzivně. Ukážeme si obě s tím, že základní program bude jeden - volání funkce Najdi mimo jiné s parametrem, který bude obsahovat hodnotu prvku, který hledáme. Vracet bude boolean hodnotu, tj. true, pokud prvek v poli je, a v opačném případě bude vracet false.

V obou případech předáváme do podprogramu čtyři parametry:

  • P - pole
  • S - počáteční (startovací) index
  • K - poslední (koncový) index
  • C - hledané číslo

Obě řešení jsou si velice podobná a rekurzivní zápis není o nic jednodušší než nerekurzivní. V rekurzivním máme funkci, které předáváme pole, počáteční a koncový index, mezi kterými hledáme. Tento rozsah postupně rozdělíme a dále rekurzivně testujeme pouze polovinu původního rozsahu, pokud již není číslo nalezené. Rekurze je ukončená ve chvíli, kdy číslo nalezneme nebo kdy již není možné dále rozsah dělit (počáteční a koncový index jsou shodné).

Nerekurzivní (iterativní) řešení funguje stejně, jenom si musíme udržovat aktuální počátek a konec prohledávaného rozsahu. Procházíme hodnoty pole v cyklu s podmínkou na začátku, která kontroluje, jestli je ještě co testovat (jestli testovaný index není stejný jako počáteční a koncový - rozsah obsahuje už pouze jeden šuplíček). Na počátku si index inicializujeme na -1, takže při prvním průchodu je podmínka určitě splněná. Dále to funguje stejně - kontroluje index v polovině rozsahu a pokud to není námi hledané číslo, tak podle porovnání (větší / menší) zmenšíme rozsah o polovinu zleva nebo zprava.

Oba vývojové diagramy vidíte na obrázcích. V příštím díle se ukážeme první tři metody třídění pole.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

2 názory  —  2 nové  
Hlasování bylo ukončeno    
8 hlasů
Google
Autor se věnuje programování za peníze :)

Nové články

Obrázek ke článku Nová česká vzdělávací služba Hacker Academy nabízí kurzy hackingu

Nová česká vzdělávací služba Hacker Academy nabízí kurzy hackingu

Kdo z Vás někdy neměl chuť proniknout do tajuplného světa hackerů a prozkoumávat neznámá zákoutí kyberprostoru? Po zhlédnutí filmu s hackerskou tématikou se toto stalo snem nejednoho teenagera. Cesta vedoucí k prvním úspěchům je ovšem velice dlouhá a složitá a jen málokdo má dostatek trpělivosti aby vydržel a do tajemného světa hackerů nakonec skutečně proniknul.

Obrázek ke článku Jak v Nette nastylovat formulář pomocí Latte maker

Jak v Nette nastylovat formulář pomocí Latte maker

Nette Framework formuláře mají pro Latte šablony definovaná vlastní makra, díky nimž je vykreslování formulářových prvků velmi jednoduché a přímočaré. To ale jen do doby, než chcete např. všem tlačítkům specifikovat vlastní html třídy (např. pro stylování pomocí Bootstrap). Jak na to, si ukážeme v dnešním článku.

Obrázek ke článku Webhosting u Active 24 – levný i multi

Webhosting u Active 24 – levný i multi

Jaká je nabídka webhostingu u ACTIVE 24 v roce 2014? Přední český webhoster nabízí 2 cenově dostupné varianty pro webhosting 1 webu nebo dvojici multihostingových balíčků, kam lze umístit více webových prezentací či aplikací.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032014 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý