Vyhľadávanie (riešené príklady)

Z Kiwiki
Verzia z 23:04, 28. február 2010, ktorú vytvoril Juraj (diskusia | príspevky)
Skočit na navigaci Skočit na vyhledávání
Imbox draft.png
 Toto je projekt, na ktorom sa ešte stále pracuje!!

Aj keď sú v tomto dokumente použiteľné informácie, ešte nie je dokončený. Svoje návrhy môžete vyjadriť v diskusii o tejto stránke.

Algoritmy a programovanie - zbierka úloh

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie

Lineárny zoznam

Binárny strom

Numerické algoritmy

Vyhľadávanie v usporiadanom zozname

Úloha

V logovacom súbore webového servera sú údaje o prístupe na niektorú z poskytovaných web stránok. Záznam v logu vyzerá asi takto: 

127.0.0.1 - - [13/Mar/2009:12:55:30 +0100] "GET / HTTP/1.1" 200 4075

Jednotlivé časti takéhoto záznamu majú nasledujúci význam:

  1. IP adresa počítača z ktorého sa pristupovalo. Pozostáva zo 4 čísel oddelených bodkou.
  2. Oddelovací znak: "- -"
  3. Dátum a čas udalosti uzatvorený do hranatých zátvoriek
    1. Časti dátumu sú oddelené lomkou „/“,
      • deň je vyjadrený 2 číslicami (02, 12, ...)
      • Mesiac je vyjadrený 3 znakmi
      • Rok je vyjadresný 4 číslicami
    2. čas je oddelený dvojbodkou „:“
      • Hodina, minúta aj sekunda je vyjadrená 2 číslicami
  4. žiadaná stránka

Úlohou bude zistiť, či v určitú dobu nastala nejaká udalosť. Ak udalosť nastala, zaujíma nás v ktorom riadku súboru je o tom záznam.

Jeden riadok súboru má maximálne 500 znakov.

Analýza úlohy

Webový server ukladá záznamy do súboru postupne, pričom každý nový pridaný záznam má hodnotu času väčšiu ako záznam pred ním. Môžeme teda povedať že tento súbor je usporiadaný vzhľadom na čas udalosti. Keďže sú vstupné dáta usporiadané môžeme použiť algoritmus binárneho vyhľadávania (je možné použiť aj algoritmus lineárneho vyhľadávania, ale bolo by to neefektívne).

Prvou úlohou je spracovať vstupné údaje. Vstupné údaje sú uložené v súbore (predpokladajme súbor access.log). V súbore treba prečítať všetky riadky. Toto jednoducho implementujeme tak, že budeme zo súboru čítať až potiaľ, pokiaľ neprečítame všetky riadky.

Predpokladajme, že v súbore nie je viac ako 1000 riadkov.

Návrh vhodnej dátovej štruktúry

Súbor budeme čítať po riadkoch, ale pri ukladaní načítaných údajov sa budeme snažiť čo najviac minimalizovať pamäťové nároky. Podľa zadania úlohy si nemusíme pamätať stránku ktorá je v danom riadku, zaujíma nás len čas a dátum prístupu. Vytvorme si teda dátovú štruktúru reprezentujúce tieto údaje: 

struct SCas{
   int den;
   char mesiac[4];
   int rok,hod,min,sek;
};

Všetky položky sú celé čísla, okrem mesiaca, pretože ten je v logovacom súbore vyjadrený ako 3-znaková skratka mesiaca. Keďže prvá časť log záznamu má premenlivú dĺžku (rôzna IP adresa), nemôžeme si jednoducho vypočítať index prvého znaku v dátume. Vždy ale vieme, že dátum začína za znakom ‘[’. Stačí teda zisťiť, kde sa nachádza znak ‘[’a potom už môžeme jednoducho zistiť dátum a čas udalosti. Pre zistenie pozície znaku ‘[’ použijeme funkciu strchr. Funkcia vráti smerník na prvý výskyt znaku z reťazci.

Získanie dátumu a času z riadku súboru

Zápisom 

char data[]="127.0.0.1 - - [13/Mar/2009:12:55:30 +0100] \"GET / HTTP/1.1\" 200 4075";
data=strchr(data,'[');

získame reťazec ktorý začína znakom ‘[’. Potom už vieme rozlíšiť ďalšie znaky. Keďže dátum má pevnú štruktúru, platí nasledovné :

reťazec data
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...
znak [ 0 5 / M a r / 2 0 0 9 : 1 2 : 5 5 : 3 0 ...

Vieme teda že platí:

  • deň získame z číslic na prvej a druhej pozícii poľa data: data[1]*10+data[2]
    • Keďže ale pole data je znakové pole, všetky znaky musíme previať na číselné hodnoty. Chcem teda previesť znak '5' na hodnotu 5. Tento prevod je jednoduché odpočítanie znaku '0'.
  • Mesiac získame spojením 4-tého až 6-teho znaku.
  • Rok, hodinu, minútu a sekundu získame podobne ako deň.

V nasledujúcom zdrojovom kóde je vytvorená funkcia, ktorej parametrom je načítaný riadok z log súboru a funkcia vráti dátum a čas (štruktúra SCas) z tohoto záznamu: 

 1 SCas dajCas(char *data)
 2 {
 3   SCas cas;
 4   data=strchr(data,'[');
 5   //retazec data vyzera teraz nasledovne:
 6   //[13/Mar/2009:12:55:30 +0100] "GET / HTTP/1.1" 200 4075  
 7 
 8   // udaje o dni su na indexe 1 a 2
 9   cas.den=(data[1]-'0')*10+(data[2]-'0');
10   
11   //mesiac sa skladá z 3 znakov (index 4 az 6) a z ukoncujuceho znaku
12   cas.mesiac[0]=data[4];
13   cas.mesiac[1]=data[5];
14   cas.mesiac[2]=data[6];
15   cas.mesiac[3]=0;
16   
17   //rok tvoria 4 cislice (index 8 az 11)
18   cas.rok=(data[8]-'0')*1000+(data[9]-'0')*100+(data[10]-'0')*10+(data[11]-'0');
19   
20   cas.hod=(data[13]-'0')*10+(data[14]-'0');
21   cas.min=(data[16]-'0')*10+(data[17]-'0');
22   cas.sek=(data[19]-'0')*10+(data[20]-'0');     
23   
24   // vsetky udaje o datume a case su zapisovane do premennej cas, ktoru na konci vraciame
25   return cas;
26 }

Vstupné a výstupné hodnoty

Vstupné údaje

Vstupom do programu bude súbor access.log, ktorého formát je popísaný v prvej časti zadania. Potom sa načíta z klávesnice hľadaný dátum a čas vo formáte:

  • deň: číslo od 1 do 31
  • mesiac: číslo od 1 do 12
  • rok:číslo od 1900 do 2100
  • hodina:číslo od 0 do 23
  • minúta:číslo od 0 do 59
  • sekunda:číslo od 0 do 59

Vzorový vstup

Súbor access.log musí byť pripravený. 

13 3 2009 12 55 32

Výstupné údaje

Program v prípade úspechu na výstupe poskytne nasledujúce informácie:

  • počet záznamov v súbore
  • pozíciu hľadaného záznamu v súbore
    • číslo riadku
    • percentuálne vyjadrenie pozície v súbore

V prípade neúspechu bude výstupom informácia, že v daný čas neexistuje žiaden záznam.

Vzorový vstup

Pocet zaznamov: 1680
Záznam sa nachádza na pozícii 420 (25.000 %)

Poznámka k vstupným údajom:

Na vstupe bude mesiac reprezentovaný ako číselný údaj (poradie mesiaca v roku) ale v súbore access.log je reprezentovaný ako 3-znaková skratka. Treba teda previesť číslo mesiaca na skratku. Toto docielime jednoduchým zápisom: 

1  SCas c; // c je struktura typu SCas  
2  int mesiac=3; //nacitany mesiac zo suboru
3 
4  // pomocne pole retazcom, ktore vyuzijem na prevod cisla mesiaca na skratku mesiaca
5  char mesiace[12][4]={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
6  
7  //do casti 'mesiac' struktury c (typu SCas) skopirujem retazec z pola mesiace na indexe mesiac-1
8  strcpy(c.mesiac,mesiace[mesiac-1]);

Riešenie v jazyku C

  1 #include<fstream.h>
  2 #include<iostream.h>
  3 #include<string.h>
  4 #include<stdlib.h>
  5 struct SCas{ 
  6        int den;
  7        char mesiac[4];
  8        int rok,hod,min,sek;
  9        };
 10 
 11 SCas dajCas(char *data)
 12 {
 13   SCas cas;
 14   data=strchr(data,'[');
 15 
 16   cas.den=(data[1]-'0')*10+(data[2]-'0');
 17   
 18   cas.mesiac[0]=data[4];
 19   cas.mesiac[1]=data[5];
 20   cas.mesiac[2]=data[6];
 21   cas.mesiac[3]=0;
 22   
 23   cas.rok=(data[8]-'0')*1000+(data[9]-'0')*100+(data[10]-'0')*10+(data[11]-'0');
 24   
 25   cas.hod=(data[13]-'0')*10+(data[14]-'0');
 26   cas.min=(data[16]-'0')*10+(data[17]-'0');
 27   cas.sek=(data[19]-'0')*10+(data[20]-'0');     
 28   
 29   return cas;
 30 }
 31 
 32 /**
 33 * Funckia vrati cislo mesiaca.
 34 * Vstupnym parametrom je stratka mesiaca
 35 */
 36 int dajMesiac(char mesiac[4])
 37 {
 38     if(strcmp(mesiac,"Jan")) return 1;
 39     if(strcmp(mesiac,"Feb")) return 2;
 40     if(strcmp(mesiac,"Mar")) return 3;
 41     if(strcmp(mesiac,"Apr")) return 4;
 42     if(strcmp(mesiac,"May")) return 5;
 43     if(strcmp(mesiac,"Jun")) return 6;
 44     if(strcmp(mesiac,"Jul")) return 7;
 45     if(strcmp(mesiac,"Aug")) return 8;
 46     if(strcmp(mesiac,"Sep")) return 9;
 47     if(strcmp(mesiac,"Oct")) return 10;
 48     if(strcmp(mesiac,"Nov")) return 11;
 49     if(strcmp(mesiac,"Dec")) return 12;
 50     return 0;                            
 51 }
 52 /**
 53 * Funckia porovna 2 datumy - d1 a d2
 54 * ak je d1>d2 - funkcia frati hodnotu 1
 55 * ak je d1<d2 - funkcia frati hodnotu -1
 56 * ak je d1==d2 - funkcia frati hodnotu 0
 57 * Vstupnymi parametrami jsu datumy d1 a d2
 58 */
 59 int porovnajCas(SCas c1,SCas c2)
 60 {
 61     int d1,d2;
 62     char mesiace[12][4]={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Okt","Nov","Dec"};
 63     d1=c1.den+dajMesiac(c1.mesiac)*100+c1.rok*10000;
 64     d2=c2.den+dajMesiac(c2.mesiac)*100+c2.rok*10000;
 65     if(d1>d2) return 1;
 66     if(d1<d2) return -1;
 67     d1=c1.sek+c1.min*100+c1.hod*10000;
 68     d2=c2.sek+c2.min*100+c2.hod*10000;
 69     if(d1>d2) return 1;
 70     if(d1<d2) return -1;
 71     return 0;       
 72 }
 73 
 74 int hladajBinarne(SCas *pole,int dlzka, SCas x)
 75 {
 76   int najdene=0;
 77   int lavy = 0, pravy = dlzka - 1, stred;
 78   while ( (lavy <= pravy) && (najdene==0) )
 79   {
 80     stred = (lavy + pravy) / 2;
 81     if (porovnajCas(pole[stred] ,x)==0 ) //pole[stred]==x
 82 	   najdene=1;
 83     else 
 84   	  if (porovnajCas(pole[stred] , x) < 0) //pole[stred] < x
 85 	     lavy = stred + 1;
 86 	   else 
 87  	     pravy=stred - 1;
 88    }
 89    if(najdene==1)
 90      return stred;
 91    else
 92   	 return -1;
 93 }
 94 
 95 int main()
 96 {
 97  fstream in;
 98  in.open("access.log");
 99  if(!in) { cout<<"subor sa neda otvorit"; return 0;}
100  char log[601];
101  SCas data[1000];
102  SCas x;
103  int i=0;
104  do
105  {
106     in.getline(log,600);
107     data[i]=dajCas(log);
108     i++;
109  }while(!in.eof());
110  in.close();  // zatvorenie suboru
111  int mesiac;
112  cin>>x.den>>mesiac>>x.rok>>x.hod>>x.min>>x.sek;
113  char mesiace[12][4]={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Okt","Nov","Dec"};
114  strcpy(x.mesiac,mesiace[mesiac-1]);
115  
116  int pozicia=hladajBinarne(data,i,x);
117  cout<<"Pocet zaznamov: "<<i<<endl;
118  if(pozicia>0)  
119    cout<<"Zaznam sa nasiel na pozicii: "<<pozicia;
120  else
121    cout<<"Zaznam sa nenasiel";
122  system("pause");
123 }

Opis použitých funkcií

SCas dajCas(char *data)

Funkcia je opísaná v časti " 1.2.2 Získanie dátumu a času z riadku súboru"

int dajMesiac(char mesiac[4])

Funkcia vypočíta z reťazca reprezentujúceho skratku mesiaca číslo mesiaca. Parametrom funkcie je reťazec z dĺžkou 4 znaky (3 pre skratku a 1 pre ukončujúci znak). V príapade, že mesiac patrí do množiny {"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Okt","Nov","Dec"}, funkcia vráti príslušné číslo mesiaca. V opačnom prípade vráti hodnotu 0.

int porovnajCas(SCas c1,SCas c2)

Vo funkcii hladajBinarne potrebujeme porovnávať dátumy. Premenné typu štruktúra sa nedajú porovnávať, preto je teba vytvoriť porovnávaciu funkciu. Funkcia porovnajCas má 2 parametre: c1 a c2, ktoré budeme porovnávať. V prípade, ak je c1>c2, funkcia vráti hodnotu 1, ak c1<c2, funkcia vráti hodnotu -1. Ak sú rovnaké tak funkcia vráti hodnotu 0.

int hladajBinarne(SCas *pole,int dlzka, SCas x)

Algoritmus binárneho vyhľadávania je opísaný na stránke Algoritmy vyhľadávania. V tejto variante je namiesto poľa celých čísel pole štruktúr typu SCas. Teda budeme vyhľadávať prvok x (tiež musí byť rovnakého typu ako sú všetky prvky poľa pole, teda SCas). Pre účely porovnávania hodnôt bola vytvorená funkcia porovnajCas.

Porovnanie efektívnosti vyhľadávacích algoritmov

Úloha

Porovnajte efektívnosť iteračnej a rekurzívnej verzie binárneho vyhľadávania. Pole, v ktorom budete vyhľadávať použite z predchádzajúceho príkladu. Ako kritérium pri porovnávaní zvoľte čas vykonania algoritmu. Výsledky porovnania zdôvodnite.

Analýza úlohy

Algoritmy binárneho vyhľadávania sú v časti Algoritmy vyhľadávania. Podľa zadania budeme vyhľadávať v poli štruktúr typu SCas.

V programe potrebuje odmerať čas, za ktorý sa algoritmus skončí. Využijeme na to funkciu clock() zadefinovanú v knižnici time.h, ktorá nám vráti počet taktov procesora od štartu programu. Tento [daj prevedieme na sekundy tak, že túto hodnotu vydelíme hodnotou makra CLOCKS_PER_SEC.

Pri meraní trvania jedného vyhľadávania však zistíme, že daný čas sa nám nepodarí odmerať. Preto musíme vyhľadávanie opakovať n-krát a výsledný čas ešte podeliť hodnotou n.

Riešenie v jazyku C

 1 #include <iostream.h>
 2 #include <stdio.h>
 3 #include <time.h>
 4 int main()
 5 {
 6    clock_t start, end;
 7    double elapsed;
 8    start = clock();
 9 
10    // beh algoritmu
11 
12    end = clock();
13    elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
14 
15    cout<<elapsed<<endl;
16 }
Zdroj: „http://www.kiwiki.info/index.php?title=Vyhľadávanie_(riešené_príklady)&oldid=2483“