Před chvílí jsem dopsal další projekt a to do HSC (Hardware/Software Codesign). Spočívalo to v naprogramování hardwarové jednotky, která vyhledala medián z 9-okolí nějakého bodu obrazu. To sloužilo k redukci šumi - antialiasingu obrazu. Projekt měl takový výzkumný charakter. K mediánu je třeba mít seřazenou posloupnost čísel. Řazení tedy probíhalo buď klasickým bubblesortem, dále optimalizovanější metoda (cokoliv rychlejšího než bubble sort), to bylo psané v Céčku a pak ještě ve VHDL udělat medián za pomoci řadicí sítě. To jsem objevil hned na netu, takže nebyl problém, tato komponenta se skládá z 19 prvků minmax, které vrací větší a menší hodnotu ze dvou vstupů, vše je to propojené dráty (signály). Pak se hledala nejvýhodnější sestava pro to filtrování - přes gprof jsem zjišťoval jednotlivé časy, které trvalo setřídění 9-okolí.
Problém se objevil paradoxně na tom nejjednodušším - řadicích metodách v Céčku. Napsal jsem bubble sort tímto způsobem:
char median_buble(unsigned char *sur){
int i, j;
unsigned char temp;
for (i = 0; i < (SUR_PIX-1); i++) {
for(j = 1; j < SUR_PIX; j++) {
if (sur[j] < sur[j-1]) {
temp = sur[j];
sur[j] = sur[j-1];
sur[j-1] = temp;
}
}
}
}
Prostě normální bubblesort. Poté jsem napsal quicksort jakožto tu druhou, rychlejší řadicí metodu. Jak jistě všichni víme :-), bubblesort má složitost n2, zatímco quicksort n*ln(n). U 9 prvků je to u bubblesortu 81, u quicksortu cca 19.77, quicksort by měl být tedy rychlejší. Napíšu, odladím, pustím grof a co nevidím - quicksort je pomalejší než bubblesort! Zapnul jsem tedy optimalizaci kompilátoru (-O2 i -O3) a nic, zrychlilo se to, ale obojí zhruba stejně. Přemýšlel jsem, čím to může být, pak mě to napadlo - quicksort mám rekurzivní, funkce tedy volá sebe sama, konkrétně to bylo průměrně 19x, což vede k větší režii (ukládání na zásobník, opětovné vyvolávání ze zásobníku a tak). Že by to ale zpomalovalo tak moc a to i u velkých objemů dat?
Dlabat na to, zkusím to jinak, hlavně nerekurzivně. Nerekurzivní quicksort se mi psát nechtělo, stejně ani už nevím, jak to vypadá, tak jsem zkusil insert sort, heap sort, shell sort... a nic, všechny metody dávaly pomalejší výsledek, než bubble sort! Jednomu spolužákovi jsem dal můj zdroják, aby to u sebe zkusil s ním a výsledek mě překvapil - jemu to fungovalo v pořádku, shellsort (který jsem nakonec zvolil) mu jen rychleji než bubblesort. V ostatních zdrojácích jsem nic neměnil. Tak fakt nevím.
Nakonec jsem to vyřešil vychcaně, zbývaly mi 3 hodiny do odevzdání, co mi zbývalo. S výslednými naměřenými hodnotami se nějak pracovalo dál, závěr se z toho dělal a tak. No a já vzal hodnoty, co mi vrátil shellsort a řekl jsem, že jsou to výsledky bubble sortu a naopak. :) Důležitý je, že vím, co jsem dělal, proč mi to dělalo takový prapodivnosti, to už je jedno.
Ne každý se snažil dělat projekt poctivě. Toto mi došlo od jednoho nejmenovaného spolužáka na ICQ:
(21:48:14) xxx: cus ses?
(21:52:08) m1c4a1: Tak napul.
(21:52:45) xxx: simte delals HSC? to sw optimized je jako ten quick?
(21:52:58) m1c4a1: jo
(21:53:54) xxx: ok
(21:53:58) xxx: a co je to pps?
(21:54:13) m1c4a1: picture per second
(21:54:21) m1c4a1: koukam, ze ani nevis, o co v tom projektu jde. ;))
(21:54:34) xxx: jj
(21:54:35) m1c4a1: pictures per second, tak. )
(21:54:40) xxx: ajo
(21:56:30) xxx: a kde to zjistim?
(21:56:39) m1c4a1: co kde zjistis?
(21:58:24) xxx: no to cislo pps
(22:00:07) m1c4a1: Musis naimplementovat ty radici metody, pak ten projekt spustit se zakompilovanym profilovanim, potom programem gprof zjistit, jak dlouho byl procesor v jednotlivych funkcich a z toho podle vzorecku na strankach projektu vypocitas pps.
(22:00:50) xxx: keryho vzorecku? ty hodnotz uz mam
(22:03:50) m1c4a1: No... tak vzorecek tam sice neni, ale tak je to snad jasny, ne? Tolikrat, kolikrat provedes vypocet, tak tolik je obrazku, tak to cislo tim jen vydelis.
(22:04:25) xxx: ale de ty cisla vemu?
(22:04:32) m1c4a1: ach jo...
(22:04:42) m1c4a1: [stránky projektu, tam se nedostanete :)] - precti si aspon toto
(22:06:32) xxx: to sem cetl
(22:07:46) m1c4a1: no nevypada to tak. kdybys to cetl, tak tam vidis "dobu vykonávání celého systému pro zpracování 30 snímků" apod.
...
No pokud někdo dělá projekty tímto stylem, že 2 hodiny před odevzdáním ještě ani neví, jak se to dělá a pak si projekt koupí (nabídky "Dám 2000 Kč za projekt" se na školním fóru jen hemží), co je to za studium? Jasně, taky se mi nechce něco dělat, ale jednou jsem šel na tu školu, abych se něco dozvěděl, tak si musím vytrpět i předměty, který nemám rád, ale nesnížím se k něčemu takovýmu. Pak ze školy vyjdou inženýři, kteří se k titulu prokopali uplácením a podvodama? Nemůžu říct, že by se mi to líbilo.
Projekty už jsou za mnou, teď se vrhnout na učení na zkoušky, na řadě jsou pokročilý databáze, ještě to 14 dní vydržím a pak bude snad už klid.
Problém se objevil paradoxně na tom nejjednodušším - řadicích metodách v Céčku. Napsal jsem bubble sort tímto způsobem:
char median_buble(unsigned char *sur){
int i, j;
unsigned char temp;
for (i = 0; i < (SUR_PIX-1); i++) {
for(j = 1; j < SUR_PIX; j++) {
if (sur[j] < sur[j-1]) {
temp = sur[j];
sur[j] = sur[j-1];
sur[j-1] = temp;
}
}
}
}
Prostě normální bubblesort. Poté jsem napsal quicksort jakožto tu druhou, rychlejší řadicí metodu. Jak jistě všichni víme :-), bubblesort má složitost n2, zatímco quicksort n*ln(n). U 9 prvků je to u bubblesortu 81, u quicksortu cca 19.77, quicksort by měl být tedy rychlejší. Napíšu, odladím, pustím grof a co nevidím - quicksort je pomalejší než bubblesort! Zapnul jsem tedy optimalizaci kompilátoru (-O2 i -O3) a nic, zrychlilo se to, ale obojí zhruba stejně. Přemýšlel jsem, čím to může být, pak mě to napadlo - quicksort mám rekurzivní, funkce tedy volá sebe sama, konkrétně to bylo průměrně 19x, což vede k větší režii (ukládání na zásobník, opětovné vyvolávání ze zásobníku a tak). Že by to ale zpomalovalo tak moc a to i u velkých objemů dat?
Dlabat na to, zkusím to jinak, hlavně nerekurzivně. Nerekurzivní quicksort se mi psát nechtělo, stejně ani už nevím, jak to vypadá, tak jsem zkusil insert sort, heap sort, shell sort... a nic, všechny metody dávaly pomalejší výsledek, než bubble sort! Jednomu spolužákovi jsem dal můj zdroják, aby to u sebe zkusil s ním a výsledek mě překvapil - jemu to fungovalo v pořádku, shellsort (který jsem nakonec zvolil) mu jen rychleji než bubblesort. V ostatních zdrojácích jsem nic neměnil. Tak fakt nevím.
Nakonec jsem to vyřešil vychcaně, zbývaly mi 3 hodiny do odevzdání, co mi zbývalo. S výslednými naměřenými hodnotami se nějak pracovalo dál, závěr se z toho dělal a tak. No a já vzal hodnoty, co mi vrátil shellsort a řekl jsem, že jsou to výsledky bubble sortu a naopak. :) Důležitý je, že vím, co jsem dělal, proč mi to dělalo takový prapodivnosti, to už je jedno.
Ne každý se snažil dělat projekt poctivě. Toto mi došlo od jednoho nejmenovaného spolužáka na ICQ:
(21:48:14) xxx: cus ses?
(21:52:08) m1c4a1: Tak napul.
(21:52:45) xxx: simte delals HSC? to sw optimized je jako ten quick?
(21:52:58) m1c4a1: jo
(21:53:54) xxx: ok
(21:53:58) xxx: a co je to pps?
(21:54:13) m1c4a1: picture per second
(21:54:21) m1c4a1: koukam, ze ani nevis, o co v tom projektu jde. ;))
(21:54:34) xxx: jj
(21:54:35) m1c4a1: pictures per second, tak. )
(21:54:40) xxx: ajo
(21:56:30) xxx: a kde to zjistim?
(21:56:39) m1c4a1: co kde zjistis?
(21:58:24) xxx: no to cislo pps
(22:00:07) m1c4a1: Musis naimplementovat ty radici metody, pak ten projekt spustit se zakompilovanym profilovanim, potom programem gprof zjistit, jak dlouho byl procesor v jednotlivych funkcich a z toho podle vzorecku na strankach projektu vypocitas pps.
(22:00:50) xxx: keryho vzorecku? ty hodnotz uz mam
(22:03:50) m1c4a1: No... tak vzorecek tam sice neni, ale tak je to snad jasny, ne? Tolikrat, kolikrat provedes vypocet, tak tolik je obrazku, tak to cislo tim jen vydelis.
(22:04:25) xxx: ale de ty cisla vemu?
(22:04:32) m1c4a1: ach jo...
(22:04:42) m1c4a1: [stránky projektu, tam se nedostanete :)] - precti si aspon toto
(22:06:32) xxx: to sem cetl
(22:07:46) m1c4a1: no nevypada to tak. kdybys to cetl, tak tam vidis "dobu vykonávání celého systému pro zpracování 30 snímků" apod.
...
No pokud někdo dělá projekty tímto stylem, že 2 hodiny před odevzdáním ještě ani neví, jak se to dělá a pak si projekt koupí (nabídky "Dám 2000 Kč za projekt" se na školním fóru jen hemží), co je to za studium? Jasně, taky se mi nechce něco dělat, ale jednou jsem šel na tu školu, abych se něco dozvěděl, tak si musím vytrpět i předměty, který nemám rád, ale nesnížím se k něčemu takovýmu. Pak ze školy vyjdou inženýři, kteří se k titulu prokopali uplácením a podvodama? Nemůžu říct, že by se mi to líbilo.
Projekty už jsou za mnou, teď se vrhnout na učení na zkoušky, na řadě jsou pokročilý databáze, ještě to 14 dní vydržím a pak bude snad už klid.
Žádné komentáře:
Okomentovat