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
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vytvořte si vlastní webové stránky. Snadno, rychle a levně přes Saywebpage.com
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

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

Google       Google       10. 2. 2012       18 343×

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

Obrázek ke článku V přechodu na DVB-T2 tápou především senioři. Přeladit jim pomáhají vnoučata, zapojí se i stát

V přechodu na DVB-T2 tápou především senioři. Přeladit jim pomáhají vnoučata, zapojí se i stát

Už na konci měsíce může zůstat část Čechů bez televizního signálu. Vypínání stávající sítě začne již 27. listopadu v Praze a středních Čechách a do poloviny roku 2020 čeká přechod na nový standard pozemního digitálního televizního vysílání DVB-T2 celou republiku. K naladění nového televizního vysílání musí řada lidí nakoupit modernější zařízení, upravit antény nebo přejít na kabelové či internetové vysílání. 

Reklama
Reklama
Obrázek ke článku Zavádění Master Data Management v praxi

Zavádění Master Data Management v praxi

Předchozím článku jsme si vysvětlili, co jsou to Master Data, kdy je firma obvykle začíná řešit, v jakých krocích postupovat a jak nám může pomoci zvláštní nástroj pro evidenci Master dat. V tomto článku se podíváme na dvou příkladech, jak prakticky začít Master data řešit.

1. Nová Master Data, která potřebujeme někde spravovat
2. Zmapování existujících Master dat a určení jejich vlastníků

Obrázek ke článku 5 nesprávných důvodů, proč dělat vlastní mobilní aplikaci

5 nesprávných důvodů, proč dělat vlastní mobilní aplikaci

Myslíte si, že máte skvělý nápad na byznys apku a znáte všechno, co potřebujete? Možná vám vývoj software na míru rozmluví Vláďa Skoumal, z firmy studio SKOUMAL vyvijející mobilní aplikace 5.11. 2019 v 18:00 v Impact Hub Praha nebo tento jeho článek.


 

Obrázek ke článku Ericsson ConsumerLab Report: rozšířená realita je další úrovní gamingu

Ericsson ConsumerLab Report: rozšířená realita je další úrovní gamingu

Celkem 66 % uživatelů zajímá rozšířená realita v oblasti gamingu. Mezi nimi je i 35 % těch, kteří jinak hry nehrají.
Pro téměř 50 % respondentů by bylo zajímavé zapojení virtuální objektů do reálného světa. Objekty by zůstaly tam, kde je při hře „umístili“.
Až 43 % uživatelů láká využití rozšířené reality ve sportu

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