Performance map vs set vs unordered_map

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

[out]

gerüchteküche schrieb:

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.

Hat jemand ein Beispiel für eine gute Hashfunktion. Soll das eigentlich auch heißen, das die default Hashfunktion bei unordered_set nicht gut ist?

Btw: immer halte ich für ein zu starkes Wort.

[hnmmmmmmmmmm]

bei meinem tuple<int,int,int> sind die ints ca. im Bereich [-10,10] und myvector ist ca. 12 Elemente groß.

[gerüchteküche]

hnmmmmmmmmmm schrieb:

bei meinem tuple<int,int,int> sind die ints ca. im Bereich [-10,10] und myvector ist ca. 12 Elemente groß.

Vergiss set, nimm vector<int> und mach lineare suche.

vector<int> found; found.reserve(myvector.size()/3); // in C++14 mit VLA
for (auto i = myvector.begin(); i != myvector.end()-2; ++i)
{
  assert(abs(*i)<100 && abs(*(i+1))<100 && abs(*(i+2))<100)
  int perfect_hash = *i + 100**(i+1) + 10000**(i+2);
  if (std::find(found.begin(), found.end(), perfect_hash) != found.end())
    return false;
  found.push_back(perfect_hash);
}

Ansonsten hast du mit perfect_hash bereits die Hashfunktion.

[gerüchteküche]

out schrieb:

Hat jemand ein Beispiel für eine gute Hashfunktion. Soll das eigentlich auch heißen, das die default Hashfunktion bei unordered_set nicht gut ist?

Genau das. hash<int> ist einach die Identität (pfui).

Hier g++-4.8 -Ofast -std=c++11:

1s 93704ns: std::set
0s 621184ns: std::unordered_set
0s 457518ns: std::unordered_set + better:hash

Für 1000 zufällige Inserts mit mt19937 und genauso vielen zufälligen Lookups.

Testcode hier: http://ideone.com/0cHZMZ (und vergiss die Ausgabe auf ideone, da wird ohne Optimierungen kompiliert)

Hashfunktion:

template <typename T>struct hash;
template<> struct hash<unsigned> {
  std::size_t tables[256][4];

  template <typename Sseq>
  hash(Sseq&& q)
  {
    std::mt19937 gen(q);
    std::generate(&tables[0][0],
		    &tables[0][0] + sizeof(tables)/sizeof(**tables),
		    gen);
  }

  std::size_t operator() (unsigned x) const
  {
    return tables[(x>> 0)&0xff][0]^
           tables[(x>> 8)&0xff][1]^
           tables[(x>>16)&0xff][2]^
           tables[(x>>24)&0xff][3];
  }
};

[out]

Ich hab mal ein kleines Vergleichsprogramm geschrieben:
set<string> VS. unordered_set<string>
set<int> VS. unordered_set<int>

#include <algorithm>
#include <chrono>
#include <fstream>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <unordered_set>
#include <string>
#include <vector>
using namespace std;

class stopwatch
{
	std::chrono::time_point<std::chrono::high_resolution_clock> last_;
public:
	stopwatch()
	{
		start();
	}
	void start()
	{
		last_ = std::chrono::high_resolution_clock::now();
	}
	std::chrono::milliseconds::rep elapsed() const
	{
		auto t = std::chrono::high_resolution_clock::now();
		return std::chrono::duration_cast<std::chrono::milliseconds>(t - last_).count();
	}
};
struct random_number
{
	int lower_bound;
	int upper_bound;
	random_device& engine;

	random_number( int lower_bound, int upper_bound, random_device& engine ) : lower_bound(lower_bound), upper_bound(upper_bound), engine(engine) {}

	int operator()()
	{
		uniform_int_distribution<int> distribution( lower_bound, upper_bound );
		return distribution( engine );
	}
};

template<typename T>
void set_string( T it_begin, T it_end )
{
	set< typename iterator_traits<T>::value_type > s;

	for(; it_begin!=it_end; ++it_begin)
	{
		s.insert( *it_begin );
	}
}
template<typename T>
void unordered_set_string( T it_begin, T it_end )
{
	unordered_set< typename iterator_traits<T>::value_type > us;

	for(; it_begin!=it_end; ++it_begin)
	{
		us.insert( *it_begin );
	}
}

template<typename T>
void set_int( T it_begin, T it_end )
{
	set< typename iterator_traits<T>::value_type > s;

	for(; it_begin!=it_end; ++it_begin)
	{
		s.insert( *it_begin );
	}
}
template<typename T>
void unordered_set_int( T it_begin, T it_end )
{
	unordered_set< typename iterator_traits<T>::value_type > us;

	for(; it_begin!=it_end; ++it_begin)
	{
		us.insert( *it_begin );
	}
}

int main()
{
	const auto LOOPS = 20;
	const auto ANZ_ELEMENTS = 100000; // max. 566321, weil txt 566321 Woerter hat.
	ifstream file("test.txt"); // http://www.gutenberg.org/files/2600/2600.txt
	const vector<string> strings( (istream_iterator<string>(file)), (istream_iterator<string>()) );

	// set_string
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			set_string( begin(strings), begin(strings)+ANZ_ELEMENTS );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit set_string: " << zeit/LOOPS << "ms" << '\n';
	}
	// unordered_set_string
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			unordered_set_string( begin(strings), begin(strings)+ANZ_ELEMENTS );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit unordered_set_string: " << zeit/LOOPS << "ms" << '\n';
	}

	const auto lower_bound = 0;
	const auto upper_bound = 100000000;
	vector<int> ints( ANZ_ELEMENTS );
	generate_n( begin(ints), ANZ_ELEMENTS, random_number(lower_bound,upper_bound,random_device()) );

	// set_int
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			set_int( begin(ints), end(ints) );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit set_int: " << zeit/LOOPS << "ms" << '\n';
	}
	// unordered_set_int
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			unordered_set_int( begin(ints), end(ints) );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit unordered_set_int: " << zeit/LOOPS << "ms" << '\n';
	}
}

Wer das Programm mal testen will... einfach den Parameter ANZ_ELEMENTS einstellen und das Programm laufen lassen. Bei mir ist es so, dass set ca. ab 10.000 Elementen die Oberhand gewinnt.

Bei ANZ_ELEMENTS = 100000 habe ich folgende Zeiten (MSVC11):
set<string> ==> 470ms
unordered_set<string> ==> 488ms

set<int> ==> 1113ms
unordered_set<int> ==> 2483ms (Wundert mich doch ein bisschen )

[gerüchteküche]

out schrieb:

Wer das Programm mal testen will...

kriegt einen Segfault (nachdem der MSVC-Blödsinn in Zeile 128 korrigiert wurde).

/usr/include/c++/4.8.1/debug/safe_iterator.h:360:error: attempt to advance
a past-the-end iterator 1000 steps, which falls outside its valid range
.

Objects involved in the operation:
iterator @ 0x0x7fff65818b90 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPKSsNSt9__\
cxx19986vectorISsSaISsEEEEENSt7__debug6vectorISsS7_EEEE (constant iterator);
state = past-the-end;
references sequence with type `NSt7__debug6vectorISsSaISsEEE' @ 0x0x7fff65818\
b90
}

Ich habe keine Lust, das zu debuggen, bitte nachbessern.

[camper]

gerüchteküche schrieb:

out schrieb:

Wer das Programm mal testen will...

kriegt einen Segfault (nachdem der MSVC-Blödsinn in Zeile 128 korrigiert wurde).

Vergessen, test.txt vorzubereiten?

Ich erhalte (g++-4.8.1 -O3 -march=native)
Laufzeit set_string: 34.05ms
Laufzeit unordered_set_string: 8ms
Laufzeit set_int: 28.15ms
Laufzeit unordered_set_int: 15.2ms
mit ANZ=100000

[out]

camper schrieb:

gerüchteküche schrieb:

out schrieb:

Wer das Programm mal testen will...

kriegt einen Segfault (nachdem der MSVC-Blödsinn in Zeile 128 korrigiert wurde).

Vergessen, test.txt vorzubereiten?

Ich erhalte (g++-4.8.1 -O3 -march=native)
Laufzeit set_string: 34.05ms
Laufzeit unordered_set_string: 8ms
Laufzeit set_int: 28.15ms
Laufzeit unordered_set_int: 15.2ms
mit ANZ=100000

Ich hab ja find vergessen. Dass das keinem aufgefallen ist . Der neue Quellcode:

#include <algorithm>
#include <chrono>
#include <fstream>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <unordered_set>
#include <string>
#include <vector>
using namespace std;

class stopwatch
{
    std::chrono::time_point<std::chrono::high_resolution_clock> last_;
public:
    stopwatch()
    {
        start();
    }
    void start()
    {
        last_ = std::chrono::high_resolution_clock::now();
    }
    std::chrono::milliseconds::rep elapsed() const
    {
        auto t = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(t - last_).count();
    }
};
struct random_number
{
    int lower_bound;
    int upper_bound;
    random_device& engine;

    random_number( int lower_bound, int upper_bound, random_device& engine ) : lower_bound(lower_bound), upper_bound(upper_bound), engine(engine) {}

    int operator()()
    {
        uniform_int_distribution<int> distribution( lower_bound, upper_bound );
        return distribution( engine );
    }
};

template<typename Elementtyp, typename Set>
void test( const string& what, unsigned loops, unsigned anz_elemente, const vector<Elementtyp>& daten, Set& set_ )
{
	stopwatch sw;
	float zeit = 0.f;

	for(auto i=0; i!=loops; ++i)
	{
		Set s = set_;
		sw.start();

		// Daten einfuegen
		for(auto it=begin(daten); it!=begin(daten)+anz_elemente; ++it)
			s.insert( *it );

		// Daten suchen
		for(auto it=begin(daten); it!=begin(daten)+anz_elemente; ++it)
			s.find( *it );

		zeit += sw.elapsed();
	}
	cout << "Laufzeit " << what << ": " << zeit << "ms" << '\n';
}

int main()
{
    const auto LOOPS = 20;
    const auto ANZ_ELEMENTS = 100000; // max. 566321, weil test.txt 566321 Woerter hat.

	// Teste strings
	{
		ifstream file("test.txt"); // http://www.gutenberg.org/files/2600/2600.txt
		const vector<string> daten( (istream_iterator<string>(file)), (istream_iterator<string>()) );

		set<string> set_string;
		test( "set_string", LOOPS, ANZ_ELEMENTS, daten, set_string );

		unordered_set<string> unordered_set_string;
		test( "unordered_set_string", LOOPS, ANZ_ELEMENTS, daten, unordered_set_string );
	}

	// Teste ints
	{
		const auto lower_bound = 0;
		const auto upper_bound = 100000000;
		vector<int> daten( ANZ_ELEMENTS );
		generate_n( begin(daten), ANZ_ELEMENTS, random_number(lower_bound,upper_bound,random_device()) );

		set<int> set_int;
		test( "set_int", LOOPS, ANZ_ELEMENTS, daten, set_int );

		unordered_set<int> unordered_set_int;
		test( "unordered_set_int", LOOPS, ANZ_ELEMENTS, daten, unordered_set_int );
	}
}

Nun bekomme ich:
set<string> ==> 9536ms
unordered_set<string> ==> 6231ms

set<int> ==> 22162ms
unordered_set<int> ==> 12120ms

Wieso ist das mit Ganzzahlen so langsam

Würdest du es bitte nochmals testen, camper.