|
|
Grafy a tabuľky |
| Vyhľadávanie pri metóde Separate chaining
|
Priemerné počty porovnaní vybraných implementácií |
//najdenie zadanej hodnoty "hodnota" v rozptylovej tabulke
//so zretazenym rozptylovanim metodou separate chaining
//funkcia vracia ukazovatel na najdeny zaznam
CZaznam_JZ* CTabulka_ZR_SCH::najdi(int hodnota) {
int riadok = funkcia_1(hodnota);
if (tabulka_[riadok].nasl_z()==0) {
return 0;
}
else {
CZaznam_JZ* aktualny=tabulka_[riadok].nasl_z();
if (++p_pokusov_ && aktualny->hodnota()==hodnota)
{++p_najdeni_; return aktualny;}
while (++p_posunuti_ && aktualny->dalsi()!=0) {
aktualny=aktualny->dalsi();
if (++p_pokusov_ && aktualny->hodnota()==hodnota)
{++p_najdeni_; return aktualny;}
}
}
return 0;
} |
| Počet porovnaní, cyklov a času trvania algoritmu pre 95% zaplnenie tabuľky. |
| počet prvkov v tabuľke |
p_pokusov_ |
p_posunuti_ |
p_najdeni_ |
p_pok/p_naj |
čas |
| 11 |
13,00 |
3,000 |
10,00 |
1,300 |
0,2864 |
| 101 |
146,0 |
51,00 |
95,00 |
1,537 |
0,2946 |
| 997 |
1369,0 |
422,0 |
947,0 |
1,446 |
0,3036 |
| 10.007 |
12454,0 |
2948,0 |
9506,0 |
1,310 |
0,3149 |
|
Z tabuľky môžeme vidieť, že počet pokusov kolíše v pomere k počtu nájdení a drží sa približne v rovnakom pomere (1,3 až 1,54) k nemu pre všetky veľkosti tabuliek. Odchýlky sú spôsobené rozptylovou funkciou. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre 75% zaplnenie tabuľky. |
| počet prvkov v tabuľke |
p_pokusov_ |
p_posunuti_ |
p_najdeni_ |
p_pok/p_naj |
čas |
| 11 |
10,00 |
2,000 |
8,000 |
1,250 |
0,2629 |
| 101 |
104,0 |
29,00 |
75,00 |
1,387 |
0,2895 |
| 997 |
1023,0 |
276,0 |
747,0 |
1,37 |
0,2753 |
| 10.007 |
9376,0 |
1871,0 |
7505,0 |
1,2493 |
0,3095 |
|
Z tabuľky môžeme vidieť, že počet pokusov kolíše v pomere k počtu nájdení a drží sa približne v rovnakom pomere (1,24 až 1,39) k nemu pre všetky veľkosti tabuliek. Odchýlky sú spôsobené rozptylovou funkciou. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Z nameraných hodnôt vidíme že čas vyhľadávania závisí od veľkosti tabuľky len minimálne a nemal by závisieť vôbec. Pre niektoré riadky tabuľky však môžu vzniknúť pri väčšom vkladanom množstve hodnôt dlhšie zoznamy a preto môže prísť z tohoto dôvodu k predĺženiu vyhľadávania. V najväčšej miere závisí čas vyhľadávania od zaplnenosti tabuľky. |
 |
| |
11 |
101 |
997 |
10.007 |
| zaplnenie tabuľky je 95% |
0,2864 |
0,2946 |
0,3036 |
0,3149 |
| zaplnenie tabuľky je 75% |
0,2629 |
0,2895 |
0,2753 |
0,3095 |
|
| |
| |
| 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. |
