hesh tabela ili nesto drugo

[genuine]

e imam jedan problem... u c++ imam neku klasu Object koju nasledjuju skoro sve bitne klase ( fazon jave). medutim object ima svoje ime u vidu stringa... e sad kako se kreira objekat tako se dodaje u odgovarajucu strukturu podataka koja treba da cuva sve objekte i da kada joj zatrazim ime vrati dati objekat.... a bitno je da to uradi sto brze...

 

[Zoran Milosevic]

ne razumem bas najbolje sta si mislio sa:
"object ima svoje ime u vidu stringa".
da nisi mislio na pokazivac na object tipa string ili metodu koja vraca odredjeni string? i da odgovarajuca struktura podataka (stek,niz,lista...) cuva pokazivace na objekte?

pre nego sto pozelis da koristis pokazivace (reference) na objekte iz niza u vidu prikazivanja iste "vrste" (ili svih) objekata redefinisanim metodama ili sta vec, ne bi bilo lose da proucis polimorfizam.

a to da li ces koristiti hash ili sta vec, u svakom slucaju bice brze od istog resenja problema odradjenog u javi. :type:

 

[GOXY83]

Pojasni malo pitanje...
"object ima svoje ime" mislis polje tipa string? I hoces da nekoj metodi definisanoj za strukturu prosledis ime kao argument, a da ti ona vrati referencu ili pointer na objekat sa tim imenom? znaci svaka instanca objekta (odnosno instanca klase izvedene iz objekta) ima drugacije ime? i onda bi to ime trebalo da bude kljuc pri pretrazivanju?

Imas li unapred zadat skup mogucih imena? koliki je broj objekata koji bi isli u takvu strukturu?

 

[genuine]

pa konkretno... imam fajl oblika XML koji kaze recimo :
<MaterialBMP name="Material #9">
<Ambient r=0.4 g=0.4 b=0.4>
<Diffuse r=0.8 g=0.8 b=0.8>
<Specular r=0.8 g=0.8 b=0.8>
<ShinninessExp value=25.0 >
<Texture filename="Scenes\Maps\Arrow.jpg">
</MaterialBMP>
<TModel name="Ok">
<UsingModel name="MODEL-Ok">
<UsingMaterial name="Material #9">
</TModel>
<TriMesh name="MODEL-Ok">
....

sve su to "objekti sa imenom" kada ih ucitavam iz fajla pravim objekte odgovarajuceg tipa izvedenog iz Object i dodajem ih u "stukturu" koja mi za zadato ime vraca referencu na objekat
Ovo je korisno kada u skript jeziku zelim da kazem translate "Ok" [1,2,3] da bi pomerio objekat TModel.... znaci koja je sturktura najbrza za cuvanje ovakvih objekata? Ovo je takodje korisno jer se hijararhija veoma lako ucitava iz fajla znaci nema pokazivaca,referenci vec samo imena a kad na primer ocu zatreba sin on ga zove po imenu a ne po maticnom broju ) ( naravno kad mu on dodje i "uhvati ga" oda moze da mu doda pokazivac kao lanac zbog performansi.. ( sad vise ne mora da ga zove .. samo povuce lanac )



primer:
TModel *t = new TModel ;
t->assignName("blablabla") // metoda koja dodaje objekat u strukturu
.
.
.
TModel &k = (TModel &)Object::get("blablabla"); // staticka metoda koja vraca objekat

p.s. imena su proizvoljni stringovi max duzine 128 karaktera...

 

[GOXY83]

Hm, po meni je jedini nacin da izbegnes listu i sekvencijalno pretracivanje da cupas neke charove iz tog stringa pa da recimo ascii vrednosti i duzinu tog stringa propustas kroz neku hesh funkciju

Mozda neko ima bolju ideju....

 

[F.L.C.X.]

Pa ako ti je u napred poznat maksimalan broj objekata, koji može da ti se pojavi, onda neka heš tabela ili eventualno proširljivo/proširivo heširanje. U suprotnom možda neko balansirano stablo.

 

[monteboy]

Dovoljan ti je recimo HashMap, u MFCu je to jednostavno realizovano u vidu klase

CMapStringToOb ili CMapStringToPtr
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclib/html/_mfc_cmapstringtoob.asp

E sad ako sam te razumio ti zelis da imas Container klassu za svoje objekte sa Metodama kao Get i Add. Nesto poput ovoga:

class ObjContainer : public CObject
{
   CMapStringToPtr m_ObjMap;
   
public:
   ObjContainer(){};
   ~ObjContainer(){};

   CObject* Get(const char* psObjName) 
   {
         CObject* pObjPtr=NULL;
         m_ObjMap.Lookup(psObjName,pObjPtr);
    
         return pObjPtr;
   };

   void Add(const char* psObjName,CObject* pObj)
   {
          m_ObjMap.SetAt(psObjName,pObj);
   };

   Rem(const char*  psObjName)
   {
         m_ObjMap.RemoveKey(psObjName);
   }
}

naravno sve methode se odnose na HashMap i njenu organizaciju alokacija i ciscenje samih Objekata mozes da vrsis spolja mada i to moze da se implementira direktno u ovoj klasi so bi imalo i vise smisla kad govorimo o containeru za Objekte.

 

[genuine]

Ok .. mislim da je to to.. doduse ne smem da koristim mfc zbog portabilnosti...

hvala svima..

 

[silverglider]

Hm, pretpostavljam da ti to treba za onaj engine. Problem sa nasim preporukama je u tome sto mi ne znamo nacin upotrebe tih podataka, kao ni logicku organizaciju tih tvojih podataka (neko sortiranje objekata u kategorije/klase, moguci broj instanci neke odredjene klase), ukupnu kolicinu tih podataka, itd. Pod ovim "upotreba podataka" mislim na to da li se to jednom samo ucita iz fajla i dalje samo cita, koliko cesto se podaci/objekti apdejtuju, koliko cesto (i koliko ukupno) struktura moze da naraste, videti verovatnocu koliko cesto treba uraditi re-hash ili re-sort, itd.
Hash je najbrzi kao lookup mehanizam, (pojednostavljujem situaciju i to vrlo) kada iz velike gomile podataka vadis jedan objekat; na primer, iz telefonskog imenika broj telefona prema imenu i prezimenu vlasnika. Medjutim, kada treba iz strukture da izvadis neki (logicki sekvencijalni) niz podataka ("daj mi podatke o svim teksturama vezanim za NPC broj n"), onda to sa hashom moze i da potraje - u tom slucaju tree moze da ispadne brze resenje. Druga stvar o kojoj moras da vodis racuna je ukupna velicina strukture; kod 3D endzina to moze da bude poprilicno veliko. Pitanje je koliko koja struktura treba dodatnih resursa da bi uradila re-sort ili re-hash. Mozda je za tebe dobitna kombinacija takva da je osnovna struktura hash tabela, a u okviru hash tabele za grupu objekata kod koje bi doslo do kolizije napravis recimo red-black tree (znaci, kolizija se resava chainingom).

Dakle, posto varijetet objekata i njihove upotebe znas samo ti, moj ti je predlog da generises dve demo grupe podataka; jedna grupa (iliti tvoj xml fajl) bi bio minimalisticki scenario, a druga worst case scenario (i po velicini i po raznolikosti podataka) i onda isprobas par predlozenih algoritama na konkretnom setu podataka, belezis kako vreme, tako i trosenje resursa i na kraju sam vidis sta ti se vise isplati.

 

[genuine]

HM..
za sad prva verzija koja mi je pala na pamet je hesh tabela sa odvojenim ulancavanjem. Ako stavim crveno crna ili avl stabla ( u kombinaciji sa hes tabelom) dobicu logaritamsku pretragu sto je dobro ali cu izgubiti malo na memoriji i vremenu potrebnom za azuriranje stabla..
ukoliko na primer imam dovoljno veliki broj ulaza u tabelu i ako ne bude puno kolizija onda po ulazu ne bi trebalo da ima vise od dva tri objekata ( koliko sam eksperimentisao) pa mi stabla tu ne pomazu. u najgorem slucaju bi se svi napakovali na jedan ulaz ( nedaj boze ) i onda vec ima poentu ubaciti stabla...
to cu jos da pogledam...
e.sad. nesto sto mi je palo usput..
kada imam jednu povezanu listu koja se naravno azurira tokom rada programa
i ja pristupam recimo u proseku elementu u sredini liste.. ja u sustini trebam da prodjem kroz pola liste da bi dosao do njega.. ali kako ja alociram memoriju za svaki cvor pojedinacno u razlicitim vremenima onda i adrese koje ti cvorovi imaju bice relativno udaljene jedna od druge.. ako sada cvor ima ( 8 bajtova- 4 za pokazivac na sledeci i 4 za pokazivac na podatak) onda da bi pristupio jednom cvoru ja moram da napunim celu kes liniju zbog tih 8 bajtova i da pri skoku na sledeci cvor ponovo uradim isto i isto...(ako vec nisu u kesu a bar kod endzina nece biti sanse da budu sa obzirom sta sve prolazi kroz procesor) Koliko se isplati ( odnosno kolika je praksa programera) da se o tome vodi racuna...? Recimo kada bih alocirao po 8
takvih nodova od jednom poravnatih sa 64, onda bi oni svi stali u jednu kes liniju i bilo bo efikasnije.. slicno i sa stablima...

 

[silverglider]

Ako je ogranicena kolicina tih podataka i radi se o kljucnom nizu podataka, sto ne bi koristio sortirani array umesto liste? Em su elementi jedan do drugoga, em nema nikakve potrebe za sekvencijalnim pretrazivanjem. Ono, ne radis utility program koji treba da bude 300K umesto 1M, pa da se jezis na upotrebu arraya; za 3D engine trosis vec "sumanute" kolicine memorije i ako je kljucna brzina...