Frage zu std::unordered_set

[Wutz]

Nimm die unordered_map, mit dem eindeutigen string als key und der Klasse als value, wobei hier das string-Element natürlich redundant ist und du Speicher sparen kannst, wenn du es hier einfach weglässt.
Zunächst kannst du erstmal die von deinem Compiler eingebaute string-Hashfunktion nehmen und wenn du einen repräsentativen Datenbestand simulieren kannst, kannst du immer noch eigene Hash-Funktionen ausprobieren, ob sie denn schneller arbeiten.
Das Suchen nach anderen Kriterien als dem String in deiner großen Map wird dann allerdings langsam sein und sollte auf Ausnahmefälle beschränkt bleiben.

[Eisflamme]

Nimm die unordered_map, mit dem eindeutigen string als key und der Klasse als value, wobei hier das string-Element natürlich redundant ist und du Speicher sparen kannst, wenn du es hier einfach weglässt.

Sehr böse. Redundanz kann alle möglichen "Anomalien" begünstigen und den String aus der Klasse zu nehmen, um Speicher zu sparen um diese "Anomalien" (keine DB, aber der Begriff passt hier trotzdem, finde ich) zu vermeiden verstümmelt die Klasse auf Grund der Einsatzmethode, das kann man doch nicht empfehlen.

Ich fände std::inordered_set okay, dann ist der Hash eben nur vom string abhängig und gut. Leider sind Sets ... "ungeschickt" implementiert und man kann nicht so einfach Werte ändern, selbst wenn diese die Ordnung nicht ändern, das ist bei unordered_set auch so. Wenn sich eh nichts ändern, sondern nur löschen oder einfügen lassen soll, ist das natürlich egal.

Wonach soll sonst gesucht werden? boost::multiindex legt auch Hierarchien an, man kann aber eben mehrere Indizes anlegen und hat die Probleme mit der Set-Unlogik nicht.

[bobo7788]

Ja, Redundanzen will ich natürlich vermeiden.

Bei einem unordered_set habe ich natürlich das Problem, dass ich nicht genau nach einen Key vom Typ std::string suchen kann.

Die Objekte A innerhalb von dem set haben zwar den std::string als Member, aber der Aufruf set.find() erwartet natürlich ein Objekt A und kein std::string.

[Eisflamme]

Du kannst doch eigene Vergleichsoperatoren für das Set definieren. Oder für die Klasse selbst eben, wenn das eben das Haupt-Vergleichskriterium ist.

[nwp3]

Was spricht denn gegen ein normales set? Da gibt es keinen Overhead wegen doppelten Strings oder Hashfunktionen.

struct A{
    std::string name;
    //anderer Kram
};

std::set<A, [](const A &a1, const A &a2){return a1.name < a2.name;}> Aset;

//noch eine Hilfsfunktion dazu:
const A *findObject(const std::string &s){
    static A a; //dummy A zum Suchen
    a.name = s;
    auto it = Aset.find(a);
    if (it == Aset.end()) //das kann man sicher noch hübscher machen, vielleicht einfach den Iterator zurück geben
        return 0;         //oder den Dummy oder den entsprechenden Wert ins set einfügen und eine Referenz darauf zurück geben
    return &(*it);
}

Dann noch eine Changefunktion bauen, die bei Ändern von A::name das Element aus dem Set entfernt, den Namen ändert und wieder hinzufügt und ansonsten per const_cast direkt ändert.

[bobo7788]

Eisflamme schrieb:

Du kannst doch eigene Vergleichsoperatoren für das Set definieren. Oder für die Klasse selbst eben, wenn das eben das Haupt-Vergleichskriterium ist.

Richtig. Ich kann aber nicht nach dem Objekt meiner Wahl mit set.find("MyKey") suchen. Ich muss mit set.find(MyObject) suchen.

[intrusive]

http://www.boost.org/libs/intrusive/

[bobo7788]

nwp3 schrieb:

Was spricht denn gegen ein normales set?

Eigentlich nicht viel.

Ich habe es jetzt tatsächlich mit einem std::set realisiert und verwende einfach ein static Objekt, dem ich den key zuweise.

Die Laufzeit bei vielen Elementen (>100000) ist mit set.find einfach deutlich besser, als mit std::find_if.

Es ist sogar noch besser, als bei einer std::map mit direktem Indexzugriff mymap[key]. Das hat mich erstaunt. Beide liegen aber im selben Bereich, die Abweichung betrifft nur die Zahl hinter dem Komma.

=> Die Laufzeit ist ja bei beiden O(logn)

[SeppJ]

bobo7788 schrieb:

Es ist sogar noch besser, als bei einer std::map mit direktem Indexzugriff mymap[key]. Das hat mich erstaunt. Beide liegen aber im selben Bereich, die Abweichung betrifft nur die Zahl hinter dem Komma.

=> Die Laufzeit ist ja bei beiden O(logn)

Das ist sicherlich nur eine Messschwankung. map sollte (wenn die Macher einigermaßen faul waren) als ein set<pair<key, value>> mit passender Vergleichsfunktion und den map-Methoden implementiert sein.

[nwp3]

bobo7788 schrieb:

Ich habe es jetzt tatsächlich mit einem std::set realisiert und verwende einfach ein static Objekt, dem ich den key zuweise.

Bin mir noch unsicher, ob ich mich freuen oder ärgern soll, dass du dasselbe erfunden hast was ich gepostet hatte. Ich sag einfach mal "Great minds think alike" und freue mich

[bobo7788]

SeppJ schrieb:

bobo7788 schrieb:

Es ist sogar noch besser, als bei einer std::map mit direktem Indexzugriff mymap[key]. Das hat mich erstaunt. Beide liegen aber im selben Bereich, die Abweichung betrifft nur die Zahl hinter dem Komma.

=> Die Laufzeit ist ja bei beiden O(logn)

Das ist sicherlich nur eine Messschwankung. map sollte (wenn die Macher einigermaßen faul waren) als ein set<pair<key, value>> mit passender Vergleichsfunktion und den map-Methoden implementiert sein.

Die Schwankung scheint aber regelmäßig zu sein. Bei 500000 Elementen habe ich im Release mit std::find_if eine Zeit von 0.00465415, mit set.find 1.20115e-006 und mit map[key] einer Zeit von 4.20402e-006.

map uns set sind praktisch gleichauf, aber dennoch schneidet set immer ein klitzewenig besser ab.

[SeppJ]

Ist 10^-6 Sekunden überhaupt noch innerhalb der Auflösung des Timers? Eventuell misst du hier die kleine if-Abfrage, die bei der map bei nicht-finden ein neues Element anlegt, wohingegen set dann einfach end() liefert. Versuch doch mal das find von der map anstatt operator[].

P.S.: Das heißt, deine set- und map-Codes sind nicht äquivalent, falls ein Element nicht vorhanden sein sollte. Ich nehme an, das hast du schon bedacht, oder?

[Eisflamme]

Die Laufzeit bei vielen Elementen (>100000) ist mit set.find einfach deutlich besser, als mit std::find_if.

Ja ach, find_if ist ja eine lineare Suche. Vergleich's mit std::binary_search (Sortierung natürlich vorausgesetzt).

Set ist schon echt okay, wenn man nichts ändern will.

[bobo7788]

SeppJ schrieb:

Ist 10^-6 Sekunden überhaupt noch innerhalb der Auflösung des Timers? Eventuell misst du hier die kleine if-Abfrage, die bei der map bei nicht-finden ein neues Element anlegt, wohingegen set dann einfach end() liefert. Versuch doch mal das find von der map anstatt operator[].

P.S.: Das heißt, deine set- und map-Codes sind nicht äquivalent, falls ein Element nicht vorhanden sein sollte. Ich nehme an, das hast du schon bedacht, oder?

Jup, das hatte ich berücksichtigt. Die Messung habe ich mit dem QueryPerformanceCounter durchgeführt.

Aber wie gesagt, sowohl set, als auch map haben O(logn) und liegen praktisch gleichauf. Man merkt bei std::find_if deutlich O(n).

[krümelkacker]

nwp3 schrieb:

std::set<A, [](const A &a1, const A &a2){return a1.name < a2.name;}> Aset;

Das müsstest Du nochmal üben. std::set will als zweiten Templateparameter auch einen Typen haben, kein "Lambda-Objekt".

Eisflamme schrieb:

Vergleich's mit std::binary_search (Sortierung natürlich vorausgesetzt).

wobei binary_search einem nur sagt, ob das Element vorhanden ist oder nicht. Was er will ist std::lower_bound -- wenn ich mich da richtig erinnere. Habe jetzt nicht nochmal extra nachgeguckt.

Bleibt vielleicht noch zu sagen, dass bei std::set und std::map die Laufzeit auch im schlechtesten Fall O(log(n)) ist, wohingegen die Laufzeit bei std::unordered_* im Durchschnitt O(1) und im schlechtesten Fall O(n) ist, je nachdem, wie viele Hash-Kollisionen es gibt.

[Sone]

"Lambda-Objekt"

closure-object. Allerdings ist die Idee nicht falsch - einfach den closure-type übergeben. Und dann muss noch eine Kopie des closure-objects an den Konstruktor von set übergeben werden, denn der default-Konstruktor ist deleted .

auto cap_obj = [](int a, int b){ return a < b; };
	std::set<int, decltype(cap_obj)> set{cap_obj};

[krümelkacker]

Sone schrieb:

"Lambda-Objekt"

capture-object.

Wenn du es genau haben willst, also Standardsprech, dann heißt das closure object, siehe §5.1.2/2. Ich habe aber bewusst "Lambda-Objekt" gesagt und mit Anführungszeichen umschlossen.

Sone schrieb:

capture-type

Du meinst closure type.

[Sone]

Ich hab mich völlig verdaddelt.* Natürlich closure. Ich habe gerade nur schon wieder etwas für das lambda-capture nach gesehen, und die Worte sind recht ähnlich.... Das ist mir peinlich.

*Passiert mir öfter.