3. Performance map vs set vs unordered_map

Performance map vs set vs unordered_map

  • ?

    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?

    0
  • ?

    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

    0
  • ?

    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.

    0
  • ?

    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.

    0
  • ?

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

    0
  • ?

    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.

    0
  • ?

    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];
  }
};
    0
  • ?

    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 😮 )

    0
  • ?

    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.

    0
  • C
    Mod

    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

    0
  • ?

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

    0
  • ?

    out schrieb:

    Wieso ist das mit Ganzzahlen so langsam 😕

    Ah, ok, das liegt daran, dass der random_device wirklich ziemlich gute Zufallszahlen erzeugt, da kommen fast keine doppelten vor 😮. In der test.txt Datei sind logischerweise viele Wörter doppelt.

    0
  • ?

    out schrieb:

    out schrieb:

    Wieso ist das mit Ganzzahlen so langsam 😕

    Ah, ok, das liegt daran, dass der random_device wirklich ziemlich gute Zufallszahlen erzeugt, da kommen fast keine doppelten vor 😮. In der test.txt Datei sind logischerweise viele Wörter doppelt.

    Ach ich hab upper_bound ja auf 100 Mio gesetzt 😃

    0
  • K

    Einfach mal mit VS 2013 Preview im Release Mode:

    Laufzeit set_string: 1090ms
Laufzeit unordered_set_string: 290ms
Laufzeit set_int: 900ms
Laufzeit unordered_set_int: 370ms
    0
  • ?

    knivil schrieb:

    Einfach mal mit VS 2013 Preview im Release Mode:

    Laufzeit set_string: 1090ms
Laufzeit unordered_set_string: 290ms
Laufzeit set_int: 900ms
Laufzeit unordered_set_int: 370ms

    😮 Welchen Quellcode hast du genommen knivil, den 1 oder den 2? Kann eigentlich nicht sein dass VS 2012 im Release so viel langsamer ist. :p

    0
  • C
    Mod

    out schrieb:

    Würdest du es bitte nochmals testen, camper. 🙂

    Laufzeit set_string: 1324ms
    Laufzeit unordered_set_string: 282ms
    Laufzeit set_int: 957ms
    Laufzeit unordered_set_int: 297ms
    mit der Anpassung

    random_device rdevice{};
        generate_n( begin(daten), ANZ_ELEMENTS, random_number(lower_bound,upper_bound,rdevice) );
    0
  • ?
     

    Laufzeit set_string: 2874ms
Laufzeit unordered_set_string: 663ms
Laufzeit better_unordered_set_string: 609ms
Laufzeit set_int: 3418ms
Laufzeit unordered_set_int: 1116ms
Laufzeit better_unordered_set_int: 1161ms

    Mit

    unordered_set<string, better::hash<string> > better_unordered_set_string;
test( "better_unordered_set_string", LOOPS, ANZ_ELEMENTS, daten, better_unordered_set_string );

    Wobei der String-Hash einfach

    std::size_t hash = 13;
while (*s)
    hash = hash * 101  +  *s++;

    ist.

    Das zeigt wieder, wie schlecht std::hash ist. (Der int-hash ist hier einigermassen akzeptabel, aber nur, weil der Inhalt selbst zufällig ist, was normalerweise ja nicht der Fall ist.)

    0
  • K

    out schrieb:

    Kann eigentlich nicht sein dass VS 2012 im Release so viel langsamer ist.

    Den 2ten. Es macht einen Unterschied, ob mittels F5 oder mittles Strg+F5 gestartet wird, also Release Mode + Debugger oder einfach ohne Debugger. (Intel Core2Quad Q9650 3GHz)

    Das zeigt wieder, wie schlecht std::hash ist

    Unterschied < 10%, so unglaublich schlecht scheint es nicht zu sein.

    0
  • ?

    Test mit Google sparsehash:

    Laufzeit set_string: 2879ms
Laufzeit unordered_set_string: 700ms
Laufzeit better_unordered_set_string: 634ms
Laufzeit google_sparse_hash_set: 1200ms
Laufzeit google_dense_hash_set: 534ms
Laufzeit set_int: 3565ms
Laufzeit unordered_set_int: 1194ms
Laufzeit better_unordered_set_int: 1225ms
Laufzeit google_sparse_hash_set: 1037ms
Laufzeit google_dense_hash_set: 215ms

    Einfach includes hinzufügen und

    google::sparse_hash_set<int> sparse_hash;
test( "google_sparse_hash_set", LOOPS, daten.size(), daten, sparse_hash );

google::dense_hash_set<int> dense_hash;
dense_hash.set_empty_key(-1);
test( "google_dense_hash_set", LOOPS, daten.size(), daten, dense_hash );

google::sparse_hash_set<string> sparse_hash;
test( "google_sparse_hash_set", LOOPS, ANZ_ELEMENTS, daten, sparse_hash );

google::dense_hash_set<string> dense_hash;
dense_hash.set_empty_key(std::string(1, '\0'));
test( "google_dense_hash_set", LOOPS, ANZ_ELEMENTS, daten, dense_hash );

    Faktor 5!!!

    0
  • K

    gerüchteküche schrieb:

    Faktor 5!!!

    Normalerweise wird Geschwindigkeit meist mit Speicher eingekauft. Bei einem ernsthaften Vergleich nur eine Seite zu betrachten, ist grob fahrlaessig.

    0
Anmelden zum Antworten