ist std::set eine schlechte Wahl?

hustbaer schrieb:

Baut & läuft der Code unter Windoof?

Habe ich nicht probiert, aber ich würde erwarten, dass VS2015 das übersetzt, da es C++11 ist. Dann sollte es auch laufen.

Swordfish

Core 2 Quad 8300, VS 2015 Update 2, Win 10.0.10586.318:

Vector:
951433 Elemente in 159ms
911 Elemente eingefügt in 524ms
110 Elemente gefunden in 2ms

Vector mit bulk insert:
951433 Elemente in 158ms
911 Elemente eingefügt in 43ms
110 Elemente gefunden in 3ms

Set:
951433 Elemente in 1081ms
911 Elemente eingefügt in 3ms
110 Elemente gefunden in 3ms

Biolunar

Benchmarks \o/

Intel Core i5-4670 CPU @ 3.40GHz, clang 3.8
clang++ -std=c++14 -O3 -march=native

Vector: 
951464 Elemente in 79ms
896 Elemente eingefügt in 68ms
73 Elemente gefunden in 0ms

Vector mit bulk insert: 
951464 Elemente in 79ms
896 Elemente eingefügt in 42ms
73 Elemente gefunden in 0ms

Set:
951464 Elemente in 690ms
896 Elemente eingefügt in 0ms
73 Elemente gefunden in 0ms

hustbaer

VS 2015 U2
x64, Release, AVX2
Windows 10
Xeon E3-1245 v3 @ 3.4 GHz

Vector:
951433 Elemente in 102ms
911 Elemente eingef³gt in 73ms
110 Elemente gefunden in 1ms

Vector mit bulk insert:
951433 Elemente in 102ms
911 Elemente eingef³gt in 24ms
110 Elemente gefunden in 1ms

Set:
951433 Elemente in 750ms
911 Elemente eingef³gt in 1ms
110 Elemente gefunden in 1ms

Set mit initialem random bulk fill:
951433 Elemente in 735ms
911 Elemente eingef³gt in 1ms
110 Elemente gefunden in 1ms

Set mit initialem sorted bulk fill:
951433 Elemente in 175ms
911 Elemente eingef³gt in 1ms
110 Elemente gefunden in 2ms

kurze_frage

hustbaer schrieb:

kurze_frage schrieb:

und dann macht man ganz einfach usecases wo das set oder der vector besser ist, ganz wie man es mag oder jetzt eben braucht.

*facepalm*
Du solltest Politiker werden.
Und du solltest nachlesen was der Begriff "use case" bedeuete.

Nur weil ich beschreibe wie diverser Test Ergebnisse fabriziert werden ist doch kein Grund mich zu beleidigen und in die Nähe von Politiker anzusiedeln

anscheinend ist das set beim einfügen immer sehr viel schneller,
muss direkt probieren wie es ist wenn man sortiert einfügt, anstatt einfügen und am Schluss sortieren.
und wie es sich mit den selben input/such Daten verhält, damit man wirklich gleiches vergleicht.
dann könnte man noch versuchen festzustellen ob sich gewisse zahlen und such mengen positiv oder negativ auf den vector oder das set auswirken, usw.
Bevor ich das aber mach muss ich jetzt lernen gehen und nachsehen was use cases den wirklich sind, danke für den Hinweis!

Fazit: man sieht also, wofür die vielen Transistoren verwendet werden und dass es noch schwieriger wird, das Laufzeitverhalten vorherzusagen.

Wutz

kurze_frage schrieb:

anscheinend ist das set beim einfügen immer sehr viel schneller,

Quatsch.
Wie meistens bei Performanzbetrachtungen gilt: "kommt drauf an";
Anfänger sollten sind von Vermutungen und Verallgemeinerungen fernhalten (nicht nur bei solchen Performanzbetrachtungen).
- ein vector fügt neue Elemente immer unbedingt hinzu (es laufen praktisch nur Speicher(Schreib)-Operationen ab)
- ein set fügt neue Elemente immer bedingt hinzu (vor dem (evtl.) Hinzufügen laufen Prüfoperationen ab (lesend));
ein set ist nur dann "schneller" als ein vector, wenn das Prüfen häufig false liefert und somit das Hinzufügen ggü. vector "eingespart" werden kann;
ein set ist beim Einfügen somit also theoretisch langsamer als vector, keinesfalls aber "immer sehr viel schneller"

kurze_frage schrieb:

muss direkt probieren wie es ist wenn man sortiert einfügt, anstatt einfügen und am Schluss sortieren.

Löse dich mal von der ganzen Sortieren-Manie.
Wenn dein Anwendungsfall letztendlich nur darin besteht, das Vorhandensein eines Elements in einer (bereitstehenden) Liste festzustellen, brauchst du überhaupt nicht sortieren. Und dafür ist set ideal und unordered_set auch theoretisch ideal.
Je größer die Liste, desto besser ist unordered_set ggü. set ggü. vector:

http://ideone.com/2L6TAB

set nutzt intern Sortierung zur Unique-fizierung der Elemente, unordered_set Hashes.

kurze_frage

Wutz schrieb:

kurze_frage schrieb:

anscheinend ist das set beim einfügen immer sehr viel schneller,

Quatsch.
Wie meistens bei Performanzbetrachtungen gilt: "kommt drauf an";
Anfänger sollten sind von Vermutungen und Verallgemeinerungen fernhalten (nicht nur bei solchen Performanzbetrachtungen).
- ein vector fügt neue Elemente immer unbedingt hinzu (es laufen praktisch nur Speicher(Schreib)-Operationen ab)
- ein set fügt neue Elemente immer bedingt hinzu (vor dem (evtl.) Hinzufügen laufen Prüfoperationen ab (lesend));
ein set ist nur dann "schneller" als ein vector, wenn das Prüfen häufig false liefert und somit das Hinzufügen ggü. vector "eingespart" werden kann;
ein set ist beim Einfügen somit also theoretisch langsamer als vector, keinesfalls aber "immer sehr viel schneller"

kurze_frage schrieb:

muss direkt probieren wie es ist wenn man sortiert einfügt, anstatt einfügen und am Schluss sortieren.

Löse dich mal von der ganzen Sortieren-Manie.
Wenn dein Anwendungsfall letztendlich nur darin besteht, das Vorhandensein eines Elements in einer (bereitstehenden) Liste festzustellen, brauchst du überhaupt nicht sortieren. Und dafür ist set ideal und unordered_set auch theoretisch ideal.
Je größer die Liste, desto besser ist unordered_set ggü. set ggü. vector:

http://ideone.com/2L6TAB

set nutzt intern Sortierung zur Unique-fizierung der Elemente, unordered_set Hashes.

nur als ich von use case sprach wurde mir nahe gelegt Politiker zu werden.

hustbaer

Weil du es etwas eigen formuliert hast.
Klang so nach "wenn mir das Ergebnis nicht passt, dann re-definiere ich die Frage einfach so lange bis es passt".

Wutz

Politiker haben keine Ahnung von der Praxis, sie beziehen ihr "Wissen" aus Hörensagen.
Ein Stück weit kommst du dem nahe, wenn du aus deiner Beobachtung weniger Einzelfälle allgemeine Schlussfolgerungen ziehst (und damit dann womöglich noch hausieren gehst, und wiederum anderen Leuten etwas "erklären" willst).