Zápočet 29.5.2007

matfyzak
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 3. 1. 2007 18:34

Zápočet 29.5.2007

Příspěvek od matfyzak »

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é):

Kód: Vybrat vše

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

Kód: Vybrat vše

struct metodainfo {
  string jmeno;
  list<string> volametody;
  list<string> volanazmetod;
};
Tuto strukturu jsem měl v poli:

Kód: Vybrat vše

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.
Odpovědět

Zpět na „2006“