3. ist std::set eine schlechte Wahl?

ist std::set eine schlechte Wahl?


  • 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.

    0
  • ?

    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();
}
    0
  • T

    manni66 schrieb:

    ...

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

    0
  • ?

    theta schrieb:

    manni66 schrieb:

    ...

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

    Das bewegt sich im Rahmen der Messungenauigkeit.

    0
  • B
     

    #include <vector>
#include <algorithm>
#include <set>

#include <Windows.h>
#include <iostream>

int main(int argc, char** args)
{
	std::vector<int> L;
	//std::set<int> L;
	unsigned long R = 0;
	DWORD T0, T1;

	for (int i = 0; i < 1000000; i++)
		//L.insert(i);
		L.push_back(i);
	std::cout << "Ok starte Messung\n";
	T0 = GetTickCount(); // bestimmt die Anzahl der vergangenen Millisekunden seit den Start des OS
	for (int i = 0; i < 1000; i++)
	{
		int v = i * 33 + 111;

		L.push_back(v);
		std::sort(L.begin(), L.end());
		if (std::binary_search(L.begin(), L.end(), v + 1))
			R += (v + 1);

		/*L.insert(v);
		auto f = L.find(v + 1);
		if (f != L.end())
			R += (v + 1);*/
	}
	T1 = GetTickCount();	
	std::cout << "R: " << R << " Zeit: " << T1 - T0 << " ms\n";
	std::cin.get();
	return 0;
}

    Mein Code mit dem ich die Messung durchführte...

    0
  • C
     

    map:    R: 2266476762 Zeit: 47 ms
vector: R: 2266476762 Zeit: 15 ms

    #include <vector>
#include <algorithm>
#include <set>

#include <Windows.h>
#include <iostream>

int main(int argc, char** args)
{
    std::vector<int> L;
    //std::set<int> L;
    unsigned long R = 0;
    DWORD T0, T1;

    for (int i = 0; i < 1000000; i++)
        //L.insert(i);
        L.push_back(i);
    std::cout << "Ok starte Messung\n";
    T0 = GetTickCount(); // bestimmt die Anzahl der vergangenen Millisekunden seit den Start des OS
    for (int i = 0; i < 100000; i++)
    {
        int v = i * 33 + 111;

		auto it = std::lower_bound(L.begin(), L.end(), v);
        if(it != L.end() && *it != v)
			L.insert(it, v);
		if (std::binary_search(L.begin(), L.end(), v + 1))
            R += (v + 1);

        /*L.insert(v);
        auto f = L.find(v + 1);
        if (f != L.end())
            R += (v + 1);*/
    }
    T1 = GetTickCount();   
    std::cout << "R: " << R << " Zeit: " << T1 - T0 << " ms\n";
    std::cin.get();
    return 0;
}

    Edit: it != L.end() &&
    Kein messbarer Unterschied in der Laufzeit.

    0

  • Wenn man den vector mit "anfüllen und dann 1x sort" aufbaut, dann sollte man das set mMn. auch mit dem iterator-range-ctor anfüllen. Sonst ist der Vergleich ... komisch. Wird zwar nicht die Welt bringen, aber trotzdem...

    0
  • ?

    hustbaer schrieb:

    Wenn man den vector mit "anfüllen und dann 1x sort" aufbaut, dann sollte man das set mMn. auch mit dem iterator-range-ctor anfüllen. Sonst ist der Vergleich ... komisch. Wird zwar nicht die Welt bringen, aber trotzdem...

    Ja (den Konstruktor kannte ich nicht). Mit sortiertem vector füllen sind es dann rund 300ms beim Celeron, also deutlich weniger.

    0

  • Achso ich hätte es aus nem unsortierten vector befüllt.
    ps: Hätte nicht erwartet dass es so viel bringt.
    Dann is set ja auch insgesamt schneller. Also wenn man init+modify+lookup zusammen rechnet. Oder?

    0
  • B

    @Caligulaminus & manni66:
    Ok, das sehe ich ein. Wenn ich so einen vector nutze, dannn ist dieser dem set ebenbürtig. Geschätzte Komplexität: O(2log(n) + n). Das set benötigt da O(2log(n)). Da macht sich natürlich einen Unterschied in den Zugriffsgeschwindigkeiten bemerkbar.

    Eine kleine Gemeinheit sei mir noch erlaubt. Wenn ich den Container mit i + 100000 initialisiere statt mit i, ist der vector ein wenig langsamer, da dies vermutlich der Worst Case für den Einfüge Algorithmus ist.

    0
  • ?

    hustbaer schrieb:

    Dann is set ja auch insgesamt schneller. Also wenn man init+modify+lookup zusammen rechnet. Oder?

    Auf meinen ollen Prozessoren ja. Wäre halt interessant was ein Core i7 draus macht.

    0

  • Ich kann auf nem Haswell Xeon testen wenn du magst.
    Baut & läuft der Code unter Windoof?

    0
  • C

    @Bitte ein Bit

    Ich hatte die Anzahl der Iterationen verhundertfacht, weil mit GetTickCount() immer 0ms herauskamen. Aber das int v = i * 33 + 111; führte dann dazu, daß die meisten Werte am Ende 'eingefügt' wurden - klarer Vorteil für den Vector.

    Wenn ich nun auf 1000 Iterationen zurückgehe (alle einfügungen finden innen statt) und mit QueryPerformanceCounter() arbeite, komme ich auf

    0,18 ms für vector und 
0,29 ms für map

    bei 10000 Iterationen:

    1,8 ms für vector und 
2,9 ms für map
    0
  • ?

    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.

    0

  • 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
    0

  • 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
    0

  • 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
    0
  • K

    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!

    0
  • ?

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

    0

  • 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.

    0
Anmelden zum Antworten