Schneller(er) Stringvergleich?



  • Hi,

    ich habe hier eine Liste aus (fest vogegebenen) Strings, welche als Eingangsparameter in meine Funktion kommen. Abhängig davon, welcher String vorgegeben wird, ist eine bestimmte Operation auszuführen. Wäre der Datentyp ein Integer und kein char-Array, wäre das ein klassischer Fall für ein switch-case.

    Allerdings ist es nun eben ein char-Array. Aktuell mache ich für jeden der möglicherweise vorkommenden Strings strncmp()s in einer langen Verkettung von if/else-if/else-...-Abfragen.

    Da es jetzt leider doch sehr viele mögliche Strings werden, ist diese Verkettung recht lang und - und das finde ich wesentlich fataler - die Abarbeitungszeit wächst, um so weiter hinten in der if-else-Kette so ein Vergleich steht.

    Meine Frage: gibt's da nichts schnelleres? Von den Strings als Parametern komme ich allerdings nicht weg, die sind von einer übergeordneten API vorgegeben, die ich nicht in der Hand habe und die ich nicht durch was anderes ersetzen kann.



  • Wegen der fest vorgegebenen Liste von Strings geht es viel viel schneller.

    Würden zum Beispiel alle mit einem anderen Anfangsbuchstaben anfangen, känntest Du switch(str[0]) schreiben. Vielleicht reicht bei Dir ja switch(str[0]+23*str[3]), weil sich zufällig alle im ersten oder dritten Buchstaben unterscheiden.

    Such mal nach perfect hashfunction und so. Es gibt fertige Programme, die basteln Dir aus eine String-Liste ein wenig C-Code, der ganz flott ist.



  • Sortiere die Liste der möglichen Strings, mach eine binäre Suche und dann switch(position).



  • Vielleicht ist die Lösung, die ich auf meine Site auf http://programming.sirrida.de/programming.html#c_case_of_string (Using a mapping container) skizziert habe, genau das, was benötigt wird.
    Die schnellste Lösung findet sich in case_map.c / case_map.cpp.
    Ein Testprogramm case.c / case.cpp liegt auch bei, mit dem man die Geschwindigkeiten der verschiedenen Ansätze durch Abstoppen vergleichen kann.
    Ggf. sollte man noch die Hashfunktionen und die Kostenfaktoren anpassen.



  • Klingt für mich so, als wolltest du perfect hashing (am besten minimal perfect hashing). Ich lass mal http://burtleburtle.net/bob/hash/perfect.html da. Unter Umständen ist auch http://cmph.sourceforge.net/ einen Blick wert, obwohl das für deutlich größere Datenmengen ausgelegt ist als deine vtml. popligen paar hundert.

    Dann den Hash als Index für ein Array von Funktionszeigern verwenden, und ab geht die Post.



  • Nach meinen Tests dauert eine gute oder gar perfekte Hashfunktion meist deutlich länger, als wenn man eine einfache benutzt und ein paar Kollisionen in Kauf nimmt.
    Mein Ansatz (s.o.) vermeidet den Aufwand, indem beim ersten Mal mehrere relativ einfache Hashfunktionen durchprobiert werden und dann die schnellste Möglichkeit ausgewählt wird, die für alle folgenden Durchläufe benutzt wird.
    Schade, daß der Compiler das nicht alles schon zur Compilezeit macht...



  • man muss es finde ich nicht ganz sooo kompiliziert machen.

    ich würde es so machen:

    int switchString(char *string) {
          switch(strlen(string)) {
                case /* hier die verschieden langen strings */
    

    ist halt nicht die schnellste lösung.

    die schnellste lösung wäre, wenn ud nach einem bestimmten algorithmus hash-werte jedes strings erstellst.
    dann erstellst du mit dem gleichen algorithmus den hash-wert vom input-string und vergleichst diesen hash mit der liste der vorberechneten.



  • Sirrida schrieb:

    Schade, daß der Compiler das nicht alles schon zur Compilezeit macht...

    Dann gib den GNU-Leuten doch mal einen Tipp, wie sie zur Compilezeit den ersten Laufzeitdurchlauf messen und ihren Code dann entsprechend optimieren sollen.



  • Das schöne an meinen Lösungen ist, daß die Anwendung trivial ist und man sich um die Implementation keine Gedanken machen muß. Der dahinter steckende Code wird wiederverwendet. Es ist natürlich klar, daß der durch die Macros generierte Code nicht der lesbarste ist, aber das sollte eigentlich egal sein.
    Wenn man mit Gewalt Macros umgehen möchte, wird man meiner Meinung nach stets auf Geschwindigkeit und/oder auf Lesbarkeit verzichten müssen...
    Funktionieren tut das Ganze unter C und C++ mit C-Strings (char*) oder STL-Strings, je nach Wahl.

    Die von mir verwendete Syntax ist diese (von Modula abgeschaut):

    SWITCH(selector)
      CASE(const1) statements
      CASE(const2) statements
      ...
      DEFAULT statements
      END
    


  • Es ist vermutlich keine besonders gute Idee, zur Compilezeit Zeiten messen zu wollen, denn das wäre zu aufwendig und vermutlich auch zu ungenau. Man kann jedoch Zeiten grob abschätzen oder für Beispielfälle mal genauer abstoppen, wie ich es getan habe. Mit den so ermittelten Zeiten für Stringvergleiche und Hashfunktionen kann man dann den gegebenen Satz von Stringkonstanten eines Switch-Statements analysieren. Dies kann ein Compiler genau so machen, wie es meine Routinen zur Laufzeit tun. Im Prinzip wäre die gesamte Rechnung sogar wegoptimierbar, da alles nötige zur Compilezeit verfügbar ist, aber zumindest GCC kann das nicht, auch nicht bei -O3.



  • Du hast meine Anspielung nicht verstanden und dich in allgemeinen Marketingsprüchen ergangen.



  • Ich habe die Anspielung nicht verstanden; bitte kläre mich auf!
    Apropos Marketing: Ich will nichts verkaufen, sondern nur eine brauchbare Lösung anbieten und konstruktive Kritik hören.
    Es gibt natürlich fast nichts, was man nicht noch verbessern könnte...


Log in to reply