[C++] vraag over snelheid STD::Map

[Laurens-R]

Hallo allemaal,

Ik ben recent begonnen met het (serieus) programmeren in C++. Ik ben bezig met een Direct3D applicatie, vanwege eductieve overwegingen.

Mijn vraag is: hoe snel is het krijgen van een memory pointer naar een object uit std::map met behulp van een key t.o.v. het doorzoeken van een std::list object.

De tijd die het kost om een object in te laden in de map is niet belangrijk.. het gaat er alleen om dat ik een object snel kan terugvinden en uitlezen tijdens het render deel in de 'game' loop.

Zelf denk ik dat het sneller is, dan m.b.v. een iterator door elk element van een list door te lopen, omdat je met behulp van je key direct aankomt bij de juiste pointer. Ik heb echter niet genoeg ervaring om dit zeker te weten.

[Icelus]

IIRC: std::map is een binaire boom. Toegang tot elementen is gelijk aan O(log(n)).
Opvragen gaat (veel) sneller dan met een iterator door een std::list lopen.

[ Voor 31% gewijzigd door Icelus op 23-03-2007 14:21 ]

[Laurens-R]

Ok, veel dank. Dan weet ik dat ik op de juiste weg zit

[Parody]

@Icelus: klopt, voor de standaard std::map. Lists doorzoeken is O(n).

Op veel systemen is er ook nog zoiets als een "hash_map" (naam uit m'n hoofd). Die heeft theoretisch O(1) toegangstijd, mits je hashfunctie goed genoeg is om geen bergen collisions te veroorzaken, maar eet wel wat meer geheugen weg (optimisatie snelheid versus geheugengebruik). Met een hoop collisions zou dit echter wel op kunnen lopen naar O(n). En je moet er natuurlijk voor zorgen dat je geen al te dure hash-functie verzint...

[Laurens-R]

@Parody: Weer wat geleerd. Ik heb eigenlijk alleen in C# met hashmaps gewerkt en aangezien de manier waarop je het gebruikt dicht bij de std::map ligt, dacht ik dat deze min of meer hetzelfde waren (beginnersfout )

Ik zal me eens gaan verdiepen in hashmaps met het oog op de criteria die je aangaf.

[ Voor 4% gewijzigd door Laurens-R op 23-03-2007 14:35 ]

[Marcj]

Als je wat over efficiente hashfuncties wil weten moet je ook deze pagina even doorlezen. Maar er zijn altijd efficientere hashfuncties zelf te bedenken als je goede aannames kan maken over je data die je hebt.

[Soultaker]

Het verschil tussen een (momenteel niet-standaard) hashmap een gewone map is trouwens lang niet zo groot als het verschil tussen een map en een list. Als ik jou was zou ik dus gewoon een map gebruiken.

[Verwijderd]

Gebruik een std::map, die zijn snel zat. Als blijkt dat de performance van je programma bagger is, kan je hem altijd nog vervangen door een hash_map. Maar ik zou me over de performance voorlopig nog niet druk maken.

[Laurens-R]

Allen dank, ik blijf voorlopig nog even bij m'n map.

Ik vind de map zowieso al prettig werken; de broncode blijft er lekker 'schoon' door