ist std::set eine schlechte Wahl?



  • vielen Dank. Dann kann ich ja beruhigt sein. Groß wird die Liste nicht (max. 40 Einträge). Ich denke von der performance nimmt sich das alles nicht so viel. Zumal der zugriff auf die Liste eher selten passiert.

    vielen Dank 😃



  • SBond schrieb:

    So gesehen befülle ich die Liste beim Programmstart und prüfe hin und wieder, ob sich eine bestimmte Kennung in der Liste befindet.

    Der vermutlich effizientere Container für dieses vorhaben dürfte ein sortierter std::vector sein. Da du nur einmal am Anfang Werte einfügst, musst du nur einmal sortieren und finden von Elementen geht in O(log N) Schritten mit binärer Suche (genau wie bei std::set , aber vermutlich schneller da im vector alles zusammenhängend gespeichert ist). Den std::unordered_set kann man ja auch mal testen. Bei nur 40 Elementen und wenigen Tests sollte die Performance nicht so eine wichtige Rolle spielen.


  • Mod

    SBond schrieb:

    Groß wird die Liste nicht (max. 40 Einträge). Ich denke von der performance nimmt sich das alles nicht so viel. Zumal der zugriff auf die Liste eher selten passiert.

    Je kleiner die Datenmenge, desto eher ist eigentlich vector die bessere Wahl. set ist ja gerade dazu gut, dass es große Datenmengen clever organisiert, so dass man sich unnötige Zugriffe spart, zum Preis gewisser Mehrkosten pro Zugriff.

    Beachte aber auch das was sebi707 gesagt hat.



  • ok 🙂

    dann bleibe ich wohl doch beim guten alten std::vector 🙂



  • Der Vector ist immer die erste Wahl. List die schlechteste. Und alles andere (Set, Map usw.), wenn Vector offensichtlich doch Ärger macht.



  • Ist die Liste compilezeitkonstant?



  • manni66 schrieb:

    Die verzeigerten Container wurden entworfen, weil sie theoretisch schneller sind. Mit den heutigen Prozessoren mit mehereren Cacheebenen ist das aber in der Praxis häufig nicht der Fall.

    So ein Stuss...

    Kennst du überhaupt den Unterschied zwischen O(n*log(n)) und O(log(n))?

    Probiere mal folgendes aus:
    1.) Initialisiere einen Container mit 1.000.000 Elementen
    2.) for i = 0; i < 1000; i++ do
    3.) Füge Zufallszahl sortiert in Liste ein
    4.) Suche Zufallszahl X und gebe das Ergebnis aus
    5.) end for

    Nimm am Anfang den std::set Container und wähle das Ende der for Schleife so, dass das Programm 5 Sekunden benötigt. Wenn du nun den Container gegen einen std::vector austauscht, wird sich das Program spürbar verlangsamen.



  • 1. 90/10 Regel .... Du hasst also ne chance von 90%, das Dein Code nur unerheblich Auswirkung auf die gesamtperformance hat.
    Also wenn dir unsicher bist, welcher container, mach lieber nen "verständliches" interface drum und entscheide dich nach bauchgefühl.
    Dann mess die GesamtPerformance ... wenn unzureichend, analysieren und wenn dann doch auf den container stößt ... bist wenigstens vorbererietet ^^

    2.

    in den ich einige Kennungen speichere

    Wie der container seine daten anordnet etc ... ist zwar schon wichtig, verblasst aber auch gegenüber der performance der vergleichsoperation ...
    Wenn in der situation bist, wo der container nen problem ist, würd ich auch überlegen, ob die kennungen nicht hashen solltest

    Ciao ...



  • Bitte ein Bit schrieb:

    manni66 schrieb:

    Die verzeigerten Container wurden entworfen, weil sie theoretisch schneller sind. Mit den heutigen Prozessoren mit mehereren Cacheebenen ist das aber in der Praxis häufig nicht der Fall.

    So ein Stuss...

    Kennst du überhaupt den Unterschied zwischen O(n*log(n)) und O(log(n))?

    Wenn du manni66s Satz nochmal liest, sollte dir auffallen, dass er auf eine Diskrepanz zwischen Theorie und Praxis hinweist.
    In der Theorie sind alle Speicherzugriffe gleich schnell, so dass man auf die Idee kommen könnte, dass sich eine map oder ein set im Vergleich zu einem stupide durchsuchten vector ab einem n von etwa 10 lohnen könnte.
    In der Praxis ist die Geschwindigkeit jedoch von der Art und Wiese abhängig, wie ein Algorithmus auf den Speicher zugreift (CPU-Cache), und diesbezüglich stehen map und set nicht sonderlich gut da, so dass das n , ab welchem map und set einen Geschwindigkeitsvorteil bringen, locker 2 bis 3 Größenordnungen höher liegt als man erwarten würde. Meiner Erfahrung nach hat man es, wenn man eine Dictionary-Datenstruktur benötigt, meistens mit einer Anzahl von Elementen zu tun, bei der wahrscheinlich ein dummer vector schneller ist. Für dein Beispiel mit den 1M Elementen dominiert natürlich aller Wahrscheinlichkeit nach die theoretische Überlegenheit von map und set .



  • std::set ist sehr oft eine gute Wahl.

    Wenn ich einen Container brauche, wo ein Element nur ein mal vorkommen darf, bzw. soll und ich darin suchen will, dann stellt std::set ein verständliches Interface zur Verfügung. Und das ist zunächst mal das Hauptkriterium.

    Verwende ich einen std::vector für den Anwendungsfall, muss ich mich selbst darum kümmern, die Elemente eindeutig zu machen und auch die Suche ist komplizierter. Nicht wirklich kompliziert, aber wie auch immer ich es mache ist es schwieriger lesbar, als bei einem std::set.

    Wenn ich mir Gedanken um die Performance mache, dann sollte ich zunächst die Frage stellen, ob die Verwendung des Containers für die Gesamtperformance meines Programmes von Bedeutung ist. Benötige ich genau an dieser Stelle eine exzellente Performance? Ist der Zugriff auf den Container Relevant? Dabei ist zu berücksichtigen, dass ein std::set sehr schnell ist.

    Wenn ich zu dem Ergebnis komme, dass der Container einen Engpass darstellen könnte, dann kann ich mir Gedanken machen, ob std::vector hier schneller wäre. Ein std::vector hat von der Performance den Vorteil, dass die Elemente hintereinander im Speicher stehen. Das wird beim std::string allerdings ein wenig abgeschwächt, da er die Daten ja über einen Zeiger indirekt verwaltet (short-string Optimierung mal ausgeklammert).

    Auch muss ich mir Gedanken machen, ob nicht der Stringvergleich beim Suchen deutlich mehr Performance benötigt, als die eigentliche Suche.

    Bei der linearen Suche in einem std::vector habe ich potentiell mehr Stringvergleiche, als bei einem std::vector. Oder ich halte die Elemente im std::vector immer sortiert. Dann muss ich mich wiederum fragen, wie viel Performance die Sortierung benötigt.

    Du siehst also, dass die Antwort viel komplizierter ist. Kurz gesagt, nimm einfach std::set, es sei denn, Du hast gute Gründe, etwas anderes zu nehmen.



  • Bitte ein Bit schrieb:

    manni66 schrieb:

    Die verzeigerten Container wurden entworfen, weil sie theoretisch schneller sind. Mit den heutigen Prozessoren mit mehereren Cacheebenen ist das aber in der Praxis häufig nicht der Fall.

    So ein Stuss...

    Ja?

    Kennst du überhaupt den Unterschied zwischen O(n*log(n)) und O(log(n))?

    Ja, und ich weiß sogar, dass dort eine Konstante c enthalten ist.

    Probiere mal folgendes aus:
    1.) Initialisiere einen Container mit 1.000.000 Elementen
    2.) for i = 0; i < 1000; i++ do
    3.) Füge Zufallszahl sortiert in Liste ein
    4.) Suche Zufallszahl X und gebe das Ergebnis aus
    5.) end for

    Nimm am Anfang den std::set Container und wähle das Ende der for Schleife so, dass das Programm 5 Sekunden benötigt. Wenn du nun den Container gegen einen std::vector austauscht, wird sich das Program spürbar verlangsamen.

    Wenn man das auf aktuellen CPUs misst (Bjarne Stroustrup hat dies z.B. getan), kommt man zu dem überraschenden Ergebnis, das auch bei großem n der vector das set schlägt. Die Erklärung: da beim set durch die Verzeigerung wild im Speicher herum gesprungen wird, muss die CPU auf den langsamen Speicher warten. Währenddessen kann der vector locker n Elemente im Cache verschieben.



  • Ja, möglicherweise ist es wirklich mal ein Anwendungsfall. Habe mit std::set noch nicht gearbeitet. Ich werde es einfach mal testen 😃



  • @manni66:
    Ich habe es mal getestet so wie es da steht. Ergebnis unter VS2012, Release Version

    Zeit bei std::vector : 16797ms
    Zeit bei std::set : 0ms

    Was soll auch ein Cache machen? Er beschleunigt im Best Case den std::vector Alg. um einen Faktor von 1000. Das dürfte ungefähr der Unterschied Zugriffsgeschwindigkeit L-Cache und Arbeitsspeicher sein. Und dieser Faktor ist konstant! Und je größer die Eingabe wird, desto weniger spielt dieser Faktor eine Rolle.



  • Bei Keys wo das Vergleichen "teuer" ist (String etc.) sollte ne unordered_map ordentlich was bringen.

    Ansonsten könnte bei riesigen Datenmengen evtl. ein B-Baum was bringen. Allerdings auch wieder nicht wenn die Key-Vergleiche zu teuer sind.

    tntnet schrieb:

    Du siehst also, dass die Antwort viel komplizierter ist. Kurz gesagt, nimm einfach std::set, es sei denn, Du hast gute Gründe, etwas anderes zu nehmen.

    Genau 🙂



  • Bitte ein Bit schrieb:

    @manni66:
    Ich habe es mal getestet so wie es da steht. Ergebnis unter VS2012, Release Version

    Zeit bei std::vector : 16797ms
    Zeit bei std::set : 0ms

    Was soll auch ein Cache machen? Er beschleunigt im Best Case den std::vector Alg. um einen Faktor von 1000. Das dürfte ungefähr der Unterschied Zugriffsgeschwindigkeit L-Cache und Arbeitsspeicher sein. Und dieser Faktor ist konstant! Und je größer die Eingabe wird, desto weniger spielt dieser Faktor eine Rolle.

    das klingt zumindest seltsam, wie hast du im vector eingefügt und gesucht?

    mach den vector sortiert, zum suchen binary search (upper oder lower_bound)
    also auch beim einfügen als auch beim lookup
    und dann sollte der unterschied bei so kleinen Nummern zumindest unerheblich sein

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



  • Die 0 ms bei std::set erinnern mich gerade an einen Beitrag von Chandler Carruth:
    https://www.youtube.com/watch?v=nXaxk27zwlk&index=4&list=PLHTh1InhhwT75gykhs7pqcR_uSiG601oh



  • Ein lehrreiches Thema für mich 🙂

    Bin beim googlen auf diese Zusammenfassung gestoßen:

    What is set good for? The point isn't that set is useless-there are times when it's the right choice. We can finally write down the
    conditions when it's a better choice than sorted_vector or the equivalent:

    - The collection can potentially grow so large that the difference between O(N) and O(log N) is important.

    - The number of lookups is the same order of magnitude as the number of insertions; there aren't so few insertions that insertion speed is irrelevant.

    - Elements are inserted in random order, rather than being inserted in order.

    - Insertions and lookups are interleaved; we don't have distinct insertion and lookup phases. Sometimes all four of these conditions are true. If they are, you should use set; that's what it's designed for.

    If any of them are false, though, using such a complicated data structure would be a waste and you could get better performance by using a simple sorted vector.

    http://lafstern.org/matt/col1.pdf

    Glaube das beschreibt es ganz gut.



  • kurze_frage schrieb:

    und dann sollte der unterschied bei so kleinen Nummern zumindest unerheblich sein

    Du weisst schon wie viel eine Million mal tausend ist, oder?
    Mal 3 GHz angenommen, dann wäre die Konstante bei O(N^2) so bei die 50 Zyklen. Das kommt schon hin.

    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.



  • Bitte ein Bit schrieb:

    @manni66:
    Ich habe es mal getestet so wie es da steht.

    Leider lässt sich das nicht übersetzen 😉
    Ich habe aber auch ein wenig rumgespielt. Das sollte ungefähr dein Szenario sein.
    Leider habe ich hier nur einen Phenom II und zum Vergleich einen alten Celeron M. Wie es auf einer wirklich modernen CPU aussieht muss dann jemand anderes testen.

    Der Aufbau ist jedenfalls beim Vector immer schneller und das spätere Einfügen wird am neueren Prozessor stärker beschleunigt als der Rest. Die Konstante ist also größer geworden.

    Celeron schrieb:

    Vector:
    951464 Elemente in 213ms
    896 Elemente eingefügt in 1139ms
    73 Elemente gefunden in 1ms

    Vector mit bulk insert:
    951464 Elemente in 200ms
    896 Elemente eingefügt in 156ms
    73 Elemente gefunden in 1ms

    Set:
    951464 Elemente in 1575ms
    896 Elemente eingefügt in 2ms
    73 Elemente gefunden in 1ms

    Phenom schrieb:

    Vector:
    951464 Elemente in 111ms
    896 Elemente eingefügt in 232ms
    73 Elemente gefunden in 0ms

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

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

    #include <iostream>
    #include <vector>
    #include <set>
    #include <algorithm>
    #include <chrono>
    #include <random>
    
    const int numElem = 1000000;
    const int numInsert = 1000;
    std::uniform_int_distribution<> dis(1, 10*numElem);
    
    void set_runner()
    {
    	std::cout << "Set:\n";
    	auto start = std::chrono::system_clock::now();
    	std::set<int> s;
    	std::mt19937 gen(42);
    	for( int i = 1; i <= numElem; ++i ) {
    		s.insert(dis(gen));
    	}
    
    	auto fill = std::chrono::system_clock::now();
    	std::cout << s.size() << " Elemente in " << std::chrono::duration_cast<std::chrono::milliseconds>(fill -start).count() << "ms\n";
    
    	int count = 0;
    	for( int i = 1; i <= numInsert; ++i ) {
    		if(s.insert(dis(gen)).second) count++;
    	}
    	auto insert = std::chrono::system_clock::now();
    
    	std::cout << count << " Elemente eingefügt in " << std::chrono::duration_cast<std::chrono::milliseconds>(insert - fill).count() << "ms\n";
    
    	count = 0;
    
    	for( int i = 1; i <= numInsert; ++i ) {
    		if(s.count(dis(gen))) count++;
    	}
    	auto search = std::chrono::system_clock::now();
    
    	std::cout << count << " Elemente gefunden in " << std::chrono::duration_cast<std::chrono::milliseconds>(search - insert ).count() << "ms\n";
    
    }
    
    void vec_runner()
    {
    	std::cout << "Vector: \n";
    	auto start = std::chrono::system_clock::now();
    	std::vector<int> v;
    	std::mt19937 gen(42);
    	for( int i = 1; i <= numElem; ++i ) {
    		v.push_back(dis(gen));
    	}
    	std::sort(begin(v), end(v));
    	v.erase( std::unique(begin(v), end(v)), end(v));
    
    	auto fill = std::chrono::system_clock::now();
    	std::cout << v.size() << " Elemente in " << std::chrono::duration_cast<std::chrono::milliseconds>(fill -start).count() << "ms\n";
    
    	int count = 0;
    
    	for( int i = 1; i <= numInsert; ++i ) {
    		auto val = dis(gen);
    
    		auto it = std::lower_bound(begin(v), end(v), val );
    
    		if( it == end(v) || *it != val) {
    			count++;
    			v.insert(it, val);
    		}
    	}
    	auto insert = std::chrono::system_clock::now();
    
    	std::cout << count << " Elemente eingefügt in " << std::chrono::duration_cast<std::chrono::milliseconds>(insert - fill).count() << "ms\n";
    
    	count = 0;
    
    	for( int i = 1; i <= numInsert; ++i ) {
    		auto val = dis(gen);
    
    		if( std::binary_search(begin(v), end(v), val ) ) count++;
    	}
    
    	auto search = std::chrono::system_clock::now();
    
    	std::cout << count << " Elemente gefunden in " << std::chrono::duration_cast<std::chrono::milliseconds>(search - insert ).count() << "ms\n";
    }
    
    void vec2_runner()
    {
    	std::cout << "Vector mit bulk insert: \n";
    	auto start = std::chrono::system_clock::now();
    	std::vector<int> v;
    	std::mt19937 gen(42);
    	for( int i = 1; i <= numElem; ++i ) {
    		v.push_back(dis(gen));
    	}
    	std::sort(begin(v), end(v));
    	v.erase( std::unique(begin(v), end(v)), end(v));
    
    	auto fill = std::chrono::system_clock::now();
    	std::cout << v.size() << " Elemente in " << std::chrono::duration_cast<std::chrono::milliseconds>(fill -start).count() << "ms\n";
    
    	int count = v.size();
    
    	for( int i = 1; i <= numInsert; ++i ) {
    		v.push_back(dis(gen));
    	}
    	std::sort(begin(v), end(v));
    	v.erase( std::unique(begin(v), end(v)), end(v));
    	count = v.size() - count;
    	auto insert = std::chrono::system_clock::now();
    
    	std::cout << count << " Elemente eingefügt in " << std::chrono::duration_cast<std::chrono::milliseconds>(insert - fill).count() << "ms\n";
    
    	count = 0;
    
    	for( int i = 1; i <= numInsert; ++i ) {
    		auto val = dis(gen);
    
    		if( std::binary_search(begin(v), end(v), val ) ) count++;
    	}
    
    	auto search = std::chrono::system_clock::now();
    
    	std::cout << count << " Elemente gefunden in " << std::chrono::duration_cast<std::chrono::milliseconds>(search - insert ).count() << "ms\n";
    }
    
    int main()
    {
    	vec_runner();
    	std::cout << "\n\n";
    	vec2_runner();
    	std::cout << "\n\n";
    	set_runner();
    }
    


  • manni66 schrieb:

    ...

    Wenn du jetzt noch std::vector<..>::reserve(..) aufrufst, wo es möglich ist, sollte das Füllen noch schneller werden.


Anmelden zum Antworten