3. String auf Enum Mappen

String auf Enum Mappen

  • ?

    Ich habe etwa 25 String Literale, die jeweils auf einen enum Wert "gemappt" werden sollen. Ich lese also Strings ein, und will wissen zu welchem enum die gehören.

    my_enum to_enum(const char* s);

    Simples Problem. Nun fragt sich, wie man das möglichst performant umsetzt. Denn die Variante jeden String einzeln zu vergleichen nutzt nicht aus, dass man mit einem Vergleich bereits mehrere Varianten ausschließen kann. Am schnellsten dürfte wohl so etwas in der Art sein:

    my_enum to_enum(const char* s)
{
    switch (*s)
    {
    case 'O':
        ...
    case 'B': 
        ...
    }
}

    Allerdings bricht das zusammen, sobald man ein Element hinzufügt. (Nicht nur, dass man es ändern muss, sondern die Änderungen sind auch nicht trivial.)

    Gibt es eine Möglichkeit diesen Code durch Templatemagie zur Compilezeit zu generieren?

    0

  • mapper schrieb:

    [...] etwa 25 String Literale [...] Ich lese also Strings ein, [...]

    Was jetzt?

    std::map ?

    0
  • ?

    Flex tut genau das, er baut aus Strings einen entsprechenden DFA, was im Prinzip genau das switch ist was du willst. Das erfordert natürlich eine Neukompilierung für jede Stringänderung.
    Ansonsten benutzte einfach eine std::map<std::string, int>. Das ist nicht optimal, aber wenn Performance nicht so die Rolle spielt ist das ok.

    0
  • ?

    std::map ist doch langweilig und langsam. Bitte etwas Template-Magie.

    0
  • ?

    Swordfish schrieb:

    Was jetzt?

    Ich lese Strings ein und will jeweils wissen zu welchem enum der gehört. Die Zuordnung String<->Enum ist aber natürlich zur Compilezeit bekannt. (Was auch immer man daran nicht verstehen konnte.)

    Flex tut genau das, er baut aus Strings einen entsprechenden DFA, was im Prinzip genau das switch ist was du willst.

    Interessant. Ist das nicht C? Wie machen die das?

    Das erfordert natürlich eine Neukompilierung für jede Stringänderung.

    Ja, natürlich. Das ist aber bei jeder Variante der Fall, sonst müsste ich die Strings ja zur Laufzeit einlesen.

    Ansonsten benutzte einfach eine std::map<std::string, int>. Das ist nicht optimal, aber wenn Performance nicht so die Rolle spielt ist das ok.

    Wenn Performance keine Rolle spielen würde, würde ich nicht fragen. 😉

    std::map ist doch langweilig und langsam. Bitte etwas Template-Magie.

    👍 😃 :xmas1: :xmas2: ➡ ⚠ 💡

    0
  • ?

    Davon ausgehend, dass der Compiler ein paar switch-Statements mit nur einem case vernünftig optimiert kann man das hier benutzen. Da kommt allerdings sehr schnell sehr viel Code raus. Hab schon so lange kein Python mehr gebastelt.
    Ab C++42 kann man den Python-Code so einbinden:

    template_code<python>("pythoncode")

    Bis dahin muss man sich einen custom build step oder so bauen.
    Für Flex gibts auch eine C++-Variante (Flex++ oder so).

    0
  • ?

    Ich befürchte bei läppischen 25 strings ist ein trie mit Kanonen auf Spatzen geschossen, aber Du kannst Dich ja mal einlesen - gcc bringt sogar einen mit.

    0
  • ?

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

    0
  • C

    warummer schrieb:

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

    Hast du irgendeinen der Beiträge hier gelesen? 🙄

    0
  • ?

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

    0
  • N

    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.

    0
  • C

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

    0
  • N

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

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

    0
  • F

    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

    0
  • C

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

    0
  • ?

    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

    0
  • F

    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?

    0
  • C

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

    0
  • C
    Mod

    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
    0
Anmelden zum Antworten