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

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.

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 CSas  
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 CScas) skopirujem retazec z pola mesiace na indexe mesiac-1
8  strcpy(c.mesiac,mesiace[mesiac-1]);