Hat die Länge der Schlüssel beeinflussen Wörterbuch-Leistung?

Verwende ich ein Wörterbuch in einem .NET-Projekt zu speichern eine große Anzahl von Objekten. Daher entschied ich mich für einen GUID-string als Schlüssel, um sicherzustellen, dass eindeutige Schlüssel für jedes Objekt.

Macht einen großen Schlüssel wie eine GUID (oder auch größeren) verringern Sie die Leistung eines Wörterbuchs, z.B. für das abrufen eines Objekts über seinen Schlüssel?

Dank,
Andrej

InformationsquelleAutor Andrej | 2009-10-08
  1. 14

    Ich würde empfehlen, mit einer tatsächlichen Guid eher als die string-Darstellung der Guid. Ja, beim vergleichen von strings die Länge wirkt sich auf die Anzahl der Operationen erforderlich, da es zu vergleichen die Zeichenfolgen Zeichen für Zeichen (auf ein minimum reduzieren; dies ist abgesehen von speziellen Optionen wie IgnoreCase). Die tatsächliche Guid geben Sie nur 16 bytes zu vergleichen, eher als das minimum von 32 in der string.

    Dass gesagt wird, sind Sie sehr wahrscheinlich nicht gehen, um keine Unterschiede feststellen...die vorzeitige Optimierung und all das. Ich würde einfach die Guid key seit das ist, was die Daten ist.

    • In der Tat, hashing wird eine Guid deutlich schneller als hashing eine 32-stellige Zeichenfolge. +1
    • Danke, das klingt vernünftig.
    • Was ist mit string-ein Praktikum von der CLR? (Intern erstellt hashtable für die Verfolgung von strings)
    InformationsquelleAutor Adam Robinson
  2. 7

    Die tatsächliche Größe eines Objekts mit Bezug auf das empfangen von Werten ist irrelevant. Die Geschwindigkeit von lookup-Werten ist viel mehr abhängig von der Geschwindigkeit zwei Methoden, die auf die übergebene IEqualityComparer<T> Instanz

    • GetHashcode()
    • Equals()

    BEARBEITEN

    Viele Menschen verwenden Zeichenfolge als Rechtfertigung für die Aussage, dass die größere Größe des Objekts verringert die lookup-Leistung. Dies muss mit einem Körnchen Salz, aus mehreren Gründen.

    • Die Leistung der oben erwähnten Methoden für String Rückgang in der Leistung als die Größe des string erhöht für den Standard-comparer. Nur weil es wahr ist, für System.String bedeutet nicht, es ist wahr, im Allgemeinen
    • Sie könnten genauso gut schreiben eine andere IEqualityComparer<String> in der Weise, dass die string-Länge war irrelevant.
    • Sie haben noch eine Schleife über den string zu vergleichen, die es in den ersten Platz, also für die Größe wird die Leistung beeinträchtigen, unabhängig von Ihrem Algorithmus.
    • Nein, Sie nicht. Es hängt alles davon ab, was ich denke, gleich sind strings in meinem Programm. Vielleicht habe ich nur über die ersten 3 Buchstaben-Präfix? Vielleicht nur den ersten Buchstaben. Oder ich einfach nur sagen, dass nicht-null-Zeichenfolgen gleich sind. Keiner von diesen wird in der Größe variieren, als der string wird größer
    • Dies scheint nicht zu gelten für die OP, dann muss er die volle Vergleiche auf guid-wie der Schlüssel.
    • Ich lese die OP die Frage mehr allgemein. Außerdem, die Leute, die sagen, dass ein String key performance hat einen direkten performance Bezug auf die Länge sind einfach falsch. Es ist eine Frage der IEqualityComparer<TKey>, nicht der Schlüssel selbst.
    • Sie sind nicht "einfach falsch". Im Standard-Fall-und wohl auch den MEISTEN Fällen-es wird eine direkte Korrelation. Auch die gängigsten Ersatz StringComparer.*IgnoreCase noch gehen Zeichen für Zeichen, bis es keine übereinstimmung findet, natürlich).
    • Ich versuche nicht zu streiten, aber es ist falsch zu sagen, dass ein String-Schlüssel der Größe hat eine direkte Auswirkung auf die Leistung. Kann es sein das die meisten wahrscheinlich, und standardmäßig der Fall, aber es ist eine falsche Behauptung. Sie kann einfach nicht sehen Sie sich den Schlüssel geben Sie ein Wörterbuch und machen eine solide Aussage über die performance-Eigenschaften von lookup. Nur die Kenntnis der details der IEqualityComparer<TKey - > kann Ihnen diese Informationen.
    • Ja, offensichtlich bist du richtig. Sie könnte die Implementierung einer IEqualityComparer<T> (für string oder irgendetwas anderes) ist O(1). Das ist aber, unwahrscheinlich. Die Unterscheidung, die Sie machen ist die wissenschaftliche, und ich könnte mir vorstellen, verursacht mehr Verwirrung als es sorgt für Klarheit.
    • Ich bin nicht einverstanden, dass es eine Akademische Diskussion, insbesondere, weil ich gesehen habe, genau diese Arten von IEqualityComparer<T> Implementierungen (mehr als 1). Und in mindestens einem der Fälle war es eine gute Idee und passen zum Szenario. Nur weil es unwahrscheinlich ist, bedeutet nicht, dass Sie nicht darauf stoßen.
    • Recht, als ich sagte, es ist unwahrscheinlich. Wenn ich meinte Sie nicht begegnen, dann würde ich gesagt haben, es wird nicht geschehen, an alle 😉 Wir sind einverstanden nicht einverstanden, dann.
    • vereinbart. Je mehr code ich sehe, desto mehr Dinge, die ich nicht mehr für selbstverständlich zu nehmen 🙁

    InformationsquelleAutor JaredPar
  3. 3

    Ja und Nein. Größere strings erhöhen die Speicher Größe eines Wörterbuchs. Und größere Größen meine etwas längere Zeiten zum berechnen von hash-Größen.

    Aber sich Gedanken über diese Dinge ist wahrscheinlich eine vorzeitige Optimierung. Während es wird langsamer, es ist etwas, das Sie wahrscheinlich tatsächlich feststellen.

    InformationsquelleAutor Anthony Mills
  4. 1

    Anscheinend nicht. Hier ist ein guter test: Dictionary String Key Test

    • Nicht ein wirklich guter test, denn es zeigt einen performance-Gewinn von nur 3 Sekunden für die 100 Millionen Wörterbucheinträge beim Vergleich von 2 und 20 Zeichen-Tasten. Dies ist nicht eine signifikante Verstärkung in den meisten Verwendungen ein Wörterbuch.
    • 2 Personen: 1,5 Sekunden. 20 Charaktere: 4,5 Sekunden. Da diese 3 Sekunden betragen einen Faktor 3 eine Verbesserung, ich denke, das ist bedeutsam. So lange natürlich, wie die Wörterbuch-Suche, die langsamste Schritt in Ihrer Verarbeitung.
    InformationsquelleAutor kelsmj
  5. 1

    Habe ich eine schnelle Google-Suche und fand diesen Artikel.

    http://dotnetperls.com/dictionary-string-key

    Er bestätigt, dass in der Regel kürzer Tasten besser sind als die längeren.

    • Dies ist nicht wirklich ein guter test, denn es zeigt einen performance-Gewinn von nur 3 Sekunden für die 100 Millionen Wörterbucheinträge beim Vergleich von 2 und 20 Zeichen-Tasten. Dies ist nicht eine signifikante Verstärkung in den meisten Verwendungen ein Wörterbuch. In jedem realen Welt Nutzung der Wörterbücher, die ich finden kann, sind die performance-Gewinne werden in nano-Sekunden. Also Ihre Aussage", die in der Regel kürzer Tasten besser sind als die längeren" ist irreführend. "In der Regel", es ist unbedeutend.
    InformationsquelleAutor ddc0660
  6. 1

    sehen Leistung - mit-Guid-Objekt oder Guid-Zeichenfolge als Schlüssel für eine ähnliche Frage. Sie konnte es testen mit einem alternativen Schlüssel.

    InformationsquelleAutor Michael Gattuso
Schreibe einen Kommentar