|
|
Grafy a tabuľky |
| Interpolačné vyhľadávanie
|
Priemerné počty porovnaní vybraných implementácií |
//interpolacne vyhladavanie zadaneho prvku "hladany"
//pole musi byt usporiadane vzostupne (na zaciatku pola je prvok s najmensou hodnotou)
//funkcia vracia index zadaneho prvku v poli (v pripade neuspechu vyhladavania vracia -1)
template < class T, int velkost_ >
int CPole < T, velkost_ > ::najdi_interpol_index(T hladany){
int lavy_o=0;
int pravy_o=velkost_-1;
while ( ++p_a_porovnani_ && pole_[lavy_o] <= hladany &&
++p_a_porovnani_ && hladany <= pole_[pravy_o]) {
++p_a_cyklov_;
float menovatel=(pole_[pravy_o]-pole_[lavy_o]);
if (++p_c_porovnani_ && menovatel==0) {
if (++p_b_porovnani_ && pole_[lavy_o]==hladany) return lavy_o;
else return -1;
}
int stred=lavy_o + (hladany-pole_[lavy_o]) * ((pravy_o-lavy_o) / menovatel);
if (++p_b_porovnani_ && pole_[stred]==hladany) return stred;
else if (++p_b_porovnani_ && pole_[stred] < hladany) lavy_o=stred+1;
else pravy_o=stred-1;
}
return -1;
} |
| Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie s p=1. |
| počet prvkov v poli |
p_a_porovnani_ |
p_b_porovnani_ |
p_c_porovnani_ |
p_a_cyklov_ |
čas |
| 10 |
2,000 |
1,000 |
1,000 |
1,000 |
0,0991 |
| 100 |
2,000 |
1,000 |
1,000 |
1,000 |
0,1064 |
| 1.000 |
2,000 |
1,000 |
1,000 |
1,000 |
0,1088 |
| 10.000 |
2,000 |
1,000 |
1,000 |
1,000 |
0,1115 |
| 100.000 |
2,000 |
1,000 |
1,000 |
1,000 |
0,1125 |
|
Pri tomto testovaní algoritmu sa vo vstupnom poli indexovanom od 0 po n-1 nachádzali čísla 0 až n-1. Algoritmus teda v takomto prípade vždy našiel hľadaný prvok na prvý pokus. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie s p < 1. |
| počet prvkov v poli |
p_a_porovnani_ |
p_b_porovnani_ |
p_c_porovnani_ |
p_a_cyklov_ |
čas |
| 10 |
3,000 |
1,700 |
1,200 |
1,200 |
0,1143 |
| 100 |
4,200 |
3,110 |
1,890 |
1,890 |
0,1781 |
| 1.000 |
6,567 |
5,459 |
3,053 |
3,053 |
0,2588 |
| 10.000 |
7,326 |
6,208 |
3,420 |
3,420 |
0,2828 |
| 100.000 |
8,367 |
7,128 |
3,720 |
3,720 |
0,3069 |
|
Pri tomto testovaní boli do poľa vložené náhodné čísla z rovnomerného rozdelenia z rozsahu 0 až n-1. Preto sa algoritmu väčšinou podarilo veľmi rýchlo priblížiť k miestu, kde by sa hľadaná hodnota mala skutočne nachádzať. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre neúspešné vyhľadávanie s p=0,9 s rovnomerným rozdelením prvkov v poli. |
| počet prvkov v poli |
p_a_porovnani_ |
p_b_porovnani_ |
p_c_porovnani_ |
p_a_cyklov_ |
čas |
| 10 |
4,000 |
2,600 |
1,400 |
1,400 |
0,1374 |
| 100 |
4,980 |
3,680 |
1,860 |
1,860 |
0,1806 |
| 1.000 |
7,058 |
5,770 |
2,933 |
2,933 |
0,2542 |
| 10.000 |
7,861 |
6,592 |
3,339 |
3,339 |
0,2838 |
| 100.000 |
9,092 |
7,767 |
3,899 |
3,899 |
0,3239 |
|
Pri tomto testovaní boli do poľa vložené náhodné čísla z rovnomerného rozdelenia z rozsahu 0 až 10*n-1. V tomto prípade sa algoritmu tiež darilo veľmi rýchlo (približne na 3 cykly) priblížiť sa k miestu, kde by sa hľadaná hodnota mala nachádzať. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre neúspešné vyhľadávanie s exponenciálnym rozdelením prvkov v poli. |
| počet prvkov v poli |
p_a_porovnani_ |
p_b_porovnani_ |
p_c_porovnani_ |
p_a_cyklov_ |
čas |
| 10 |
8,100 |
7,100 |
3,600 |
3,600 |
0,3006 |
| 100 |
24,02 |
23,02 |
11,52 |
11,52 |
0,8133 |
| 1.000 |
63,56 |
62,49 |
31,26 |
31,26 |
2,123 |
| 10.000 |
547,6 |
546,6 |
273,3 |
273,3 |
17,80 |
| 100.000 |
2698,6 |
2697,6 |
1348,8 |
1348,8 |
104,7 |
|
Pri tomto testovaní boli do poľa vložené náhodné čísla s exponenciálnym rozdelením z rozsahu 0 až 10*n. Algoritmu sa preto nedarilo rýchlo sa približovať k skutočnému miestu, kde by sa mal prvok nachádzať. So zväčšujúcim sa vstupným poľom sa aj čas vyhľadávania veľmi predlžuje. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Ako je z grafu vidno, efektivita a časová zložitosť tohto algoritmu silne závisí od rozdelenia prvkov v poli. Pri vždy úspešnom vyhľadávaní je výsledný čas trvania vlastne len vyrátaním pozície hľadaného prvku. Pri rovnomernom rozdelení si algoritmus počína približne rovnako efektívne aj pri úspešnom aj neúspešnom vyhľadávaní. Pri exponenciálnom rozdelení prvkov je už tak dosť časovo náročný výpočet novej aktuálnej pozície ešte aj príťažou a spomalením v hľadaní. Pre takéto polia nie je tento algoritmus vhodný.
Porovnanie s binárnym algoritmom môžeme nájsť na konci podkapitoly 1.2. |
 |
| |
10 |
100 |
1.000 |
10.000 |
100.000 |
| úspešné vyhľadávanie s p=1 |
0,0991 |
0,1065 |
0,1088 |
0,1115 |
0,1125 |
| úspešné vyhľadávanie s p < 1 |
0,1143 |
0,1781 |
0,2588 |
0,2828 |
0,3069 |
| neúspešné vyhľadávanie v poli s rovnomerným rozdelením s p=0,9 |
0,1374 |
0,1806 |
0,2542 |
0,2838 |
0,3239 |
| neúspešné vyhľadávanie v poli s exponenciálnym rozdelením |
0,3006 |
0,8133 |
2,123 |
17,80 |
104,7 |
|
| |
| |
| 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. |
