|
|
Grafy a tabuľky |
| Vyhľadávanie pri metóde Coalesced chaining
|
Priemerné počty porovnaní vybraných implementácií |
//najdenie zadanej hodnoty "hodnota" v rozptylovej tabulke
//so zretazenym rozptylovanim metodou coalesced chaining
//funkcia vracia index polozky v ktorej bola hodnota najdena (v pripade neuspechu vracia -1)
int CTabulka_ZR_CCH::najdi(int hodnota) {
int riadok = funkcia_1(hodnota);
if (++p_pokusov_ && tabulka_[riadok].prazdna()) return -1;
else if (++p_pokusov_ && tabulka_[riadok].hodnota()==hodnota)
{++p_najdeni_; return riadok;}
while (++p_posunuti_ && (riadok = tabulka_[riadok].nasl_p())!=-1) {
if (++p_pokusov_ && tabulka_[riadok].hodnota()==hodnota)
{++p_najdeni_; return riadok;}
}
return -1;
} |
| 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 |
16,00 |
6,000 |
10,00 |
1,600 |
0,2433 |
| 101 |
170,0 |
65,00 |
95,00 |
1,684 |
0,2567 |
| 997 |
1621,0 |
674,0 |
947,0 |
1,712 |
0,2769 |
| 10.007 |
14708,0 |
5202,0 |
9506,0 |
1,547 |
0,2949 |
|
Pomer počtu pokusov k počtu vyhľadávaní sa pohybuje v rozmedzí 1,54 až 1,72. Odchýlky sú opäť spôsobené len náhodnosťou generovania čísiel. |
| |
| 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 |
11,00 |
3,000 |
8,000 |
1,375 |
0,2190 |
| 101 |
115,0 |
40,00 |
75,00 |
1,533 |
0,2423 |
| 997 |
1111,0 |
364,0 |
747,0 |
1,487 |
0,2513 |
| 10.007 |
10343,0 |
2838,0 |
7505,0 |
1,378 |
0,2789 |
|
Pomer počtu pokusov k počtu vyhľadávaní sa pohybuje v rozmedzí 1,38 až 1,54. Odchýlky sú opäť spôsobené len náhodnosťou generovania čísiel. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Pri tomto druhu rozptyľových tabuliek by tiež nemal čas vyhľadávania závisieť od veľkosti tabuliek, ale keďže použitá rozptyľová funkcia a ani generátor náhodných čísiel nebol ideálny, mohlo dochádzať v niektorých častiach tabuľky k vysokej miere zaplnenosti a mohli tak vznikať dlhé reťaze vkladaných hodnôt. Čas vyhľadávania opäť závisí najmä od zaplnenosti tabuľky |
 |
| |
11 |
101 |
997 |
10007 |
| zaplnenie tabuľky je 95% |
0,2433 |
0,2567 |
0,2769 |
0,2949 |
| zaplnenie tabuľky je 75% |
0,2190 |
0,2423 |
0,2513 |
0,2789 |
|
| |
| |
| 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. |
