Optimize me!
Tole spodaj je implementacija operaterja + za class Coord. Coord je en preprost razred, ki združuje tri integerje, ki predstavljajo koordinate v prostoru. X, Y in Z.
Kaj počne operter +? Izvede premik v željeno smer. Vseh možnih smeri je 26 (če sem jaz prav preštel). Vse smeri so zajete v enum vrednostih od 0, pa do 26 (tri ravnine, trenutna, zogrnja in spodnja, vsaka z osmimi možnimi smermi, plus pomik vertikalno, gor ali dol).
Torej imam my_place = Coord(10, 10, 10) in rad bi se premaknil en sektor naprej, zato izvedem my_place = my_place + Space::Dir_F;
Operater plus mora to prestreči in ugotoviti, da vse kar mu je za narediti je to, da poveča vrednost spremenljivke, ki predstavlja pozicijo na Z (m_Z) osi, za ena. Tako bo nova koordinata 10, 10, 11. Če bi se rad premaknil za eno polje nazaj, desno spodaj, potem bom my_place prištel Space::Dir_BDR. Operater bo sedaj najprej m_Z zmanjšal za ena, m_X bo povečal za ena in m_Y bo prav tako zmanjšal za ena. In če izhajam iz prejšnje pozicije, bo nova koordinata sedaj, 11, 9, 10.
Po moji kurji pameti sem implementiral tale operater tako, da sem premike razdelil na tri osi in potem glede na to, kak je bil premik ustrezno povečeval oziroma zmanjševal m_X, m_Y in m_Z. Pri zmanjševanju sem dodal še bremzo, da ne gre v negativo.
Torej, sledi vprašanje, bi lahko tole premikanje še bolj optimiziral? Ga izvedel mogoče kako drugače?
[cpp]
Coord & Coord::operator+ (int dir)
{
switch (dir)
{
case Space::Dir_None:
break;
case Space::Dir_F:
case Space::Dir_FR:
case Space::Dir_FL:
case Space::Dir_FU:
case Space::Dir_FUR:
case Space::Dir_FUL:
case Space::Dir_FD:
case Space::Dir_FDR:
case Space::Dir_FDL:
m_Z++;
break;
case Space::Dir_BR:
case Space::Dir_B:
case Space::Dir_BL:
case Space::Dir_BUR:
case Space::Dir_BU:
case Space::Dir_BUL:
case Space::Dir_BDR:
case Space::Dir_BD:
case Space::Dir_BDL:
if (m_Z > 0) m_Z–;
break;
default:
break;
}
switch (dir)
{
case Space::Dir_None:
break;
case Space::Dir_FR:
case Space::Dir_R:
case Space::Dir_BR:
case Space::Dir_FUR:
case Space::Dir_UR:
case Space::Dir_BUR:
case Space::Dir_FDR:
case Space::Dir_DR:
case Space::Dir_BDR:
m_X++;
break;
case Space::Dir_BL:
case Space::Dir_L:
case Space::Dir_FL:
case Space::Dir_BUL:
case Space::Dir_UL:
case Space::Dir_FUL:
case Space::Dir_BDL:
case Space::Dir_DL:
case Space::Dir_FDL:
if (m_X > 0) m_X–;
break;
default:
break;
}
switch (dir)
{
case Space::Dir_None:
break;
case Space::Dir_U:
case Space::Dir_FU:
case Space::Dir_FUR:
case Space::Dir_UR:
case Space::Dir_BUR:
case Space::Dir_BU:
case Space::Dir_BUL:
case Space::Dir_UL:
case Space::Dir_FUL:
m_Y++;
break;
case Space::Dir_D:
case Space::Dir_FD:
case Space::Dir_FDR:
case Space::Dir_DR:
case Space::Dir_BDR:
case Space::Dir_BD:
case Space::Dir_BDL:
case Space::Dir_DL:
case Space::Dir_FDL:
if (m_Y > 0) m_Y–;
break;
default:
break;
}
return *this;
}
[/cpp]
13 thoughts on “Optimize me!”
Quick look… Tukaj mi marsikaj manjka…
Najbrz… 😉
Čemu bi ne bili vsi tisti Dir_ takisto instance Coord in bi jih potem sesšteval kot hruške?
Druga ideja je specializacija kalupov glede na smer. Če se potrudiš lahko napišeš generator teh kalupov, tako da koda ne bo več tako klobasasta in še izvajanje bi načeloma naj bilo hitrejše.
Zdaj se ukvarjam z bizarnostjo ustvarjanja 3D arraya v C++ in sicer taksnega kjer velikost arraya ni znana ob casu compilanja.
Owca. Kalup? Em? Template?
Meni se tudi dopade tista ideja s hruškami. Itak imaš znano število smeri.
Bizarnost ustvarjanja 3D array-a v času compilanja? Hja – če se dobro spomnim (2 leti nazaj, pa še fortran) so bile neke veze z allocate, pa ne bi več vedel točno kako. Je pa blazna zajebancija, ker compiler (v tistem primeru Compaq fortran) ni hotel sprostit placa, pa potem sploh ni bil hec v tem… Stric Google je izpljunil odgovor (po dveh dneh teženja). Za C++ pa priznam, da nimam pojma. Pa nimaš česa bolj humanega za tako zadevo?
optimizacija? odvisno kaj bi rad optimiziral? če hitrost izvajanja, potem naredi en sam switch in v njem za vsako smer izvedi vsa potrebna prištevanja… če gre za velikost kode, potem je ovčja pripomba jako elegantna! sam bi jo dodelal še takole: narediš polje, poimenujva ga dir_coords, v katerem je element z indeksom Dir_Nekaj konstantni primerek razreda Coord, katerega prostorske koordinate so natanko spremembe dotične koordinate pri premiku v smer Dir_Nekaj (za Dir_Up recimo (0,0,1), torej je dir_coord[Dir_Up] = new Coord(0,0,1)). potem preprosto napišeš operator +, ki sešteje dva primerka razreda Coord, operator +, ki Coordu prišteje smer (to, kar imaš zapisano zgoraj) pa implementiraš takole:
Coord & Coord::operator+ (int dir) {
return (*this) + (*dir_coord[dir]);
}
Morda reč ni za C++-u najbolj sintaktično pravilna, ampak ta poseg prepuščam tebi… Sam se gnusne pokveke, ki si upa sebe proglasiti za jezik, in sliši na ime cplusplus že kar nekaj časa nisem pritaknil…
Templatei (mmg, všeč mi je izraz kalup, owwwca)?! V C++u?!?! Najbolj gnusna stvar na svetu… Template v jezikih, ki ne premorejo RTTIja in reflection-like sposobnosti, bi bilo treba prepovedati z zakonom! Pod grožnjo smrtne kazni! V C++u povzročajo milijon težav: ko jih hočeš recimo spravit v knjižnico moraš vnaprej predvidet za katere tipe bodo nekoč uporabniki template instanciral… No, ampak saj v C++u še milijon drugih bebavih konstruktov povzroča težave… Stroustrupa bi morali križati, potem pa obesit na kakšno drevo, bodočim jezikostvarjalcem v opomin, poduk in svarilo!
Hehe, kako si se zapletel. Samo malo moraš svoj enum spremeniti pa bo bolše:
//somewhere in Space:
enum Direction {
Dir_L = 1,
Dir_R = 2,
Dir_U = 4,
Dir_D = 8,
Dir_F = 16,
Dir_B = 32
};
Coord & Coord::operator+ (Space::Direction dir)
{
if (dir && Space::Dir_L)
–m_X;
else if (dir && Space::Dir_R)
++m_X;
if (dir && Space::Dir_U)
++m_Y;
else if (dir && Space::Dir_D)
–m_Y;
if (dir && Space::Dir_F)
++m_Z;
else if (dir && Space::Dir_B)
–m_Z;
return *this;
}
Naslednja izbira zame bi bila pa lookup tabela. Je pa odvisno kje uporabljaš tele “koordinata + smer”, bolj kot imaš to ozko določeno, lažje optimiziraš. Sploh se mi zdi tale operator+ mal overkill.
Aja valda v tvoj enum dodaš še Dir_LU = Dir_L | Dir_U, itd.
Hmmm, ma hitrost me niti ne zanima tako zelo, bolj codewise optimizacija v smislu berljivosti kode. Tole kar je Gundolf predlagal z biti, niti ni tako zelo napacno. Z biti sem precej delal nekaj let nazaj… pa se je kar obneslo.
Ceprav tudi tole s sestevanjem koordinat ni napacno, tako bi dobil tudi premik za vec sektorjev v zeljeno smer,…
No, sem pa optimiziral samo vesolje. Sedaj mi iz enega botka rata 100*100*100 botov v kakih petih sekundah, s tem, da se pred tem ustvari se 100*100*100 vesolje.. Prej je trajalo skoraj dve minuti. Ne sprasujte… 😛
glede hitrosti sem prej zabluzil… en switch s kupom caseov se seveda prevede v kup primerjanj in branchev, kar pomeni, da v najslabšem primeru dobiš n-1 primerjanje… hitrostno optimalna varianta je, jasno:
int coord_delta_4_dir[N_DIRS][3];
/* velja npr.
coord_delta_4_dir[Dir_U][0] = 0;
coord_delta_4_dir[Dir_U][1] = 0;
coord_delta_4_dir[Dir_U][2] = 1;
*/
potem izvedeš plus z:
Coord & Coord::operator+ (int dir) {
m_X += coord_delta_4_dir[dir][0];
m_Y += coord_delta_4_dir[dir][1];
m_Z += coord_delta_4_dir[dir][2];
return *this;
}
Še nekaj čisto C++ovskega. Ne vem kako ti uporabljaš tale tvoj operator+ ampak tale definicija je po moje čisto zgrešena. Zaenkrat dela tako:
a = b + Space::Dir_L;
a in b dobita isto vrednost in sicer b + levo.
Mogoče (če res želiš da tako deluje) bi ti bolj prav prišel operator +=.
Jaz bi se tudi šel JaKovo varianto z arrayom 26-tih Coord (vektorjev).. od -1,-1,-1 do 1,1,1 brez 0,0,0, pa si definiraš seštevanje (+checking negativnih koordinat).
Potem pa sam prišteješ 🙂
current+=premik[dir];
Comments are closed.