std::map vs. std::tr1::unordered_map



  • Hallo,

    ich benötige eine Datenstruktur, bei der ein Ganzzahl Key auf ein Element zeigt - bisher habe ich das als std::map implementiert.
    Wenn ich das aber richtig verstanden habe, ist der Aufwand für Abfrage und Abspeicherung eines Elementes logarithmisch,
    da map intern auf einem Baum arbeitet.

    Haben folgende Anweisungen dann wirklich logarithmischen Aufwand?

    std::map<int, float> myMap;
    
    myMap[0] = 1.0;
    myMap[1] = 1.1;
    
    float f = myMap[0];
    

    Die unordered_map aus TR1 scheint diese Anweisungen ja im Optimalfall in O(1) durch Hashing erledigen zu können.
    Ganz naiv habe ich also den Code folgendermaßen verändert:

    std::tr1::unordered_map<int, float> myMap;
    
    myMap[0] = 1.0;
    myMap[1] = 1.1;
    
    float f = myMap[0];
    

    Durch diese triviale Änderung hatte ich mir einen kleinen Geschwindigkeitschub erhofft, da ich map intensiv benutze.
    Da die fps sich aber kein bißchen verändert haben, nehme ich an, dass ich irgendetwas nicht berücksichtigt habe.
    Ich sollte vielleicht noch erwähnen, dass der Integer Key eindeutig ist.

    Kann mir vielleicht jemand weiterhelfen?



  • Zwischen logarithmischen und konstanten Zugriffen gibt es erst bei einigen X-hundert bis -tausend Einträgen merkliche Unterschiede (beachte, daß log2(1024) gerade mal 10 ist).
    Und selbst beim Hashing gibt es je nach Kollisionstyp (open or closed) ebenfalls einigen Overhead.

    Wie viele Einträge hast du denn in der Map?



  • Die Map kann theoretisch 512^3 ( = 132.417.728) Einträge beinhalten. Im Normalfall sollte die Anzahl allerdings 1-2 Millionen betragen.
    Da ich teilweise pro frame auch etwa 1000 mal darauf zugreife, hatte ich mir doch einen merkbaren Unterschied versprochen.

    Die Frage war auch dahingehend gerichtet, ob meine Benutzung der unordered_map vielleicht einfach falsch ist.


  • Mod

    Spricht etwas gegen vector<float> ?



  • Ja, und zwar muss ich die Elemente direkt ansprechen können und muss auch wissen, ob sie schon enthalten sind.
    Beides wäre mit einem Vector ziemlich aufwändig...



  • Was du eventuell tun könntest, wäre genau zu messen, wo am meisten Zeit benötigt wird. Auf diese Weise kannst du meist spezifischer optimieren. Dazu reichen eigentlich Zeitmessungsfunktionen (betriebssystemspezifisch), oder du nimmst gleich einen Profiler (z.B. AMD CodeAnalyst).

    Welche Operationen benötigst du denn am meisten (Einfügen, Suchen, ...)? Macht es viel aus, wenn du beim Lesezugriff find() statt operator[] verwendest?


Log in to reply