Hashtable oder sonst



  • Hallo zusammen, ich habe einen lexikalischen Analysator für den Compilerbau erstellt. Er liefert mir unter anderem Strings der Kategorie Bezeichner. Jetzt muss ich prüfen ob der String ein gewöhnlicher Bezeichner, oder ein Schlüsselwort ist. Das heisst, ich habe eine Menge von ungefähr 100 Schlüsselworter, und muss prüfen ob der String in dieser Menge enthalten ist. Dabei ziehe ich drei Möglichkeiten in Betracht. Entweder ich trage die Schlüsselworte in ein Array ein, und suche dann sequentiell, oder aber ich benutze eine Hashtable. Eigentlich ist es klar, dass Hashing schneller sein müsste. Aber dabei muss ja noch eine Hashfunktion arbeiten. Und 100 Schlüsselworte sind nicht gerade viel. Weiss jemand etwas dazu, was schneller ist ? Oder sollte man einen binären Suchbaum verwenden ?



  • Messen?

    Wobei meine erste Intuition wäre: nimm irgendeine geeignete Struktor (std::unordered_set!) und stelle sicher, dass dieser Lookup überhaupt relevant viel Zeit kostet (das würde ich nämlich ohne Messung erstmal anzweifeln).

    Edit: uups, sorry, ist C# und nicht C++. Dann also nicht std::unordered_set, sondern die entsprechende Klasse dafür in C#.


  • Administrator

    Wenn es so wenige sind, nimm das was die Wartbarkeit des Programmes erhöht. Der Unterschied dürfte wahrscheinlich recht klein sein und nicht ins Gewicht fallen. Dann geh lieber mit Wartbarkeit. Wenn es doch noch zu einem Problem wird, kannst du immer noch messen gehen und sinnvolle Optimierungen durchführen. Heisst dort, wo der Profiler dir mitteilt, wo es auch Performance-Probleme hat.



  • Wenn du nur Keys, aber keine Values dazu hast, dann benutze HashSet<T> oder aber SortedList<T>. Eine eigene Hash-Funktion brauchst du dann nicht, da es automatisch die des generischen Parameters (bei dir also string) benutzt.
    Hashtable sollte man nicht mehr benutzen, da es nicht generisch ist.



  • Ja Sorry, ich brauche Keys und Values. zB: "BEGIN" -> TokenEnum.begin Erst prüft man, ob "BEGIN" in der Hashtable enthalten ist, und gibt dann TokenEnum.begin zurück. TokenEnum ist ein Aufzählungstyp, die die Lexeme benennt.



  • Sequentill suchen wär auf jeden Fall langsamer. Bei binärer Suche bin ich mir nicht sicher, müsste man messen.



  • @mechanics sagte in Hashtable oder sonst:

    Sequentill suchen wär auf jeden Fall langsamer.

    Woher willst du das wissen? Dafür wissen wir viel zu wenig über die 100 Schlüsselwörter. Angenommen 90 der Schlüsselwörter kommen nur sehr selten vor und eines besonders oft. Wenn du dann nach durchschnittlicher Häufigkeit sortierst und immer erst mit dem häufigsten vergleichst, könntest du sogar mit einer sequentiellen Suche schneller sein, weil du eben fast immer nur einen Vergleich machen musst. Die paar mal, wo du dann linear durchscannen musst, fallen dann ggf. nicht so ins Gewicht. Man kann das auch kombinieren, z.B. die häufigsten 5 Wörter linear scannen, danach einen Hash errechnen. Oder wie auch immer.

    Die wirkliche Frage an @biter ist aber, ich wiederhole mich: hast du gemessen und erwies sich diese Funktion als relevant für die Geschwindigkeit? Ist das auf allen Systemen der Fall? Etc.



  • Also gemessen habe ich noch nicht, ich möchte die Funktion erst später einbauen, wollte mich nur vorbereiten. Messen kann ich immer noch. 100 Schlüsselworte sind wahrscheinlich wenig, und mit allen Methoden effizient beherrschbar. Am schnellsten ist wahrscheinlich ein binärer Suchbaum sofern er ausgeglichen ist. Man kann auch den String einfach mit allen Schlüsselworten ( per Hand ) vergleichen, und die häufigsten zuerst.



  • Dann nimm ein Dictionary<TKey, TValue> und dessen TryGetValue(...)-Methode:

    Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey,TValue> class is implemented as a hash table.

    PS: List<T>und Dictionary<K, V> sind die Standard-Containerdatentypen in .NET. Nur wenn man speziellere Datentypen braucht, dann zuerst noch im System.Collections.Generic Namespace nachsehen.
    Für WPF und dessen DataBinding gibt es z.B. aber noch ObservableCollection<T>.



  • Also Danke Euch, es war sehr aufschlussreif !



  • @biter sagte in Hashtable oder sonst:

    100 Schlüsselworte sind wahrscheinlich wenig, und mit allen Methoden effizient beherrschbar.

    Kommt drauf an was du unter "effizient" verstehst.

    Am schnellsten ist wahrscheinlich ein binärer Suchbaum sofern er ausgeglichen ist.

    Binäre Suchbäume sind fast nie die schnellste Möglichkeit.

    Man kann auch den String einfach mit allen Schlüsselworten ( per Hand ) vergleichen, und die häufigsten zuerst.

    Man kann viel machen, ja.



  • Lesbarkeit geht vor. Wenn du Schlüssel und Values benötigst und nichts stark dagegen spricht würde ich in C# immer zu einem Dictionary<TKey,TValue> greifen.

    MfG SideWinder



  • Einfügen und Suchen bei binären Suchbäumen, geht mit O( log n ), also effizient, Dictionary mit O( 1 ), ist natürlich schneller.



  • hustbaer, ob bei kleinen Datenmengen, 100 Schlüsselworte, Dictionary schneller ist als ein binärer Suchbaum wage ich zu bezweifeln, schliesslich muss da eine Hashfunktion f arbeiten, und hinterher noch: f(Argument) % Dictionary-Länge. "%" kostet Zeit, und f(Argument) auch. Den Pfad eines Suchbaums zu durchlaufen ist preiswert ! Wahrscheinlich sind alle Methoden hinreichend effizient !



  • @wob: gutes Argument. Ich bezog mich auf den "Normalfall" ohne weitere Einschränkungen und da wären 100 Elemente schon zu viel für eine sequentielle Suche. Aber ich finde deinen Einwand interessant, das könnte in so einem Use Case tatsächlich relevant sein.

    Ich finde diese ständigen Kommentare, dass Lesbarkeit vorgeht usw. ziemlich nutzlos. Das ist doch sowieso schon klar. Kein Grund, die Diskussion gleich abzuwürgen.


  • Administrator

    @biter Ich möchte nur kurz darauf hinweisen, dass Komplexität nichts über Geschwindigkeit aussagt. Wenn dein O(1) 10 Stunden braucht, aber dein O(log(n)) auch mit einem N in den Millionen noch innert Millisekunden fertig wird, so ist offensichtlich O(log(n)) noch lange schneller. Bitte niemals von Komplexität einfach auf Performance schliessen.


  • Administrator

    @mechanics sagte in Hashtable oder sonst:

    Ich finde diese ständigen Kommentare, dass Lesbarkeit vorgeht usw. ziemlich nutzlos. Das ist doch sowieso schon klar. Kein Grund, die Diskussion gleich abzuwürgen.

    Mag dir klar sein, aber vielen Anfängern nicht. Und ich erwarte bei solchen Fragen meistens, dass es Anfänger sind. Die wollen ihre 100 Einträge grossen Wörterbücher optimieren gehen, was meistens völlig sinnlos ist.



  • @dravere sagte in Hashtable oder sonst:

    @biter Ich möchte nur kurz darauf hinweisen, dass Komplexität nichts über Geschwindigkeit aussagt. Wenn dein O(1) 10 Stunden braucht, aber dein O(log(n)) auch mit einem N in den Millionen noch innert Millisekunden fertig wird, so ist offensichtlich O(log(n)) noch lange schneller. Bitte niemals von Komplexität einfach auf Performance schliessen.

    👍

    Ich habe manchmal das Gefühl, dass Professoren, dass nicht kapieren 😇 und die Studenten es entsprechend auch nicht...



  • @biter sagte in Hashtable oder sonst:

    hustbaer, ob bei kleinen Datenmengen, 100 Schlüsselworte, Dictionary schneller ist als ein binärer Suchbaum wage ich zu bezweifeln,

    Du könntest es auch einfach messen, dann wüsstest du es. Und wenn du es dann noch hier postest, dann wüssten wir es auch alle.

    schliesslich muss da eine Hashfunktion f arbeiten, und hinterher noch: f(Argument) % Dictionary-Länge. "%" kostet Zeit, und f(Argument) auch.

    Heutzutage werden kaum noch Hashtable-Grössen verwendet die keine Zweierpotenz sind, eben gerade weil dividieren sehr langsam ist. Das % ist also kein % sondern ein &, und das ist super-flott. Was die Hash-Funktion angeht: ja, da hast du recht. Dummerweise scheint .NET sogar den Hash-Code bei jeden Aufruf neu zu berechnen. Was mich etwas wundert, da .NET ja immutable Strings hat. Hmmm...

    Den Pfad eines Suchbaums zu durchlaufen ist preiswert !

    Jain. Sich über Pointer von einer Node zur nächsten durch den Speicher zu schwingen ist nicht greade cache-freundlich. Ausserdem musst du bei jedem Knoten einen String-Vergleich durchführen. Natürlich wird meist früh abgebrochen werden, aber gratis ist es auf jeden Fall auch nicht.

    Wahrscheinlich sind alle Methoden hinreichend effizient !

    Gut möglich. Was "hinreichend" ist kommt total auf die Anwendung an und da ich die nicht kenne...

    Langer Rede kurzer Sinn: Wenn es dir wichtig ist hier optimale Performance zu bekommen, dann vergleich mehrere Möglichkeiten. Wenn nicht, dann nimm Dictionary weil das die "default" Datenstruktur für deine Anwendung ist. Etwas anderes als Dictionary zu nehmen ohne verglichen zu haben (auf Grund von Vermutungen oder was weiss ich) ist mMn. Quatsch. Mit Soße.



  • Nochmals, etwas verspätet, Danke Euch !