Indizierte Stringsammlung in Java

Question

Verwendung von Java, vorausgesetzt v1.6.

Ich habe eine Auflistung, in der der eindeutige Index eine Zeichenfolge ist und der nicht eindeutige Wert eine Zahl ist. Ich muss Tausende von Abfragen anhand dieser Sammlung so schnell wie möglich durchführen.

Ich verwende derzeit eine HashMap<String, Integer> aber ich bin besorgt, dass die Boxing/unboxing der Integer zu int macht dies langsamer.

Ich hatte an die Verwendung eines ArrayList<String> gekoppelt mit einem int[] .

d.h. Statt:

int value = (int) HashMap<String, Integer>.get("key");

Ich könnte

int value = int[ArrayList<String>.indexOf("key")];

Haben Sie eine Idee? Gibt es einen schnelleren Weg, dies zu tun?

p.s. Ich werde die Sammlung nur einmal erstellen und sie vielleicht einmal ändern, aber jedes Mal werde ich die Größe kennen, so dass ich die String[] 代わりに ArrayList aber nicht sicher, ob es einen schnelleren Weg gibt, indexOf zu replizieren...

Answer 1

Das Auspacken geht schnell - es sind keine Zuweisungen erforderlich. Boxing ist potenziell langsamer, da es ein neues Objekt zuweisen muss (es sei denn, es wird ein gepooltes Objekt verwendet).

Aber sind Sie sicher, dass Sie wirklich ein Problem haben? Machen Sie Ihren Code nicht komplizierter, bevor Sie nicht bewiesen haben, dass es sich um einen signifikanten Schaden handelt. Ich bezweifle sehr, dass es das ist.

Es gibt Sammlungsbibliotheken für primitive Typen, aber ich würde bei der normalen HashMap aus der JRE bleiben, bis Sie ein Profil erstellt und überprüft haben, dass dies ein Problem verursacht. Wenn es sich wirklich nur um Tausende von Lookups, ich bezweifle sehr, dass es überhaupt ein Problem sein wird. Ebenso, wenn Sie Lookup-basierte eher als Addition-basierte (dh Sie holen häufiger als Sie hinzufügen), dann die Boxing Kosten wird nicht besonders signifikant sein, nur unboxing, die billig ist.

Ich würde vorschlagen, dass Sie intValue() statt des Casts zur Umwandlung des Wertes in eine int Aber es macht (IMO) klarer, was vor sich geht.

EDIT: Um die Frage in dem Kommentar zu beantworten, HashMap.get(key) wird schneller sein als ArrayList.indexOf(key) wenn die Sammlung groß genug ist . Wenn Sie tatsächlich nur fünf Punkte haben, kann die Liste durchaus schneller sein. Ich nehme aber an, dass das nicht wirklich der Fall ist.

Wenn Sie wirklich keine Lust auf das Einpacken und Auspacken haben, versuchen Sie Trove (TObjectHashMap). Außerdem gibt es COLT aber ich konnte dort nicht den richtigen Typ finden.

Answer 2

Jeder Leistungsgewinn, der sich daraus ergibt, dass Sie nicht boxen/unboxen müssen, wird durch die for-Schleife, die Sie mit der indexOf-Methode durchführen müssen, wieder zunichte gemacht.

Verwenden Sie die HashMap. Auch brauchen Sie nicht die (int) Cast, der Compiler wird es für Sie übernehmen.

Die Array-Sache wäre in Ordnung mit einer kleinen Anzahl von Elementen in das Array, aber dann so ist die HashMap...

Die einzige Möglichkeit, schnell in einem Array nachzuschauen (und das ist no ein echter Vorschlag, da es zu viele Probleme gibt) ist, wenn Sie den HashCode des Strings als Index in das Array verwenden - denken Sie aber nicht einmal daran, das zu tun! (Ich erwähne es nur, weil Sie vielleicht etwas über Google finden, das darüber spricht... wenn dort nicht erklärt wird, warum es schlecht ist, lesen Sie nicht weiter darüber!)

Answer 3

Ich würde vermuten, dass die HashMap eine viel schnellere Suche bieten würde, aber ich denke, dass dies einige Benchmarking braucht, um richtig zu beantworten.

EDIT: Außerdem wird kein Boxing durchgeführt, sondern nur das Unboxing der bereits gespeicherten Objekte, was ziemlich schnell sein sollte, da in diesem Schritt keine Objektzuweisung erfolgt. Ich glaube also nicht, dass Sie dadurch mehr Geschwindigkeit erreichen, aber Sie sollten trotzdem Benchmarks durchführen.

Answer 4

Ich denke, Scannen Ihre ArrayList, um die Übereinstimmung für Ihre "Schlüssel" zu finden, wird viel langsamer als Ihre Boxing/unboxing Bedenken sein.

Answer 5

Da Sie sagen, dass dies tatsächlich ein Engpass ist, schlage ich vor Primitive Sammlungen für Java ; insbesondere die ObjectKeyIntMap sieht genau nach dem aus, was Sie wollen.