|
|
Grafy a tabuľky |
| Vyhľadávanie v obojsmerne zreťazenom zozname podľa aktuálnej pozície
|
Priemerné počty porovnaní vybraných implementácií |
//sekvencne vyhladavanie zadanej hodnoty "hladany"
//v OZ zozname od zaznamu "aktualny" s podmienkou
//zoznam musi byt vzostupne usporiadany
//(na zaciatku zoznamu je zaznam s najmensou hodnotou)
//zoznam musi byt zretazeny dokola
//funkcia vracia ukazovatel na najdeny zaznam (v pripade neuspechu vyhladavania vracia 0
CZaznam_OZ* CZoznam_OZ::najdi_sekv2_zaznam_podm(int hladany, CZaznam_OZ* aktualny){
if (++p_a_porovnani_ && !aktualny) return 0;
if (++p_b_porovnani_ && hladany==aktualny->hodnota()) return aktualny;
CZaznam_OZ* prvy=aktualny;
if (++p_b_porovnani_ && hladany < aktualny->hodnota()) {
do {
aktualny=aktualny->predch();
++p_posunuti_;
} while (++p_b_porovnani_ && hladany < aktualny->hodnota() &&
++p_c_porovnani_ && aktualny!=prvy);
if (++p_b_porovnani_ && hladany==aktualny->hodnota()) return aktualny;
else return 0;
}
else {
do {
aktualny=aktualny->dalsi();
++p_posunuti_;
} while (++p_b_porovnani_ && hladany > aktualny->hodnota() &&
++p_c_porovnani_ && aktualny!=prvy);
if (++p_b_porovnani_ && hladany==aktualny->hodnota()) return aktualny;
else return 0;
}
} |
| Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie. |
| počet záznamov v zozname |
p_a_porovnani_ |
p_b_porovnani_ |
p_c_porovnani_ |
p_posunuti_ |
čas |
| 10 |
1,000 |
4,300 |
1,200 |
1,900 |
0,4653 |
| 100 |
1,000 |
38,52 |
34,52 |
35,52 |
2,913 |
| 1.000 |
1,000 |
331,3 |
327,3 |
328,3 |
26,96 |
| 10.000 |
1,000 |
3343,8 |
3339,8 |
3340,8 |
269,3 |
|
Z tabuľky môžeme vyčítať, že priemerný počet cyklov pri tomto type vyhľadávania je približne n/3. Počet porovnaní je približne 2*n/3. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Závislosť dĺžky trvania tohto algoritmu od veľkosti zoznamu je lineárna. Podobné časy by vyšli aj pre zväčša neúspešné vyhľadávanie (tak ako tomu bolo pri sekvenčnom vyhľadávaní s podmienkou v poliach), pretože ak by algoritmus nenašiel hľadanú hodnotu na predpokladanom mieste, ďalej by už nehľadal a teda by mal veľmi podobný počet posunutí v zozname ako úspešné vyhľadávanie. |
 |
| |
10 |
100 |
1.000 |
10.000 |
| úspešné vyhľadávanie |
0,4653 |
2,913 |
26,96 |
269,3 |
|
| |
| |
Porovnanie algoritmu s predchádzajúcimi algoritmami |
Ako môžeme vidieť, ak začneme vyhľadávať od začiatku zoznamu, vyhľadávanie trvá v priemernom prípade dlhšie ako keď začneme od aktuálnej pozície. Z toho pohľadu by bolo azda najefektívnejšie vždy vyhľadávať od stredu zoznamu. Tento stred by však bolo nutné niekde uchovávať a pri vkladaní alebo vynímaní záznamov zo zoznamu ho aj meniť. Existujú zoznamy, ktoré si uchovávajú ukazovatele aj do stredu zoznamu a tiež ukazovatele na niektoré iné dôležité pozície, tými sa však nebudeme na týchto stránkach zaoberať. |
 |
| |
10 |
100 |
1.000 |
10.000 |
| úspešné vyhľadávanie od aktuálnej pozície |
0,4653 |
2,913 |
26,96 |
269,3 |
| vyhľadávanie od zažiatku zoznamu úspešné |
0,5414 |
4,230 |
40,52 |
406,5 |
| vyhľadávanie od zažiatku zoznamu neúspešne s p=0,9 |
0,5074 |
4,520 |
40,57 |
404,5 |
|
| |
| |
| Poznámka: Algoritmy boli testované na počítači s procesorom AMD Athlon(tm) XP 1700+ a s 256 MB operačnou pamäťou pod operačným systémom Windows XP. Všetky časy uvedené v tabuľke sú v mikrosekundách. |
