Ein-Dimensionale std::unordered_map?



  • Hallo,

    ich bastel gerade wieder mal an einem tokenizer für strings. Dafür hab ich eine relativ große Anzahl an keywords, auf die jedes token überprüft werden soll (also ob das aktuelle token ein keyword ist oder nicht).

    Da das ganze gut mit der Anzahl der keywords skalieren soll, will ich einen solchen Test in O(1) durchführen, was mich nach Recherche zu einer std::unordered_map gebracht hat.

    Allerdings ist eine unordered_map ja zwei-dimensional, enthält also immer ein key-value Paar. Allerdings brauche ich hier ja gar keinen Value, sondern es reicht ja schon zu checken ob die map den key enthält oder nicht.

    Daher jetzt meine Frage, wie löst man sowas dann am besten? Gibt es auch eine ein-dimensionale map, die dann quasi wie ein array funktioniert nur halt mit suchen in O(1)? Sowas bräuchte ich halt.





  • Es gibt std::unordered_set. Allerdings Obacht: Hashtables sind nur eine gute Idee, wenn deine Keys aus vertrauenswürdiger Quelle stammen, sonst ergeben sich da leicht DoS-Möglichkeiten (indem der Angreifer die Keys so wählt, dass sie alle kollidieren).

    Ansonsten benutze ich für solche Dinge gern ternäre Suchbäume. In Boost ist einer bereits etwas versteckt implementiert, als Teil von Boost.Spirit: boost::spirit::qi::symbols. Zum Beispiel:

    #include <boost/spirit/include/qi.hpp>
    
    ...
    
    boost::spirit::qi::symbols<char> tst;
    
    tst.add("foo");
    
    if(tst.find("foo")) { ... }
    


  • Braunstein schrieb:

    Wie wärs mit unordered_set?

    seldon schrieb:

    Es gibt std::unordered_set. Allerdings Obacht: Hashtables sind nur eine gute Idee, wenn deine Keys aus vertrauenswürdiger Quelle stammen, sonst ergeben sich da leicht DoS-Möglichkeiten (indem der Angreifer die Keys so wählt, dass sie alle kollidieren).

    Hm ok, ich hab aber irgendwo gelesen dass bei einem unordered_set nicht garantiert wird dass der lookup in O(1) durchgeführt wird...

    Die keywords kann man in meiner Anwendung theoretisch gruppieren nach Vertrauenswürding und Nicht Vertrauenswürdig. Würde es dann Sinn machen dafür zwei verschiedene Container zu verwenden oder lieber alles in einen Container stecken der auch mit Nicht Vertrauenswürdigen keys umgehen kann?

    Was ich mir auch noch überlegt hatte einfach einen dummy-wert in meine unordered_map zu schreiben, so nach diesem Motto:

    std::unordered_map<std::string, int> my_map;
    my_map["test"] = 0; // Null ist hier einfach ein Dummy-Wert
    

    Oder nimmt man dann lieber gleich ein std::unordered_set?



  • Mit einem DFA geht es schneller als mit einem unordered_set.

    Beispiel:
    Tokens:

    Ich
    Du
    Ice
    

    DFA:

    (Start) -I-> (I) -c-> (Ic) -h-> (Ich) -EOF-> ((Ich))
                               -e-> (Ice) -EOF-> ((Ice))
            -D-> (D) -u-> (Du) -EOF-> ((Du))
    

    Die Dinger in Klammern sollen Zustände sein, -Z-> heißt Übergang wenn das nächste Zeichen ein Z ist, doppelte Klammern sind ein Endzustand, nicht existente Übergänge bedeuten das Token wurde nicht gefunden. Damit ließt er die minimale Anzahl an Zeichen.

    Boost hat sicher was, womit man zur Compilezeit einen DFA mit beliebigen Tokens füttern kann. Alternativ kannst du Flex nehmen, das ist genau dafür da und wahrscheinlich schneller als alles, was man spontan von Hand baut. Obwohl das natürlich deinen ganzen Tokenizer obsolet macht.

    Außerdem brauchst du keine Hash-Funktion und hast keine Probleme mit bösartigem Input.



  • happystudent schrieb:

    Hm ok, ich hab aber irgendwo gelesen dass bei einem unordered_set nicht garantiert wird dass der lookup in O(1) durchgeführt wird...

    Kannst annehmen, daß sie es in O(1) packt. Es ist nicht garantiert, aber schon sehr wahrscheinlich.

    happystudent schrieb:

    Die keywords kann man in meiner Anwendung theoretisch gruppieren nach Vertrauenswürding und Nicht Vertrauenswürdig. Würde es dann Sinn machen dafür zwei verschiedene Container zu verwenden oder lieber alles in einen Container stecken der auch mit Nicht Vertrauenswürdigen keys umgehen kann?

    Die Keywords SIND vertrauenswürdig. Nicht vertrauenwürdig wäre, wenn Du fremden Nutzern die Möglichkeit einräumst, zur Laufzeit die Hashtable zu befüllen.

    happystudent schrieb:

    Was ich mir auch noch überlegt hatte einfach einen dummy-wert in meine unordered_map zu schreiben, so nach diesem Motto:

    std::unordered_map<std::string, int> my_map;
    my_map["test"] = 0; // Null ist hier einfach ein Dummy-Wert
    

    Oder nimmt man dann lieber gleich ein std::unordered_set?

    Logo.

    Kannst auch lookups mit O(1) erzwingen, perfect hashing oder cockoo hastables, wird aber nicht nötig sein. Wirsr nichmal den Unterschied zwischen unordered_set und set bemerken können.

    Damit Du nicht googlen musst:
    cuckoo hashing: http://de.wikipedia.org/wiki/Kuckucks-Hashing

    perfect hashing: Du probiert so lange Formeln aus, bis Du eine einfache Formel hast, die jedes keyword auf einen anderen Platz legt. Zum Beispiel bei "Ich" "Du" "Ice" einfach returen {letzter Buchstabe}-'a' modulo 3, und da steht das Wort nochmal, ums mit der Eingabe vetgleichen zu können.



  • nwp3 schrieb:

    Außerdem brauchst du keine Hash-Funktion und hast keine Probleme mit bösartigem Input.

    Deswegen beginnen alle meine Programme mit

    #define i hujhdjghaskgfhkgfgfhjdfgfhzgfuzgfhjfagzufgshjkfagzfuagzhsdugauzgdaufkgbefzufegfuzfghzfdujgzufdasgzeaugfzufdasgzufasdgfdahuzdagbzufdasgasuzadsgzsdaugzufagfauzafdgzudasfgauzdasfgzufdasgaszuofdasgdshufalgazuagasuzoadsgfzudasfolgauzolasfgzouagzudasfogasdzuoafgzuafolgauol
    


  • nwp3 schrieb:

    Mit einem DFA geht es schneller als mit einem unordered_set.

    Ok, das sieht aber schon aufwendiger aus vor allem weils das nicht in der std lib gibt... Aber ich werd mir das mal anschauen, danke.

    volkard schrieb:

    Kannst annehmen, daß sie es in O(1) packt. Es ist nicht garantiert, aber schon sehr wahrscheinlich.

    Ok, das ist schonmal gut zu wissen.

    volkard schrieb:

    Die Keywords SIND vertrauenswürdig. Nicht vertrauenwürdig wäre, wenn Du fremden Nutzern die Möglichkeit einräumst, zur Laufzeit die Hashtable zu befüllen.

    Ja, also deswegen könnte ich die theoretisch auch gruppieren. Es gibt einen (relativ großen) Satz feste keywords die sich nicht ändern und eine (theoretisch) beliebige Anzahl an dynamischen keywords die zur Laufzeit vom Benutzer erzeugt werden können.

    volkard schrieb:

    Kannst auch lookups mit O(1) erzwingen, perfect hashing oder cockoo hastables, wird aber nicht nötig sein. Wirsr nichmal den Unterschied zwischen unordered_set und set bemerken können.

    Damit Du nicht googlen musst:
    cuckoo hashing: http://de.wikipedia.org/wiki/Kuckucks-Hashing

    perfect hashing: Du probiert so lange Formeln aus, bis Du eine einfache Formel hast, die jedes keyword auf einen anderen Platz legt. Zum Beispiel bei "Ich" "Du" "Ice" einfach returen {letzter Buchstabe}-'a' modulo 3, und da steht das Wort nochmal, ums mit der Eingabe vetgleichen zu können.

    Ok, danke schonmal für den Link und die Infos.

    volkard schrieb:

    Deswegen beginnen alle meine Programme mit

    #define i hujhdjghaskgfhkgfgfhjdfgfhzgfuzgfhjfagzufgshjkfagzfuagzhsdugauzgdaufkgbefzufegfuzfghzfdujgzufdasgzeaugfzufdasgzufasdgfdahuzdagbzufdasgasuzadsgzsdaugzufagfauzafdgzudasfgauzdasfgzufdasgaszuofdasgdshufalgazuagasuzoadsgfzudasfolgauzolasfgzouagzudasfogasdzuoafgzuafolgauol
    

    Hm, ist das ein Witz? 😃
    Oder hat das einen Sinn sowas zu machen?


Log in to reply