Warum würde die Karte viel schneller als unordered_map?

Implementiert habe ich eine Suche Zwischenspeicherung von Ergebnissen, die aus Schlüsseln bestehen von Art Zustand (a-Klasse mit 7 short ints), und Werte des Typs Socre (eine Klasse von 3 verdoppelt.) Mit unordered_map war mindestens 20 mal langsamer als eine Karte. Warum?

Edit: so ein Mist! Meine hash-Funktion wurde

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  //1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

Ich vergaß zu return retval, also es war alles kollidieren! Ich Wünsche unordered_map hatte hash_function_quality () - Funktion, die Berichte die Durchschnittliche Anzahl von Kollisionen.

Was ist Ihr Zugang Muster?
Welche Plattform/compiler?
intel i5, gcc, 6 hundert tausend Einsätzen und lookups
Verwenden Sie eine hash-Funktion mit unordered_map?
ja. würde es funktionieren, wenn ich nicht?
Für sechs-hundert-tausend-Einsätzen würde ich wahrscheinlich ein std::map noch. Es ist nur etwa 19 Operationen, um den Zugriff auf ein element. Jeder computer führt die 19-Operationen sehr schnell. Auch die prototypische Computer aus den 1950er Jahren.
Es war tatsächlich UB zu fallen das Ende eines Wert-Rückkehr-Funktion. Gcc hat eine Warnung für diese, -Wreturn-Typ, die in die Wand.
Der compiler nutze ich, gibt ein lautes Warnsignal, wenn eine Funktion nicht wieder etwas am Ende. Nicht deins?
Ich verwende cmake und ich denke, es ist verstecken Sie die Warnhinweise.
Genial. Sie herausgefunden, wie man cmake als IDE.

InformationsquelleAutor Neil G | 2011-01-31

c++map stl unordered-map

16

Die Geschwindigkeit der unordered_map ist direkt proportional zu der Geschwindigkeit der Hash-Funktion. Es ist nie einfach eine Beziehung. Case in point, wenn Sie sich für die einfachste Hash-Funktion:
```
std::size_t myHash(MyObjectType _object){ return 1; }
```
dann, was werden Sie am Ende mit ist eine Sammlung, die sich verhält wie eine Liste eher als eine Hash-container. Alle Elemente anzeigen, um eine einzelne Eimer und müssen Sie durchqueren den gesamten Eimer, bis Sie das Einzelteil, das Sie wünschen (etwas dauern könnte O(N) Zeit.)

Was Sie tun müssen, ist, sich auf zwei Dinge:
1. Was Hash-Funktion verwenden Sie? Kostet es eine lächerliche Menge an Zeit zu verarbeiten?
2. Wie viele Kollisionen wird es produziert? Das ist, wie viele verschiedene Elemente zugeordnet werden die gleichen hash-Wert?
Entweder von diesen selbst, kann und wird töten die Leistung.
- Dies ist die Antwort, die hat mich eines besseren belehrt, was könnte schief gehen, so Sie es annehmen.
InformationsquelleAutor wheaties
9

std::unordered_map ist allgemein langsam, für eine kleine Anzahl von Elementen, da die hash-Funktion. Es wird eine Feste (-ish) Höhe der Zeit, aber vielleicht eine erhebliche Menge an Zeit dennoch.

std::map auf der anderen Seite einfacher ist, als std::unordered_map. Die Zeit, die es braucht, Zugriff auf ein element, es hängt von der Anzahl der Elemente, aber weniger als die Anzahl der Elemente wächst. Und die groß-oh-Faktor c für eine std::map ist allgemein sehr klein, im Vergleich zu std::unordered_map.

Im Allgemeinen lieber mit std::map über std::unordered_map, es sei denn, Sie haben einen besonderen Grund zur Benutzung std::unordered_map. Dies gilt insbesondere, wenn Sie nicht über eine große Anzahl von Elementen.
- Schwer zu glauben, dass eine hash-Funktion nehmen würde, 20x länger als transversing a binary tree.
- Die OP ist, sofern keine Einzelheiten von jeder Art auf, die. Nicht nur könnte die hash-Funktion länger als erwartet dauern, naiv hash-Funktionen generieren können viele Kollisionen.
- Ich glaube nicht, Folgen Sie "keine Angaben jeder Art aus." Uns fehlt der Zugang patern, wahr. Kaufen vorausgesetzt typische Kollisionen, 20x macht keinen Sinn.
- warten Sie, OP zu sagen 600k fügt, dann 600k-Lookups, was Sie tun müssen?
- Vielen Dank für diese Beratung. Ich werde auf jeden Fall halten Sie im Verstand für die nächste Zeit.
- Vor dem Bearbeiten, alle wussten wir um die hash-Funktion ist, dass es operiert auf einem Objekt mit 7 shorts. Nicht wörtlich, "keine details, die von jeder Art", aber es könnte genauso gut gewesen. In der Tat, es war scheinbar genau die Kollisionen habe ich erwähnt, dass das problem verursacht.
- sorry, ich habe einige Informationen unten in den Kommentaren die Frage.
- Ich finde diese Antwort ein wenig irreführend. Man sollte eher vergleichen einen Baum, um eine hash-Tabelle, und es ist jeweiligen Einsatz-Szenarien, wie sortiert traversal vs unsortiert, Einfügung und Abbau-Zeiten. Und dann gibt es auch compiler-abhängig Optimierungen, z.B. einige Compiler behandeln unordered_set als einen Vektor, so lange, wie Ihre Schlüssel sind in einem Bereich von 0..50k.
InformationsquelleAutor wilhelmtell
8

unordered_map verwendet eine hash-Tabelle unter der Haube, so dass die meisten offensichtlichen Grund, warum hash-schlecht ist, weil Sie zu viele Kollisionen. Können Sie erwägen, verschiedene, nicht-Standard -, hash-Funktion, die geben bessere Ergebnisse für Ihre Art des keys.
- ja, Sie hatten Recht. +1
InformationsquelleAutor Alexei Polkhanov
0

Für

Wünsche ich unordered_map hatte
hash_function_quality () - Funktion,
Berichte, die Durchschnittliche Anzahl der
- Kollisionen.

Ich denke, dass die folgende Funktion hilfreich sein könnten.
```
unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.
```
Niedriger die load_factor besser ist die hash-Funktion.
- Ich schaute auf die load_factor, aber das problem ist nicht E[Elemente] in den Eimer, aber E[Elemente^2].
InformationsquelleAutor Arun

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.