dev.gamez.lv

[elvman]

Ok, izveidoju hash table (izrādās, ka tas tomēr neprasija tika daudzlaika, pāris minūšu darbs) ar visiem iteratoriem un string atbalstu.

Vienīgie jautājumi ir saistībā ar iteratoriem, man viņi darbojas tā:

Ir klase CIterator, kurā glabājas pointeri uz iepriekšējo un nākošo iteratoru (un pašu objektu, kam ir šis iterators). Kad pievienoju listei jaunu elementu, dabūju tā Indexu tabulā, un tad braucu pa tabulu uz atpakaļu, līdz dabūju iepriekšējo elementu, un tieši to pašu daru uz priekšu, lai dabūtu nākošo elementu.

Kad elements tiek izdzēsts, tad iepriekšējā iteratora nākošais iterators ir izdzēstā iteratora nākošais iterators,un nākošā iteratora iepriekšējais iterators ir izdzēstā iteratora iepriekšējais iterators.
Pseidokods:
Dzēst(Iterators)
{
IepriekšējaisIterators=Iterators->prev;
NākošaisIterators=Iterators->next;

IepriekšējaisIterators->next=NākošaisIterators;
NākošaisIterators->prev=IepriekšējaisIterators;

IdzēšamIteratoru(index);
}

Šo metodi dabūju pats izdomāt, jo literatūru netā ir diezgan grūti atrast. Varbūt ir kāda labāka metode, kā to visu darīt?
_________________
long time; /* know C */

[bubu]

Literatūru ir atrast viegli, vajag tikai pareizos keywordus zinā - doubly linked list: http://en.wikipedia.org/wiki/Linked_list#Doubly-linked_lists
Vispārīgā variantā iesaku pamācīties par datu struktūrām, daudz labu lietu sapratīsi:
http://en.wikipedia.org/wiki/Data_structure (rindas, steki, koki, grafi, un tml).
http://en.wikipedia.org/wiki/Category:Data_structures

Par to kā labāk darīt - tad jautājums, kam tev šāds CIterator ir vajadzīgs?

[elvman]

Pastudēju tavus linkus, mans variants bija identisks tavam dotajam Doubly-linked list (biju pieļāvis nelielas loģikas kļūdas). Tagad visi iteratori strādā ideāli un nemaz neprasīja tik daudz laika. Atkal atsvešinos no STL...
_________________
long time; /* know C */

[bubu]

Vispār, ko es personīgi būtu darījis tavā gadījumā - lietojis std::map. Pirmkārt - tas strādā, ir pārbaudīts un ir maz ticam, ka STLā ir kāda kļūda (ko galīgi nevaru teikt ne par tavu implementāciju, no offence, ne arī par savu, ja tādu rakstītu). Otrkārt - vai tiešām šī id lookapošanā mapā būtu performances bottleneks? Es ceru, ka tu zini, 90/10 likumu - ka gandrīz jebkurā softā, tai skaitā spēlēs, 90% CPU laika tiek pavadīts 10% koda. Tas nozīmē, ka kods ir jāoptimizē tikai tajos 10% koda, kas parasti ir vienā konkrētā vietā. Mūsu Squares3D mēs lietojam map'u visur, kur vien vajag asociatīvo konteineru neuztraucoties par performances zudumiem (hash_map vs map), jo es zinu, ka tā nu noteikti nav vieta, kas rada bremzi. Zinu daudz citas vietas savā kodā, kas rada bremzi.

Jo redzi, kāda jēga optimizēt std::map šim tavam gadījumam, ja performancē iegūsi tikai labi ja 1% ? Es nesaku, ka nevar iegūt vairāk, iespējams var - tas atkarīgs no koda. Bet veltīt tik daudz laika optimizējot šo 1%... vai ir jēga? Manuprāt labāk veltīt laika optimizējot patiešām performances kritiskas lietas tādējādi iegūstot 10%, 20% vai pat vairāk procentu ātrdarbības.

Kā gudri vīri saka - "premature optimization is the root of all evil".
http://www.flounder.com/optimization.htm
http://en.wikipedia.org/wiki/Optimization_(computer_science)


Ak jā, ja runā konkrēti par std::map implementāciju, tad tā vispārīgi rēķinot, pieņemsim, ka tev ir n=1000 objekti salikti kādā mapā. Un ja tu gribēsi noskaidrot vai kaut kāds identifikators ir šajā mapā vai nav (find metode), tad nepieciešamo darbību skaita kārta (aptuveni) ir log2(n), kas nozīmē to, ka būs nepieciešamas ap 10 salīdzināšanas (tb if konstrukcijas) un 10 pointeru dereferencēšanas (a = a->left). Man tas nemaz nešķiet tik ļoti "dārgi".

[elvman]

Nu man daļa no šiem 10% arī būtu tā identifikatoru padarīšana, jo spēlē viss tiek balstīts uz šiem identifikatoriem (burvestības, radījumi, objekti, spēlētāji, pat charakteru skini) un katrā loopā ir n-tās reizes ir jārakņājas pa šīm listēm.
Un neprasīja tas nemaz tik daudz laika izveidot šo hash listi, bet ieguvumam vajadzētu būt milzīgam (vēl neesmu testējis uz lieliem datu apjomiem). Kļūdām arī nevajadzētu būt (notestēju au visos variantos, tomēr 100% pārliecināts nekad nevar būt).
_________________
long time; /* know C */

[bubu]

[elvman]

Ok, paskatīšos kādi rezultāti būs profilera testam.
_________________
long time; /* know C */

[elvman]

Man tagad viena neliela problēma. Gribētu, lai lietotāji varētu no klases ārpuses definēt hash un salīdzināšanas funkcijas.
Klases sākums izskatās tā:

[bubu]

Nesapratu tavu problēmu no tava koda piemēra.

Cik saprotu gribi customizētus datu tipus likt savā konteinerī? Un tāpēc ir jābūt hešfunkcijai pieejamai, kuru nezini kā definēt? Tad ir divi varianti - taisi memberfunkcijas savām klasēm (cik saprotu šo tu negribi), vai arī izmanto funkciju overloadingu (līdzīgi kā STLā tiek realizēts operator << outstreamam):

[elvman]

Ui, neiedomājos padarīt šīs member funkcijas par statiskām (static). Viss OK, lietotājs, gan no klases ārpuses var padod savas funkcijas ar SetEqualFunction(funkcija), gan arī CList klase var izmantot savējās (statiskās) funkcijas, ja lietotājs tās nav uzstādījis pats.
_________________
long time; /* know C */

[bubu]

Kāpēc tam CList'am vispār vajag kautkādas savējās statiskās funkcijas izmantot?
Es iepriekšējā postiņā pie Edit2 pierakstīju kāpēc tavs risinājums nav labs no ātrdarbības viedokļa.

[bubu]

Pēc garām diskusijām IRC dimensijā tika viennozīmīgi nolemts, ka "premature optimization is the root of all evil", jo realizētais CList nemaz nestrādāja pareizi. Rezultātā kods tika atgriezts pie "sentēvu" metodēm - std::map<A,B>. Pie reizes tika iznīdēts "Hungarian notation" un funkciju argumentos tika ieteikts ieviest const & ātrdarbības uzlabošanai.

Labs darbiņš, kas padarīts - kārtējais neticīgais pievērsts "pareizajai" ticībai ;)