Matfyz Wiki
Termín byl od 10:00, byl tam s námi Tomáš Kalibera, dostali jsme na to 3 hodiny, s tím, že nikdo přesně nevěděl, kdy se začíná počítat čas. Asi po půhodině vypravování a upřesňování zadání řekl, že budem končít v 13:20. A teď zadání (doslova, tištěné):
Analyza protokolu o behu programu ----------------------------------------- Napiste program pro analyzu protokolu (trace) o prubehu programu v systemu Mono. Trace je ulozen v textovem souboru, jehoz format je podrobne popsan nize - pri kazdem zavolani metody a kazdem navratu z metody pribude v trace jedna radka. Ukolem analyzatoru je pro zadane metody zjistit a vypsat seznam volajicich metod a seznam volanych metod - upresneno nize. Pro testovani mate k dispozici dva testovaci protokoly (traces). Format trace: --------------- Kazda radka trace souboru se sklada z * nula a vice opakovani retezce ". " - podle hloubky zanoreni volani * z retezce "ENTER: " nebo "LEAVE: " - budto zavolani nebo navrat z metody * z nula nebo jednoho retezce "(wrapper neco) ", kde neco je posloupnost pismen, cislic a podtrzitek - volani takto oznacenych metod, i vsechna vnorena volani, ignorujte. * z retezce tvaru "Namespace.Trida:", kde namespace je posloupnost pismen, cislic, podtrzitek a tecek (teckami jsou oddeleny casti namespace). Trida je posloupnost pismen, cislic a podtrzitek. * z retezce tvaru "metoda" - posloupnost pismen, cislic a podtrzitek, muze zacinat teckou. * z oznaceni typu argumentu tvaru "(neco)", kde neco je posloupnost znaku neobsahujici uzavrenou zavorku ")" * dalsi casti radky ignorujte Upresneni: ------------ Pouziti programu: trace -t soubor_s_trace metoda1 metoda2 metoda3 ... metodan metodax ... zapis "Namespace.Trida:metoda (oznaceni_typu)", vcetne uvozovek, aby operacni system poznal, ze se jedna o jeden argument Forma vystupu: pro kazdou zadanou metodu se vypise seznam volanych metod a seznam volajicich metod, identifikace metod je stejna jako na prikazove radce. uvazuje se jenom seznam primo volanych resp. primo volajicich metod (ne tranzitivni uzaver).
Dal nám pak odkaz na 2 testovací soubory:
http://nenya/~kalibera/files/c/hw.zip (heslo: nazdar)
http://nenya/~kalibera/files/c/rijndael.zip (heslo jsem zapomnel)
Když jsme si každej stáhli tydle soubory na lokální disk, tak otevřel rozváděcí skřín, a vytáh síťovej kabel.
Pak začalo upřesňování zadání. Zjistili jsme, že v testovacích souborech jsou i řádky, které nemají tento formát. Máme je prý ignorovat. Pokud je řádka volání wrapperu (které máme taky ignorovat), tak máme navzdory zadání ignorovat pouze tuto řádku a ne všechna vnořená volání. Jinak by totiž výstup byl vždy prázdný (strom volání začíná vždy wrapperem). To, že toto ignorování rozhodí počet ". " na začátku řádek, je pravda, nicméně s tím máme počítat (v zásadě nebylo třeba vůbec s tečkama počítat, já je třeba uplně ignoroval). Druhý testovací soubor byl hodně velký (asi 50 MB), takže bylo nutné aby ho program zpracoval v rozumném čase. Mohli jsme používat C, C++, libovolně STL (ale nic platformně specifického), ovšem NESMĚLI jsme používat asociativní pole z STL.
A moje dojmy: V 11:40 jsem odcházel jako první s tím, že jsem to udělal. Ostatní tam ještě sedí. Celé jsem to napsal v C++, použil jsem hromadu STL: string, list, vector, stack, na všechno jsem nasadil iterátory, takže výsledek jsem měl na 120 řádků. Na 50 MB souboru mi průběh trval asi 10 vteřin (pozor na rozdíl mezi debug a release verzí, rozdíl v rychlosti byl hodně znát), což prohlásil za OK. Řešil jsem to tak, že jsem měl strukturu
struct metodainfo {
string jmeno;
list<string> volametody;
list<string> volanazmetod;
};
Tuto strukturu jsem měl v poli:
vector<metodainfo> metody;
Z parametrů jsem toto pole naplnil. Pak jsem procházel všechny řádky (pomocí getline(stream, string)), zahodil všechny tečky ze začátku, ignoroval wrappery. Když jsem našel ENTER, hodil jsem ho na zásobník (stack<string> zasobnik;), když leave, tak jsem dal pop ze zásobníku. A pro každou řádku jsem se podíval, jestli na vrcholu zásobníku je metoda z př. řádky. To potom znamená že aktuální metodu přidám do volaných metod. A pokud je aktuální řádek něco z př. řádky, přidám do seznamu metod ze kterých se volá. Je to trochu zmatečné, všechny ty pole seznamů stringů. Ale je to IMHO nejjednodušší způsob řešení (nemusí se nic kontrolovat, délka řádků, nic alokovat, nic, nic, nic). Nakonec jsem ještě pole (vector<metodainfo>) změnil na spoják (list<metodainfo>), ale to už je celkem jedno.