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

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

 
Hledat
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Pergoly a střechy Brno

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

Google       Google       10. 2. 2012       19 555×

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ů.

Reklama
Reklama

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

Reklama
Reklama
Obrázek ke článku Konference: Moderní informační systémy podporují automatizaci

Konference: Moderní informační systémy podporují automatizaci

Současná situace v šíření onemocnění Covid-19 klade na řadu firem nové nároky a mnohé z nich jsou nyní více než kdy jindy závislé na nejmodernějších informačních technologiích. Proto i v oblasti podnikových informačních systémů vidíme rostoucí důraz na automatizaci nebo na důslednou integraci. Také o těchto trendech se bude mluvit na konferenci Firemní informační systémy, která se koná 24.9.2020 v pražském Kongresovém centru Vavruška na Karlově náměstí.

Obrázek ke článku Nebezpečí ukrytá v USB: z nuly na škvarek za pět sekund

Nebezpečí ukrytá v USB: z nuly na škvarek za pět sekund

Za cenu šesti dolarů lze celkem bez obtíží koupit nový, líbivě vyhlížející flash disk. Přidaná hodnota, které se vám spolu s ním dostane, už tak moc líbivá není. To, co se před pár sekundami tvářilo jako externí disk, se po připojení k počítači změní v důmyslné elektrické křeslo, které vaše zařízení v onen příslovečný škvarek promění za pár sekund. Cílovou skupinou pro koupi takových zařízení by mohli být záškodníci, kteří by tímto způsobem osnovali pomstu třeba vůči záletnému partnerovi. 

Obrázek ke článku Znalosti, dovednosti i prestižní titul MBA: Jde to i moderně a online

Znalosti, dovednosti i prestižní titul MBA: Jde to i moderně a online

Snad nikdy není špatná příležitost na investici do hodnotného vzdělání. Obzvlášť v případě, že absolvent dovede teoretické poznatky přetavit v praktické dovednosti, využitelné při řešení problémů i v komunikaci. Právě na to se specializuje studijní program MBA Řízení informačních technologií, vyučovaný na Business Institutu.

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032021 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý