String auf Enum Mappen

cooky451

warummer schrieb:

warum geht denn die vorgeschlagene Lösung mit map<string, int> nicht?

Hast du irgendeinen der Beiträge hier gelesen?

@cooky: Ja, und alles was da stand war die Behauptung, dass das zu langsam sei. Ich würde sowas ja erst mal messen und dann die Werte posten.

Nexus

warummer schrieb:

@cooky: Ja, und alles was da stand war die Behauptung, dass das zu langsam sei. Ich würde sowas ja erst mal messen und dann die Werte posten.

Warum muss hier immer die Performancekeule ausgepackt werden, sogar wenn der Threadersteller explizit eine schnelle Lösung möchte?

Es ist doch egal, ob mapper den nächsten Compiler schreibt, oder ob er aus reinem Interesse nach einer maximal schnellen Lösung fragt. Er macht jedenfalls nicht den Eindruck eines Anfängers, der die Prioritäten von sauberem und schnellen Code noch nicht im Griff hat.

cooky451

warummer schrieb:

@cooky: Ja, und alles was da stand war die Behauptung, dass das zu langsam sei. Ich würde sowas ja erst mal messen und dann die Werte posten.

Dann poste deine Bedenken dazu dass std::map ähnlich schnell wie switch sei, und frag nicht solchen Dünnschiss.

Nexus

Zum Thema: Du könntest dir einen Präfixbaum (Trie) bauen, oder eine Verkettung von Lookup-Tables. switch macht ja nichts anderes.

Hier ein möglicher Anfang. Für jeden Index im String gibts eine Lookup-Table, wobei ein Zeichen nachgeschlagen wird. Zurückgegeben wird:

Found mit dem zugehörigen Integerwert des Enumerators, falls der String bis zu diesem Index schon eindeutig ist
Progress , falls weitere Zeichen geprüft werden müssen
NotFound , falls die bisherige Zeichenfolge keinem String entspricht.

Code:

#include <array>
#include <vector>

struct LookupTable
{
	enum State
	{
		Progress,
		Found,
		NotFound,
	};

	struct Result
	{
		explicit Result(State state = NotFound)
		: enumerator(0)
		, state(state)
		{
		}	

		explicit Result(int enumerator)
		: enumerator(enumerator)
		, state(Found)
		{
		}

		int enumerator;
		State state;
	};

	Result& operator[] (char ch)
	{
		return array[ch - 'a'];
	}

	std::array<Result, 26> array;
};

LookupTable::Result lookup(std::vector<LookupTable>& tables, const char* word)
{
	LookupTable::Result result(LookupTable::Progress);
	for (std::size_t index = 0; result.state == LookupTable::Progress; ++index)
		result = tables[index][word[index]];

	return result;
}

Eine Anwendung könnte so aussehen:

enum Words
{
	aaa = 11,
	abc = 22,
	cde = 33,
};

int main()
{
	// LUTs aufbauen
	std::vector<LookupTable> tables(2);
	tables[0]['a'] = LookupTable::Result(LookupTable::Progress);
	tables[0]['c'] = LookupTable::Result(cde);
	tables[1]['a'] = LookupTable::Result(aaa);
	tables[1]['b'] = LookupTable::Result(abc);

	// Nachschlagen
	LookupTable::Result aaaResult = lookup(tables, "aaa");
	LookupTable::Result abcResult = lookup(tables, "abc");
	LookupTable::Result cdeResult = lookup(tables, "cde");
	LookupTable::Result noResult = lookup(tables, "xyz");
}

Was noch zu tun ist:

Du kannst das Aufbauen der LUTs automatisieren, z.B. von einer std::map<std::string, int> .
Const-Correctness, Overload für operator[]
Bei fixen Grössen std::array statt std::vector verwenden
Evtl. Result zu einem Template Result<Enum> machen, sodass man den Enumerator typsicher (ohne Casten) bekommt
Für mehr als 26 Kleinbuchstaben erweitern

cooky451

Ich hab aus Spaß mal einen kleinen Benchmark geschrieben. (Hoffentlich stimmt da alles, die Ergebnisse sind nämlich ganz lustig.)
http://ideone.com/p3hHG1

Ideone (1kk Iterationen) schrieb:

......
to_animal_naive: 0.111903
......
to_animal_naive_map: 0.247395
......
to_animal_map: 0.090593
......
to_animal_unordered_map: 0.225098
......
to_animal_switch_only: 0.03257
......
to_animal_if_only: 0.031715
......
to_animal_nice_mix: 0.036592

g++ -O3 -march=native (Win7) (10kk Iterationen) schrieb:

..........................................................
to_animal_naive: 1.92811
..........................................................
to_animal_naive_map: 5.3103
..........................................................
to_animal_map: 0.760044
..........................................................
to_animal_unordered_map: 5.2323
..........................................................
to_animal_switch_only: 0.286016
..........................................................
to_animal_if_only: 0.278016
..........................................................
to_animal_nice_mix: 0.327019

VS2012 (Win7) (10kk Iterationen) schrieb:

..........................................................
to_animal_naive: 0.485028
..........................................................
to_animal_naive_map: 1.25907
..........................................................
to_animal_map: 0.540031
..........................................................
to_animal_unordered_map: 1.06806
..........................................................
to_animal_switch_only: 0.222013
..........................................................
to_animal_if_only: 0.236013
..........................................................
to_animal_nice_mix: 0.211012

Schon irgendwie bedenklich wie viel schneller VS hier bei den maps ist. Einen kleinen Vorsprung gab es da auf Windows ja schon immer (jedenfalls seit ich dabei bin), aber da hier.. ich habe fast das Gefühl, irgendwo einen Fehler gemacht zu haben.

@Nexus: Falls du dich da zurecht findest kannste deinen Test ja mal rein packen.

firefly

welche gcc version hast du verwendet?
Denn ein vergleich mit einem gcc <4.6/4.7 gegen vs2012 ist dann doch etwas unfair.

Hier das ergebnis mit gcc 4.6.1 (linux 64bit, CPU Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz)
Optimierung: -02:

Max iterations: 1000000
Enter animals:
Kleine Namen Aber Affe Ape Algen Allgemein Anteater Armadillo Albatross Alligator AmericanBison Antelope start
......
to_animal_naive: 0.145953
......
to_animal_naive_map: 0.16681
......
to_animal_map: 0.039556
......
to_animal_unordered_map: 0.104628
......
to_animal_switch_only: 0.024446
......
to_animal_if_only: 0.021665
......
to_animal_nice_mix: 0.025679

Wobei ich diese Zeiten erst ab dem 2. lauf des programms bekommen habe beim ersten lauf waren die zeiten ählich zu deinem mit gcc und 10Mio durchläufen

cooky451

Ich habe MinGW, mit Version 4.7. .. ist das schon wieder zu alt?^^

Mit dem Tool GNU gperf kann man sich C oder C++ Code erzeugen lassen, der dieses Mapping mittels einer Perfect Hash Function erledigt. Dürfte auch performant sein.

http://www.gnu.org/software/gperf/

Tutorial: http://www.ibm.com/developerworks/linux/library/l-gperf/index.html

firefly

cooky451 schrieb:

Ich habe MinGW, mit Version 4.7. .. ist das schon wieder zu alt?^^

ne die 4.7er reihe ist die aktuelle.
Hast du bei deinen Tests das programm nur einmal laufen lassen oder mehrmals?

cooky451

Mehrmals, mache ich immer so, hat sich nichts geändert. Schon komisch.

camper

Hier ein paar Ergebnisse mit einem Atom

Linux 3.7.0-hardened x86_64 Intel(R) Atom(TM) CPU 330 @ 1.60GHz  übertaktet auf 2 Ghz
g++ (Gentoo Hardened 4.5.4 p1.0, pie-0.4.7) 4.5.4 für x86_64 und x86 ABI
g++ (Gentoo 4.7.2 p1.3, pie-0.5.5) 4.7.2 für x32 ABI
Kompiliert mit
g++ -std=c++0x -O3 -march=native test.cpp
zusätzlich -fomit-frame-pointer im x86-Fall
jeweils 10M Iterationen
						x86_64		x86			x32
to_animal_naive:		2.3351		2.22243		2.39634
to_animal_naive_map:	5.98775		5.8825		4.47632
to_animal_map:			3.59247		1.77951		2.08863
to_animal_unordered_map:5.26436		5.13893		4.00907
to_animal_switch_only:	1.09334		0.747978	0.672978
to_animal_if_only:		1.06588		0.695158	0.667932
to_animal_nice_mix:		1.08924		0.758383	0.726613

cooky451

Ich muss gestehen, an einer TMP Lösung hätte ich durchaus Interesse. Leider weiß ich nicht wirklich wie das funktionieren sollte.. niemand eine Idee? Nach dem TMP Brainfuck Interpreter sollte das doch möglich sein.

cooky451 schrieb:

Ich muss gestehen, an einer TMP Lösung hätte ich durchaus Interesse. Leider weiß ich nicht wirklich wie das funktionieren sollte.. niemand eine Idee? Nach dem TMP Brainfuck Interpreter sollte das doch möglich sein.

Leider hat C++ keine Compile-Time-Reflection. In D würde das gehen.

Kellerautomat

Natuerlich geht sowas. Nur leider nicht automatisch. Man muesste eben String-Werte selbst angeben.

Kellerautomat

Ich hatte ein bisschen Langeweile, also habe ich sowas gleich mal implementiert.

Verwendungsbeispiel:

#include <iostream>

enum struct my_enum : unsigned
{
	foo,
	bar,
	baz,
	qux,
};

// Zum ueberpruefen
std::ostream& operator << (std::ostream& os, my_enum e)
{
	static char const* const table[] = { "foo", "bar", "baz", "qux" };
	return os << table[static_cast<unsigned>(e)];
}

int main()
{
	typedef tmp::enum_mapper
	<
		my_enum,
		// Reihenfolge der Eintraege egal, wird intern sowieso sortiert
		EMAP(my_enum::baz, 'b','a','z'),
		EMAP(my_enum::bar, 'b','a','r'),
		EMAP(my_enum::foo, 'f','o','o'),
		EMAP(my_enum::qux, 'q','u','x')
	> my_enum_mapper;

	my_enum_mapper mapper;

	std::cout << mapper("foo") << '\n';
	std::cout << mapper("bar") << '\n';
	std::cout << mapper("baz") << '\n';
	std::cout << mapper("qux") << '\n';

	try
	{
		std::cout << mapper("garbage") << '\n';
	}

	catch(std::invalid_argument const& iv)
	{
		std::cout << iv.what() << '\n';
	}
}

foo
bar
baz
qux
string 'garbage' has no enum value

https://ideone.com/3cwMzU

Auf Zeit messen habe ich allerdings jetzt keine Lust mehr, das darf jemand anderes machen. :xmas1:

Der ganze Aufwand...und dann wird doch insgesamt 10 mal strcmp aufgerufen.

Kellerautomat

Dann mach mal einen Vorschlag, wie man es besser machen koennte...

Der nächste Schritt wäre, einen Compile-Time-Trie aufzubauen.

Kellerautomat

Genau das mache ich doch durch die Rekursion?!