Unordered map und ordered map



  • Hallo zusammen,

    ich hätte ein kurze Frage zu den zwei verschiedenen maps und zwar gehts um Zugriffszeiten. Bislang hab ich alles in Vektoren gespeichert, wobei sich - meiner Meinung nach - eine Hashtable besser für mein Vorhaben eignet. Grund hierfür ist die fehlende Suche nach der ID. Bspw. habe ich die Atommassen der Elemente (im PSE) in einem Vektor abgespeichert und gleichzeitig die Elemente selbst in einem anderen. Bei einem Zugriff auf die Atommasse muss ich zuerst die ID des Elements suchen, um dann im zweiten Vektor die Masse zu erhalten. Via Hashtable ist das ja wesentlich einfacher, unkomplizierter und alles in einer Table gespeichert. Hier wäre mein zu verwendender Typ <string, double>. Eine zweite Hashtable wäre bspw., die, die alle chemischen Spezies enthält und zu jeder Spezies ein Satz von Polynomkoeffizienten hat (14 Stck an der Zahl). Bislang hab ich das auch so gelöst, dass ich zwei Vektoren verwendet habe. Hier würde ich dann eine Hashtable vom Typ <string, vector<double> > verwenden.

    Jetzt zur eigentlichen Frage, was schneller und besser ist. Ich denke die Hashtable sollte ich der Variante mit den zwei Vektorarrays vorziehen, oder? Wenn ja, wäre die nächste Frage, welche Table besser geeignet wäre. Die Größe der zweiten Hashtable ist sicher < 800 Einträge, jedoch habe ich einen Vektor als zweiten Typen. Eine wichtige Information ist, dass die Tables initialisiert werden und danach nur noch darauf zugegriffen werden und das sehr oft. Ich denke pro Iteration mehrere tausend mal.

    Laut meiner Recherche wäre es in meinem Fall dann geschickter die unordered map zu verwenden, da diese eine Operation benötigt O(1) (access/insert) und die ordered logarithmisch ist O(ln(n)). Könnt ihr mir das bestätigen oder wäre eine andere Lösung besser?

    Grüße Tobi



  • Bei <800 Einträgen ist eigentlich alles egal.

    Bei kurzen Strings ist es möglicherweise auch am schnellsten, den Vector zu sortieren und dann mit lower_bound nach dem String suchen.



  • Danke für die Antwort (:



  • Bei kurzen Strings müsste aber auch eine Hashtable ziemlich schnell sein. Einen langen string zu hashen kann etwas teurer sein. Wenn die Strings lang sind, ist die Suche in einer map oder einem sortierten Vector vielleicht schneller, bei kurzen Strings fällt aber der Nachteil des Hashens weniger ins Gewicht.
    Das müsstest du doch schnell ausprobieren können? Dann weißt du, was für deinen Anwendungsfall optimal ist.



  • Zu dem Thema kann ich folgenden Beitrag von Chandler Carruth wärmstens empfehlen:
    https://isocpp.org/blog/2015/07/cppcon-2014-efficiency-with-algorithms-performance-with-data-structures-cha



  • theta schrieb:

    Zu dem Thema kann ich folgenden Beitrag von Chandler Carruth wärmstens empfehlen:
    https://isocpp.org/blog/2015/07/cppcon-2014-efficiency-with-algorithms-performance-with-data-structures-cha

    ... der aber leider bezüglich map / unordered_map ein wenig enüchternd ist, weil er im Prinzip sagt, dass wenn man dort wirklich maximale Performance benötigt, beide Maps eine Katastrophe sind und man besser eine selbst zusammengebaute Datenstruktur verwenden sollte (sortiertes Array/ vector oder eine Hashtabelle mit offener Adressierung). Das erklärt allerdings auch, weshalb z.B. in der Spieleentlichklung oft ein Bogen um die Standardbibliothek gemacht wird, bzw. diese auf kritischen Codepfaden nur eingeschränkt eingesetzt wird. Es wäre schön wenn man in der Standardbibliothek je nach Anwendungsfall noch ein paar zusätzliche assoziative Container zur Verfügung hätte. Nicht jeder braucht z.B. bei der unordered_map einen Interator über die Elemente eines Hashtabellen-Buckets (einer der Gründe, weshalb unordered_map nur sehr schwer etwas CPU-Cache-freundlicher zu implementieren ist).

    Finnegan



  • Finnegan schrieb:

    ...

    Schön zusammengefasst - danke.



  • Naja, die Zusammenfassugn wäre eher:
    - Effeziente Algorithmen bauen, die wirklich nur das machen, was sie sollen und nicht noch mehr
    - per API die Möglichkeit geben eben genau sowas einzustellen, dass eben nichts unnötiges berechnet/gemacht wird
    - CPU-Cache ausnutzen
    - CPU-Cache freundliche Datenstrukturen bevorzugen
    - CPU-Cache nutzen
    - Architektur und Ziel-CPU genau kennen



  • 👍



  • Man sollte besser mal einen Beitrag empfehlen, der erklärt wie man der Grund von Performanceproblemen findet, anstatt sinnlos irgendwo rumzuoptimieren. Vielleicht wär das mal ein Anfang: The First and Only Rule of IBO: You are wrong.


Log in to reply