|
|
Grafy a tabuľky |
| Vyhľadávanie algoritmom Brute force
|
Priemerné počty porovnaní vybraných implementácií |
//obycajne sekvencne vyhladavanie zadaneho vzoru "vzor" s poctom znakov "dlzka"
//funkcia vracia index prveho znaku najdeneho vzoru v retazci
//(v pripade neuspechu vyhladavania vracia -1)
int CRetazec::najdi_sekv(char* vzor, int dlzka){
for (int j=0; ++p_a_porovnani_ && j < velkost()-dlzka+1; j++){
for (int i=0; ++p_a_porovnani_ && i < dlzka; i++) {
if(++p_b_porovnani_ && retazec_[j+i] != vzor[i]) break;
}
if (++p_b_porovnani_ && i == dlzka) {
return j;
}
}
return -1;
} |
| Počet porovnaní, cyklov a času trvania algoritmu pre veľkosť abecedy=3 znaky, veľkosť vzoru=3 znaky. |
| počet znakov v prehľadávanom reťazci |
p_a_porovnani_ |
p_b_porovnani_ |
čas |
| 10 |
20,00 |
19,00 |
0,2020 |
| 100 |
242,0 |
238,0 |
2,450 |
| 1.000 |
2474,0 |
2435,0 |
25,27 |
| 10.000 |
24708,0 |
24352,0 |
249,4 |
| 100.000 |
247619,0 |
244005,0 |
2520,0 |
|
Z nameraných hodnôt môžeme vidieť, že súčet porovnaní je približne rovný 5-násobku dĺžky prehľadávaného reťazca. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre veľkosť abecedy=24 znakov, veľkosť vzoru=3 znaky. |
| počet znakov v prehľadávanom reťazci |
p_a_porovnani_ |
p_b_porovnani_ |
čas |
| 10 |
18,00 |
17,00 |
0,1514 |
| 100 |
203,0 |
202,0 |
1,191 |
| 1.000 |
2039,0 |
2038,0 |
11,13 |
| 10.000 |
20416,0 |
20414,0 |
110,3 |
| 100.000 |
204281,0 |
204273,0 |
1109,0 |
|
Z nameraných hodnôt môžeme vidieť, že súčet porovnaní je približne rovný 4-násobku dĺžky prehľadávaného reťazca. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre veľkosť abecedy=3 znaky, veľkosť vzoru=9 znakov. |
| počet znakov v prehľadávanom reťazci |
p_a_porovnani_ |
p_b_porovnani_ |
čas |
| 10 |
6,000 |
5,000 |
0,0881 |
| 100 |
229,0 |
228,0 |
2,303 |
| 1.000 |
2460,0 |
2458,0 |
24,67 |
| 10.000 |
24924,0 |
24922,0 |
249,9 |
| 100.000 |
249339,0 |
249332,0 |
2493,0 |
|
Z nameraných hodnôt môžeme vidieť, že súčet porovnaní je približne rovný 5-násobku dĺžky prehľadávaného reťazca. |
| |
| Počet porovnaní, cyklov a času trvania algoritmu pre veľkosť abecedy=24 znakov, veľkosť vzoru=9 znakov. |
| počet znakov v prehľadávanom reťazci |
p_a_porovnani_ |
p_b_porovnani_ |
čas |
| 10 |
6,000 |
5,000 |
0,0883 |
| 100 |
192,0 |
191,0 |
1,164 |
| 1.000 |
2028,0 |
2027,0 |
11,01 |
| 10.000 |
20409,0 |
20408,0 |
110,8 |
| 100.000 |
204284,0 |
204283,0 |
1111,5 |
|
Z nameraných hodnôt môžeme vidieť, že súčet porovnaní je približne rovný 4-násobku dĺžky prehľadávaného reťazca. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Dĺžka času prehľadávania reťazca závisí podľa nameraných hodnôt najmä od veľkosti abecedy. Keďže pre malé abecedy je vysoká pravdepodobnosť zhody znakov (0. znaku vzoru a aktuálneho znaku v reťazci), algoritmus často vykonáva porovnanie aj s 1. a nasledujúcimi znakmi vzoru a preto je časovo náročnejší. Ak je abeceda veľká, prichádza väčšinou len k neúspešnému porovnaniu 0. znaku vzoru s reťazcom a následne posunutiu vzoru na ďalšiu možnú vyhovujúcu pozíciu. Závislosť dĺžky času vykonávania od veľkosti prehľadávaného reťazca je lineárna. |
 |
| |
10 |
100 |
1.000 |
10.000 |
100.000 |
| veľkosť abecedy=3 znaky, dĺžka vzoru=3 znaky |
0,2020 |
2,450 |
25,27 |
249,5 |
2520,0 |
| veľkosť abecedy=24 znakov, dĺžka vzoru=3 znaky |
0,1514 |
1,191 |
11,13 |
110,3 |
1109,0 |
| veľkosť abecedy=3 znaky, dĺžka vzoru=9 znakov |
0,0881 |
2,303 |
24,67 |
250,0 |
2493,0 |
| veľkosť abecedy=24 znakov, dĺžka vzoru=9 znakov |
0,0883 |
1,164 |
11,01 |
110,9 |
1111,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. |
