Performance map vs set vs unordered_map

[Eisflamme]

Aber vector mappt doch nichts. Und ich verstehe noch nicht, wo der Vorteil darin ggü. der map liegt. Wenn ich eine Abbildung brauche, muss ich nun Mal eine Suche machen. Und in einer Map ist die doch zumindest binär, in einem vector linear, es sei denn ich schreibe mir irgend eine Suchfunktion, die ausnutzt, dass ein Teil des vector-Elements sortiert eingefügt wurde oder so.

map vs unordered_map verstehe ich. Aber ich verstehe noch nicht, wieso die map ggü. einem vector böse ist. Das sind für mich zwei paar Schuhe. Eine weitere Erklärung wäre super.

[Shade Of Mine]

Eisflamme schrieb:

Aber vector mappt doch nichts.

Du kannst ein pair in den vector packen - dann hast du mapping.

du kannst einne vector uebrigens auch sortieren und mittels lower_bound inserten und mittels binary_search look ups machen...

[seldon]

Dafür, ob eine Hashmap sinnvoller ist als ein binärer Baum, sind für mein Verständnis im Wesentlichen vier Faktoren von Bedeutung:

1. Wenn eine Sortierung notwendig ist, bringt eine Hashmap dich nicht weiter.

2. (Bezogen auf closed hashing) Wenn du vorher nicht abschätzen kannst, wie viele Einträge du verwalten musst, verliert die Hashmap dadurch etwas an Flair, dass sie alle Weile mal neu aufgebaut werden muss. Es ist eine Überlegung, die auch bei der Wahl zwischen std::deque und std::vector eine Rolle spielt.

3. Wenn Speicher knapp ist und die verwalteten Objekte ausreichend groß sind, kann auch das für einen Baum sprechen - eine Hashmap muss, um effektiv zu sein, immer einen gewissen Anteil (Pi * Daumen 20-30%) unbenutzten Speichers halten.

4. Alles steht und fällt mit der Hashfunktion. Wenn es über den erwarteten Schlüsselwertebereich schwierig ist, eine Hashfunktion zu finden, die selten kollidiert, ist eine Hashmap keine gute Wahl. Das betrifft beispielsweise Fälle, in denen die Schlüssel aus nicht vertrauenswürdigen Quellen stammen (DoS!). Generell ist das Ziel einer Hashfunktion, die Verteilungsstruktur der zu erwartenden Schlüssel in eine Gleichverteilung umzuwandeln. Ist das nicht möglich, verbietet sich Hashing.

Punkt 4 ist sehr wichtig aber auch schwierig und arbeitsaufwändig, weswegen er gern übersehen wird - häufig wird einfach ohne Prüfung angenommen, dass der Hash schon einigermaßen gleichverteilt sein wird, und gelegentlich handelt man sich auf die Art einen Haufen Ärger ein - ganz besonders, wenn man die Erwartung hat, dass Zugriffe auf eine Hashmap immer mit O(1) laufen sollten und nie echte Messungen vornimmt.

Es ist in der Praxis selten möglich, einen mathematischen Beweis über die Verteilung der Schlüssel zu führen, also muss Empirie herhalten: Wenn du eine Hashmap benutzt, nimm auch einen Profiler in die Hand und prüf anhand eines realistischen (am besten echten) Datasets nach, wie gut sie funktioniert.

Speziell für Strings gibt es übrigens andere Datenstrukturen, die effizientes Mapping vornehmen können. Hier scheint sich inzwischen die Idee des ternären Suchbaums durchgesetzt zu haben.

[Eisflamme]

Shade of Mine:
Okay, aber dann muss ich nach allen Einfügungen sortieren. Wenn ich zwischendurch immer Mal wieder was einfügen würde, würde sich der vector nicht anbieten, richtig?

Und zweite Frage: bei binary_search müsste ich dann aber ein Prädikat angeben, oder? Ich schätze, der nimmt nicht von selbst an, dass der erste Teil des Pairs als Schlüssel herhalten soll.

Und die Frage, was an einem solchen vector besser als an einer map ist, die automatisch das Key-Value-Verhältnis vorgibt und die Suche auch bereits integriert hat, ist mir auch noch nicht ganz beantwortet.

seldon:
Das klingt gut. In meinem Fall habe ich nur eine ziemlich kleine Datenmenge, auf die ich möglichst schnell zugreifen möchte. Das sind zwar strings, aber für den ternären Baum gibt es bisher keine Implementierung in boost etc., richtig?

Vielen Dank euch allen so weit!

[SeppJ]

Variante 1: Wenn du Zahlen aus einem Bereich von bis zu ein paar zig Millionen Einträgen auf irgendetwas mappen musst und du weißt, dass dieser Wertebereich nicht deutlich überschritten wird, dann kannst du einfach einen vector von eben einer Million Pointern auf die gemappten Objekte machen und den map-Zugriff als Zugriff auf diese Pointer gestalten. Konstante Zugriffszeit, dabei unschlagbar kleine Konstante. Minuspunkte: Du opferst dafür Wertebereich*Pointergröße Speicherplatz. In Zeiten von Gigagbytegroßen Hauptspeichern aber nicht so schlimm.

Variante 2: Wenn deine Mappingstruktur nur ein paar dutzend Einträge (mit billiger Vergleichsfunktion!) hat, kannst du auch alles in einem vector speichern. Mit linearer Suche kann der Zugriff schneller sein als bei einer map, die recht große Konstanten hat und erst einmal eine nicht zu kleine Zahl von Einträgen braucht, bevor die bessere Laufzeitkomplexität gegen die kleinen Konstanten des vectors gewinnt.

[CStoll]

Eisflamme schrieb:

Aber vector mappt doch nichts.

Doch, es mappt eine Zahl (den Index) auf einen Wert - d.h. wenn du mit ganzen Zahlen als Schlüssel zu tun hast (und darin nicht zu viele Lücken sind), kannst du in konstanter Zeit auf die zugeordneten Werte zugreifen.

PS: mit einem ternären Suchbaum hatte ich während der Studienzeit mal gearbeitet - der konnte durchaus mit Binärbäumen und Hash-Strukturen mithalten. Für kleine Datenmengen können die Geschwindigkeitsverhältnisse aber wieder ganz anders aussehen.

[Shade Of Mine]

Eisflamme schrieb:

Okay, aber dann muss ich nach allen Einfügungen sortieren. Wenn ich zwischendurch immer Mal wieder was einfügen würde, würde sich der vector nicht anbieten, richtig?

Du fuegst ueber std::lower_bound ein.
Das verschieben der Elemente beim Insert ist natuerlich uU teuer.

Und zweite Frage: bei binary_search müsste ich dann aber ein Prädikat angeben, oder? Ich schätze, der nimmt nicht von selbst an, dass der erste Teil des Pairs als Schlüssel herhalten soll.

Entweder ein predicate oder aber du nimmst nicht std::pair sondern eine eigene Klasse mit ueberladenen operator<

Und die Frage, was an einem solchen vector besser als an einer map ist, die automatisch das Key-Value-Verhältnis vorgibt und die Suche auch bereits integriert hat, ist mir auch noch nicht ganz beantwortet.

Eine map hat pro Knoten einen overhead - je nach implementierung sind das mehrere Zeiger. Weiters kostet das anlegen eines Knoten eine dynamische Speicherallokation.

Ein vector hat quasi keinen Speicher Overhead und ein einfuegen kostet keine Speicherallokation. Weiters ist ein vector deutlich cache lokaler - was zB ein lookup im vergleich zu einem baum schneller machen kann.

Er hat natuerlich auch viele Nachteile - keine Frage. Aber manchmal ist er die beste Wahl. Ich wuerde sagen, desto weniger Elemente du hast, desto besser ist vector. Ab einer gewissen Anzahl an Elementen ist vector in so einem Fall wohl unbrauchbar.

[seldon]

Eisflamme schrieb:

Das klingt gut. In meinem Fall habe ich nur eine ziemlich kleine Datenmenge, auf die ich möglichst schnell zugreifen möchte. Das sind zwar strings, aber für den ternären Baum gibt es bisher keine Implementierung in boost etc., richtig?

Es gibt in Boost.Spirit einen TST, der von boost::spirit::qi::symbols benutzt wird (per Default in Verbindung mit einer Hashmap). Siehe http://www.boost.org/doc/libs/1_46_1/libs/spirit/doc/html/spirit/qi/reference/string/symbols.html

Das ist zwar eigentlich zur Verwendung mit Spirit-Parsern gedacht, kann aber auch standalone benutzt werden.

[Eisflamme]

Okaaaay, das hilft mir schon Mal sehr viel weiter, aber leider ergeben sich für mich direkt ein ganzer Haufen weiterer Fragen.

SeppJ:
Okay, jetzt verstehe ich, wieso map überhaupt langsamer ist. Die Konstante ist größer, aber die Laufzeit nach O(x(N)) sollte gleich sein, oder?

Deine Variante 1 habe ich noch nicht ganz verstanden. Wieso brauche ich jetzt noch eine Map? Und wenn mein vector nur Zeiger auf "gemappte" Objekte hat, muss ich letztere ja auch noch irgendwo speichern. Aber ich glaube, ich verstehe hier etwas gänzlich falsch, kannst Du vll. 2-3 Zeilen Pseudocode schicken, das macht's glaube ich mit wenig Aufwand schnell verständlich.

CStoll:
Okay, das ist eine coole Idee.

Shade Of Mine:
Ahh, okay. Hast Du Lust noch kurz auszuführen, was es mit der Cache-Lokalität auf sich hat? Ich hab den Begriff Mal nachgeschlagen und im Bezug auf die normalen System-Caches auch verstanden, denke ich, aber wie drückt sich die bessere Cache-Lokalität hier denn aus?

seldon:
Sieht interessant aus, schaue ich mir sicher Mal an!

[SeppJ]

Eisflamme schrieb:

SeppJ:
Okay, jetzt verstehe ich, wieso map überhaupt langsamer ist. Die Konstante ist größer, aber die Laufzeit nach O(x(N)) sollte gleich sein, oder?

Im Vergleich zu was? Falls du einen vector tatsächlich linear durchsuchst (Variante 2) ist das O(N) beim Zugriff. Die map hat (O(log(N)) was besser ist. Da die Konstanten beim vector viel kleiner sind, kann das für kleine N aber besser sein.

Deine Variante 1 habe ich noch nicht ganz verstanden. Wieso brauche ich jetzt noch eine Map? Und wenn mein vector nur Zeiger auf "gemappte" Objekte hat, muss ich letztere ja auch noch irgendwo speichern. Aber ich glaube, ich verstehe hier etwas gänzlich falsch, kannst Du vll. 2-3 Zeilen Pseudocode schicken, das macht's glaube ich mit wenig Aufwand schnell verständlich.

Das ist genau das was CStoll dir auch erklärt hat. Die zusätzliche Indirektion über Pointer habe ich vorgeschlagen, weil ich annahm, dass deine Werte deutlich größer als ein einzelner Pointer sind. Falls dies nicht so ist, kannst du sie natürlich auch direkt speichern. Es geht nur darum, dass du bei einem großen Wertebereich genügend freien Speicher an einem Stück brauchst und eventuell bei komplex zu konstruierenden Wertobjekten auch unnötige Konstruktoraufrufe scheust.

edit: Bezüglich Cache-Lokalität: Es gibt da mehrere Effekte
- Bei einer Vectorstruktur (ohne Pointerindirektion) sparst du dir all die vielen Pointer in der map, die dann nicht mehr Platz im Cache verbrauchen.
- Bei einer map liegen die Pointer und Werte möglicherweise wild im Speicher verteilt. Bei vielen anderen Datenstrukturen liegen die nötigen Daten aber zusammen, daher holt der Cache bei einem Zugriff auf den Speicher schon einmal im Voraus die Werte in der Nähe, so dass der nächste Zugriff auf das nächste Objekt um so schneller geht.
- Beim Zugriff in einer map müssen viele Vergleiche gemacht werden. Das Ergebnis dieser Vergleiche ist auch sehr unvorhersehbar. Das ist ganz schlecht für moderne Prozessoren.

[Eisflamme]

Vielen Dank für die ausführliche Erklärung, das hat wieder etwas Licht in die Dunkelheit meines Unwissens gebracht.

[hnmmmmmmmmmm]

Wie sieht es mit set vs unordered_set aus?

[Marthog]

Es ist das gleiche, schließlich passiert auch das gleiche, man hat nur keinen Wert, also geringeren Overhead.

[hnmmmmmmmmmm]

Ich meinte, wann sollte man set und wann unordered_set einsetzen?

[Nathan]

Wie bei map:
set ist bei einer kleinen Anzahl schneller und sollte man verwenden wenn die Ordnung wichtig ist (logisch eig.), unordered_set bei größeren Anzahlen, weil die Konstante bei letzterem groß ist.

[out]

hnmmmmmmmmmm schrieb:

Ich meinte, wann sollte man set und wann unordered_set einsetzen?

Per default nimmst du immer std::set . Nur wenn du es schneller brauchst und den verdacht hast, std::unordered_set könnte schneller sein, nimmst du std::unordered_set ... natürlich ein paar Zeitmessungen durchführen. So hat es zumindest Stephan in einem seiner Videos erklärt.

[Wutz]

hnmmmmmmmmmm schrieb:

Ich meinte, wann sollte man set und wann unordered_set einsetzen?

Immer dann, wenn du auf die unsägliche Sortierung der keys verzichten kannst (also praktisch immer) verwende unordered_set.
Außerdem kannst du hierbei durch die optionale Angabe der Hashfunktion noch selbst optimieren, wenn du deine Daten besser kennst, als es die Default-Hashfunktion umzusetzen vermag.

[hnmmmmmmmmmm]

Ich habe folgende Situation:

set<tuple<int,int,int>> myset;
...
for (auto i = myvector.begin(); i != myvector.end()-2; ++i)
{
  if (myset.insert(make_tuple(*i, *(i+1), *(i+2))) == false)
    return false;
}

Ist hier unordered_set besser?

[out]

hnmmmmmmmmmm schrieb:

Ich habe folgende Situation:

set<tuple<int,int,int>> myset;
...
for (auto i = myvector.begin(); i != myvector.end()-2; ++i)
{
  if (myset.insert(make_tuple(*i, *(i+1), *(i+2))) == false)
    return false;
}

Ist hier unordered_set besser?

Compilerfehler

[gerüchteküche]

Nathan schrieb:

set ist bei einer kleinen Anzahl schneller [...] unordered_set bei größeren Anzahlen, weil die Konstante bei letzterem groß ist.

Das ist ein Gerücht. unordered_set ist immer besser (vorausgesetzt, die Ordnung ist egal), ausser die Hashfunktion ist Schrott.

@hnmmmmmmmmmm: Wenn du Lust hast, eine gute Hashfunktion zu schreiben ist unordered_set besser. Gut bedeutet aber nicht xor.