Kleine Mengen in Java: Welche Datenstruktur?

9

Gibt es eine gute Referenz oder kann mir jemand mehr über die Leistung verschiedener Java-Implementierungen auf kleinen -Sätzen (etwa 1-100 Elementen) erzählen? Die Geschichte von O (1) vs O (log n) ist für diese Größen ziemlich irrelevant, aber da ich mit Millionen dieser kleinen Sätze umgehen muss, spielt die Leistung sicherlich eine Rolle. Die meisten Referenzen, die ich finde, erwähnen nicht viel darüber.

Ich würde folgendes mit diesen Sets machen müssen (nur ein paar Mal pro Set):

  • initialisiere einen neuen Satz und / oder kopiere einen alten
  • Elemente hinzufügen / entfernen
  • über die Menge iterieren
  • Berechnung der hashCode() der gesamten Menge

Ich denke, dies sind die praktikablen Optionen zum Vergleichen (angenommen, dass Vergleich / Hashing T fast frei ist):

  • HashSet & lt; T & gt; : scheint beim Iterieren schlecht zu sein (und daher bei hashCode() )
  • TreeSet & lt; T & gt; : scheint einen lächerlich hohen Overhead zu haben
  • LinkedHashSet & lt; T & gt; : Keine Erfahrung damit, hat es einen hohen Aufwand?
  • ArrayList & lt; T & gt; : schnell an sich, aber kein Set, so hässliche Tricks wie Collections.sort() benötigt ...

Welches der oben genannten wird im Allgemeinen bevorzugt? Oder sollte ich meine eigene SmallSet<T> Klasse schreiben?

    
user1111929 10.09.2012, 06:48
quelle

2 Antworten

3

Wenn Sie wirklich nach Leistung suchen, dann gibt es nichts weniger als das Testen für sich selbst, das Ihnen hier helfen wird:

  • Ordnen Sie sie ständig neu zu? Wenn dies der Fall ist, ist die Speicherbereinigung möglicherweise relevanter als in anderen Fällen
  • Ordnen Sie sie einmal zu und benötigen schnellen Zugriff? Hashcollisions wirken sich auf das
  • aus
  • Änderst du sie ständig?

Sie müssen einen Testfall einrichten, der Ihrer tatsächlichen Verwendung ähnlich ist - testen Sie lange genug, dass GC einsetzt und Sie die Effekte dort sehen.

Wenn Sie kritische Unterschiede feststellen, führen Sie die Tests nach jeder Aktualisierung der JVM erneut aus, da sich die Implementierungen möglicherweise ändern.

Bis Sie solche Leistungstests durchgeführt haben, gebe ich meinen Standardratschlag: Wählen Sie die beste lesbare Option und ändern Sie sie nur dann, wenn Sie deutliche Vorteile aus der Verwendung einer weniger lesbaren Option ziehen. Die Code-Betreuer (möglicherweise ein zukünftiger Sie) werden Ihnen dafür danken.

    
Olaf Kock 10.09.2012 06:54
quelle
0

Dies ist eine kleine Set-Implementierung als Arrays:

Es ist so einfach, sich an Ihre Bedürfnisse anzupassen:)

Quelle: Ссылка

%Vor%     
Yan King Yin 08.12.2014 21:37
quelle

Tags und Links