Hashtable oder sonst



  • @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 !