V minulom dieli (príklad 6.3) sme ukázali ako jednoducho sa dá vyhľadávať v zoznamoch údajov ak použijeme triedu List<T> a použijeme metódu Find() . Stačilo si ešte zadefinovať vlastnú funkciu, ktorá slúžila ako vyhľadávacie kritérium.
Find() má nevýhodu v tom, že nedokáže nájsť index (pozíciu) ľubovoľného prvku. Ale iba prvky, ktoré vyhovujú určitému kritériu. T.j. nie je schopný nájsť napr. pozíciu čísla 3 v zozname čísiel, jedine že by sme si naprogramovali vyhľadávacie kritérium len pre hľadanie čísla 3, čo by bolo asi dosť nepraktické :-)) Alebo si môže spraviť jednoduchý cyklus, ktorý robí sekvenčné vyhľadávanie sami, viď príklad na konci.
POZNÁMKA : Označenie List s <T> používam preto, že to vyjadruje generickú triedu, ktorá je podporovaná len od verzie C# 2.0. T znamená ľubovoľný dátový typ. Tieto triedy sú v priestore mien System.Collections.Generic. V .Net Framework SDK sa môžete stretnúť s takýmto označením : List (of T)
Zároveň existujú aj triedy na zoznamy s rovnakými menami, ale nie sú založené na generickom princípe. Dajú sa do nich ukladať len dáta typu object a potom je potrebné pretypovanie pri spätnom vyberaní údajov.
>>Ako efektívne vyhľadávať v zozname?
Metóda (funkcia) triedy List<T> .Find() funguje sekvenčne. To znamená, že začne s porovnávaním od prvého prvku a postupne na všetky aplikuje porovnávacie kritérium, ktoré sme si naprogramovali. Predstavte si, že máme veľmi rozsiahli zoznam údajov a prvok, ktorý vyhovuje kritériu je úplne na konci. Sekvenčne od prvého prvku sa musí porovnať všetkých n prvokov, pričom jednoduchšie by bolo ale začať od konca.
Existuje algoritmus, ktorý nájde prvok rovnako rýchlo, či už sa nachádza na prvom mieste alebo na konci : Binárne vyhľadávanie.
>>Ako funguje binárne vyhľadávanie?
Možno, že tento algoritmus poznáte aj pod menom : Vyhľadávanie pomocou pólenia.
Základnou podmienkou je : Zoznam musí byť utriedený !!!!!
Nebudem tu rozpisovať detaily tohto algoritmu. Základnou myšlienkou je, že nájdeme stredný prvok zoznamu a porovnávame jeho hodnotu s hľadaným prvok. Ak má hľadaný prvok väčšiu hodnotu - znamená to, že sa určité nachádza v pravej polovici zoznamu (a aj opačne). Ešte raz upozorňujme, že zoznam musí byť utriedený.
Pozrite sa na tento jednoduchý príklad hľadania, či sa prvok nachádza v zozname :
Viete si určite vypočítať, koľko krokov by sme potrebovali pri sekvenčnom vyhľadávaní.
>>Ako teda pole utriedim?
Ako keby s touto otázkou počítali aj programátori triedy List<T> a priamo implementovali túto metódu do triedy List<T>. Takže stačí použiť metódu Sort(). Ak si pamätáte, stretli sme sa s ňou aj v príklade 6.4 v minulom dieli.
>>Ako je to s efektivitou takéhoto vyhľadávania ?
Efektivita tohto algoritmu sa ukáže pri väčšom počte prvkov. Hlavne pre podmienku usporiadaného zoznamu.
Metóda Sort() používa veľmi rýchli triediaci algoritmus, o čom hovorí aj jeho meno : QuickSort.
Nebudem ho tu rozpisovať, poobzerajte sa po Internete, určite niečo nájdete, alebo mi jednoducho verte, že je do dosť dobrý algoritmus :-)). Zatiaľ Vám prezradím, že čas potrebný na utriedenie závisí od funkcie
n . log(n). To ale nie je pravidlo, čas závisí aj od toho v akej miere je usporiadaný vstupný zoznam. V najhoršom prípade to môže byť závislé aj od funkcie n.n.
POZOR!! Ak použijete binárne vyhľadávanie na neutriedený zoznam, výsledok dostanete, ale bude najskôr nesprávny.
Nevýhodou binárneho vyhľadávania vyplýva z jeho podstavy. Vstupný zoznam sa utriedi a teda preusporiada.
>>Dosť už teórie, chcem príklad !
Odporúčam príklad stiahnuť a pohrať sa s rôznymi parametrami – napr. počet prvkov.
Príklad 7.1
static List<int> cisla = new List<int>(500000);
static List<int> naVyhladanie = new List<int>(20000);
TimeSpan diff1 = t_sekvencne_end - t_sekvencne_start;
TimeSpan diff2 = t_binarne_end - t_binarne_start;
Console.WriteLine("Casy :");
Console.WriteLine("Sekvence : {0}ms",diff1.Milliseconds);
Console.WriteLine("Binarne : {0}ms",diff2.Milliseconds);
private static void NaplnZoznam(List<int> zoznam,int poc,int max)
for(int i = 0; i< poc; i++
for(i = 0; i < naVyhladanie.Count; i++)
for(j = 0; j < cisla.Count; j++)
if (cisla[j] == naVyhladanie[i]) break;
for(int i = 0; i < naVyhladanie.Count; i++)
Príklad funguje tak, že vygeneruje náhodne 500 000 čísiel a naplní nim zoznam cisla.
Ďalej vygeneruje 20 000 čísiel, ktoré sa budú v predchádzajúcom zozname vyhľadávať.
Najprv sa použije sekvenčný spôsob, ktorý jednoducho keď číslo nájde prejde na ďalšie číslo na vyhľadanie bez toho, aby nejako tento výsledok zúžitkoval.
Potom sa použije binárne vyhľadávanie, kde sa najprv pole utriedi.
Časové výsledky ako vidíte na obrázku som dosiahol na PC 1.3GHz Atlhon, 512MB Ram.
Možno, že som nepoužil dobré štatistické metódy, ale určitú výpovednú hodnotu tento náš pokus určite má :-)
Michal Čižmár
