Zuordnung von String zu Integer - Performance verschiedener Ansätze
Nehmen wir an, ich muss eine Zuordnung von String zu einer Ganzzahl vornehmen. Die ganzen Zahlen sind einzigartig und bilden einen kontinuierlichen Bereich beginnend bei 0. Das ist:
Es gibt mindestens zwei einfache Möglichkeiten, dies zu tun. Mit einer Hashmap:
%Vor%Oder mit einer Liste:
%Vor% Welchen Ansatz sollte ich verwenden und warum? Möglicherweise hängt die relative Leistung von der Größe der Liste / Karte ab, da List#indexOf() eine lineare Suche mit String#equals() - & gt; O (n) Effizienz, während HashMap#get() Hash verwendet, um die Suche einzugrenzen - & gt; sicherlich effizienter, wenn die Karte groß ist, aber vielleicht unterlegen ist, wenn es nur wenige Elemente gibt (es muss ein gewisser Mehraufwand bei der Berechnung des Hashes bestehen, oder?).
Da der Vergleich von Java-Code notorisch schwierig ist, würde ich gern ein paar fundierte Vermutungen anstellen. Ist meine Argumentation korrekt (Liste ist besser für kleine, Karte ist besser für große)? Was ist die Schwellengröße ungefähr? Welchen Unterschied machen verschiedene List und HashMap Implementierungen?
6 Antworten
Eine dritte Option und möglicherweise mein Favorit wäre die Verwendung eines trie :
Ich wette, es schlägt die HashMap in der Leistung (keine Kollisionen + die Tatsache, dass die Berechnung des Hash-Codes sowieso O(length of string) ist) und möglicherweise auch List in einigen Fällen (wie wenn Ihre Strings haben lange gemeinsame Präfixe, da das indexOf viel Zeit in den equals -Methoden verschwenden würde.
Wenn ich zwischen Liste und Karte wähle, würde ich nach einem Map (zB HashMap ) gehen. Hier ist meine Argumentation:
-
Lesbarkeit
Die Map-Schnittstelle bietet einfach eine intuitivere Benutzeroberfläche für diesen Anwendungsfall.
-
Optimierung am richtigen Ort
Ich würde sagen, wenn Sie
Listverwenden, würden Sie sowieso für die kleinen Fälle optimieren. Das ist wahrscheinlich nicht, wo der Flaschenhals ist.
Eine vierte Option wäre die Verwendung von LinkedHashMap , die Iteration bei kleiner Größe und get die zugehörige Zahl bei großer Größe.
Eine fünfte Option besteht darin, die Entscheidung in einer separaten Klasse zusammen zu kapseln. In diesem Fall könnten Sie es sogar implementieren, um die Strategie in der Laufzeit zu ändern, wenn die Liste wächst.
Sie haben recht: Eine Liste wäre O (n), eine HashMap wäre O (1), also wäre eine HashMap schneller für n groß genug, so dass die Zeit zum Berechnen des Hash die Liste nicht überflutete lineare Suche.
Ich kenne die Schwellengröße nicht; das ist eine Frage des Experimentierens oder der besseren Analytik, als ich gerade aufbringen kann.
Ihre Frage ist in allen Punkten völlig korrekt:
-
HashMaps sind besser (sie verwenden einen Hash) - Benchmarking Java-Code ist schwer
Aber am Ende des Tages müssen Sie nur Ihre spezielle Anwendung benchmarken. Ich sehe nicht, warum HashMaps für kleine Fälle langsamer sein würden, aber das Benchmarking wird Ihnen die Antwort geben, ob dies der Fall ist oder nicht.
Eine weitere Option, eine TreeMap , ist eine weitere Karte Datenstruktur, die einen Baum im Gegensatz zu einem Hash verwendet, um auf die Einträge zuzugreifen. Wenn Sie Benchmarking durchführen, können Sie dies auch gut benchmarken.
Beim Benchmarking ist eines der Hauptprobleme der Garbage Collector. Wenn Sie jedoch einen Test durchführen, der keine Objekte zuweist, sollte das kein Problem sein. Füllen Sie Ihre Karte / Liste, dann schreiben Sie einfach eine Schleife, um N zufällige Elemente zu erhalten, und dann Zeit, die vernünftig reproduzierbar und daher informativ sein sollte.
Leider müssen Sie dies selbst benchmarken, da die relative Leistung entscheidend von den tatsächlichen String-Werten und auch von der relativen Wahrscheinlichkeit abhängt, dass Sie eine Zeichenfolge testen, die nicht in Ihrem Mapping enthalten ist. Und natürlich hängt es davon ab, wie String.equals() und String.hashCode() implementiert sind, sowie die Details der verwendeten Klassen HashMap und List .
Im Fall von HashMap wird bei einer Suche normalerweise der Hash des Schlüssels String berechnet und dann der Schlüssel String mit einem oder mehreren Entry-Schlüssel-Strings verglichen. Die Hashcode-Berechnung berücksichtigt alle Zeichen des Strings und hängt daher vom Schlüssel String ab. Die Operationen equals untersuchen normalerweise alle Zeichen, wenn equals true zurückgibt und wesentlich weniger, wenn false zurückgegeben wird. Die tatsächliche Häufigkeit, mit der equals für eine bestimmte Schlüsselzeichenfolge aufgerufen wird, hängt davon ab, wie die Hash-Schlüsselzeichenfolgen verteilt sind. Normalerweise würden Sie erwarten, dass durchschnittlich 1 oder 2 Anrufe für einen "Treffer" gleich sind und bis zu 3 für einen "Fehlschlag".
Im Falle von List ruft ein Lookup equals für durchschnittlich die Hälfte der Entry Key Strings im Falle eines "hits" und alle im Falle eines "miss" auf. Wenn Sie die relative Verteilung der Schlüssel kennen, die Sie suchen, können Sie die Leistung im Trefferfall verbessern, indem Sie die Liste sortieren. Aber der Fall "Miss" kann nicht optimiert werden.
Zusätzlich zu der trie Alternative, die von @aioobe vorgeschlagen wird, könnten Sie auch einen speziellen String in die Ganzzahl hashmap implementieren, indem Sie a verwenden so genannte perfekte Hash-Funktion . Dies ordnet jede der tatsächlichen Schlüsselzeichenfolgen einem eindeutigen Hash innerhalb eines kleinen Bereichs zu. Der Hash kann dann zum Indizieren eines Arrays von Schlüssel / Wert-Paaren verwendet werden. Dies reduziert ein Nachschlagen auf genau einen Aufruf der Hash-Funktion und einen Aufruf von String.equals . (Und wenn Sie davon ausgehen können, dass der übergebene Schlüssel immer einer der abgebildeten Strings sein wird, können Sie auf den Aufruf von equals verzichten.)
Die Schwierigkeit des perfekten Hash-Ansatzes besteht darin, eine Funktion zu finden, die für die Menge der Schlüssel im Mapping funktioniert und nicht zu teuer für die Berechnung ist. AFAIK, muss dies durch Versuch und Irrtum erfolgen.
Aber die Realität ist, dass die Verwendung von HashMap eine sichere Option ist, weil sie O(1) performance mit einer relativ kleinen Proportionalitätskonstante angibt (es sei denn, die Eintrittsschlüssel sind pathologisch).
(FWIW, mein rate ist, dass der Break-Even-Punkt, an dem HashMap.get() besser wird als List.contains() kleiner als 10 ist, unter der Annahme, dass die Strings eine durchschnittliche Länge von% haben co_de% bis 5 .)
Soweit ich mich erinnern kann, ist die Listenmethode O (n), würde aber schnell Elemente hinzufügen, da keine Berechnung stattfindet. Sie könnten dieses niedrigere O (log n) erhalten, wenn Sie eine b-Suche oder andere Suchalgorithmen implementiert haben. Der Hash ist O (1), aber er ist langsamer einzufügen, da der Hash jedes Mal neu berechnet werden muss, wenn Sie ein Element hinzufügen.
Ich weiß in .net, Theres eine spezielle Sammlung namens HybridDictionary, die genau das tut. Verwendet eine Liste zu einem Punkt, dann einen Hash. Ich denke, die Frequenzweiche ist um 10, also kann das eine gute Linie im Sand sein.
Ich würde sagen, dass Sie in Ihrer obigen Aussage richtig sind, obwohl ich mir nicht 100% sicher bin, ob eine Liste für kleine Mengen schneller ist und wo der Kreuzungspunkt ist.
Ich denke, ein HashMap wird immer besser sein. Wenn Sie n strings jeder Länge höchstens l haben, dann sind String#hashCode und String#equals beide O(l) (in der Java-Implementierung sowieso).
Wenn Sie List#indexOf ausführen, durchläuft es die Liste ( O(n) ) und führt für jedes Element einen Vergleich durch ( O(l) ), um O(nl) performance zu erhalten.
Java HashMap hat (sagen wir) r Buckets und jeder Bucket enthält eine verkettete Liste. Jede dieser Listen hat die Länge O(n/r) (unter der Annahme, dass die Methode hashCode der Zeichenfolge die Strings gleichmäßig auf die Buckets verteilt). Um einen String nachzuschlagen, müssen Sie hashCode ( O(l) ) berechnen, den Bucket nachschlagen ( O(1) - one, nicht l ) und die verknüpfte Liste dieses Buckets durchlaufen ( O(n/r) elements) macht einen O(l) Vergleich für jeden. Dies ergibt eine Gesamtnachschlagezeit von O(l + (nl)/r) .
Da die List-Implementierung O(nl) ist und die HashMap-Implementierung O(nl/r) ist (Ich lasse die erste l fallen, da sie relativ unbedeutend ist), sollte die Lookup-Leistung gleich sein, wenn r=1 und die HashMap schneller sind für alle größeren Werte von r .
Beachten Sie, dass Sie r festlegen können, wenn Sie die HashMap mithilfe von dieser Konstruktor (setze das initialCapacity auf r und das loadFactor Argument auf n/r für deine gegebene n und ausgewählte r ) .
Tags und Links java performance data-structures big-o