Datentypen Große, sortierte, schnelle Datenstruktur

[Povlsen84]

Hallo,

ich suche eine Datenstruktur, die viele (100k) Objekte aufnehmen kann, sortiert ist und möglichst effektiv einfügen und löschen kann.

Die bisher getesteten (TreeSet, Vector, ...) scheitern bei diesen Anforderungen an der Laufzeit oder dem Speicher

lG,
Stephan

 

[moormaster]

Erstens: Vector sortiert nicht.
Zweitens: Was stört dich an der Laufzeit?

TreeSet (Java Platform SE 6)

Die Einfügeoperation hat eine Komplexität von O(log n) Schritten... genauso das auffinden oder löschen eines Elementes aus dem TreeSet...

Wenn du Probleme mit dem Speicherplatz hast, solltest du vielleicht mal die HeapSize der VM vergrößern?

 

[Schumi]

Der Speicherverbrauch hängt wohl weniger von der haltenden Datenstruktur als mehr von der zu haltenden Datenstruktur selber ab.

 

[ThreadPool]

Erstens: Vector sortiert nicht.
Zweitens: Was stört dich an der Laufzeit?

TreeSet (Java Platform SE 6)

Die Einfügeoperation hat eine Komplexität von O(log n) Schritten... genauso das auffinden oder löschen eines Elementes aus dem TreeSet...

Die Komplexität mag asymptotisch so aussehen nur wenn ich mich recht entsinne sagt das jetzt nichts über die Kosten der Schritte selbst aus, da wird IMHO nur unterstellt das die endlich und in konstanter Zeit abzulaufen haben. Das TreeSet ansich bringt etwas Overhead mit da es ein "Wrapper" für eine TreeMap ist. Die TreeMap ist wiederum durch einen Rot-Schwarz-Baum implementiert, also einen höhenbalancierten Baum. Das Ausbalancieren selbst kostet ja auch nicht Nichts, fällt natürlich mit unter den Worstcase O(log n) aber ein gewisser Faktor ist es IMHO. [1]

Vor ein paar Jahren hatten wir auch mal was mit TreeSet versucht, schneller waren wir im Endeffekt durch eine einfache ArrayList mit einfacher binärer Suche [2] zum Einfügen und sortiert Halten.

[1] Komplexitätstheorie war noch nie meine Stärke, groben Unfug bitte korrigieren.
[2] verwendet wurde eine Eigene nicht die aus der Arrays-Klasse

 

[faetzminator]

[2] verwendet wurde eine Eigene nicht die aus der Arrays-Klasse

Du willst damit sagen, dass dein Sortieralgo schneller ist als jener, welcher sich in der Standard API befindet :lol:?

 

[ThreadPool]

Du willst damit sagen, dass dein Sortieralgo schneller ist als jener, welcher sich in der Standard API befindet :lol:?

Wenn du richtig gelesen hättest dann wäre dir nicht entgangen das ich von der binären Suche spreche. Tatsache ist das der Algorithmus vom Ablauf identisch ist nur eben angepasst auf die Datenobjekte welche wir verwendet haben.

 

[faetzminator]

Also hat er auch die gleiche Laufzeit Ausser, dass in der Standard API nicht zwingend Binary Search verwendet wird (z.B. bei kleinen Datenmengen) - da ist mein Stand allerdings nicht allzu aktuell.

 

[ThreadPool]

Also hat er auch die gleiche Laufzeit Ausser, dass in der Standard API nicht zwingend Binary Search verwendet wird (z.B. bei kleinen Datenmengen) - da ist mein Stand allerdings nicht allzu aktuell.

Wenn der Compiler garantieren kann das die compare-Funktion des Comparators geinlined wird dann hast du recht. Andernfalls habe ich immernoch weniger Overhead, da ich diese Funktion nicht aufrufe und glücklicherweise durch etwas Trickserei die Sortierschlüssel auf Longs abbilden konnte. Was dann in einem stumpfen Ganzahlvergleich endet. Aber das is hier Off-Topic.

 

[faetzminator]

Jaja, schon ok

 

[fastjack]

Also ich habe bei größeren Datenimporten sehr gute Erfahrungen mit TreeMap und Vector/ArrayList gemacht. Größere bedeutet mehrere Millionen Datenzeilen, die als Objekte verpackt in einer der obigen solchen Strukturen lagen.
Bei der Bearbeitung habe ich meistens darauf geachtet, wenn möglich, das fertig behandelte Element aus der Liste zu entfernen. Meistens war das eine Kombi von get(0)/remove(0) n-Mal. Gepaart mit einer Empfehlung an die VM eine GC zu machen, beispielsweise nach tausend Objekten. Das lief bisher immer gut.
Hauptspeicherprobleme traten bei großen Mengen natürlich auch auf, doch die Schalter Xmx und Xmx sollten helfen (Windowsmaschinen verkraften hier so um 1GB, server-Option der VM setzen). Bei einem früheren besonders heftigen Einmalimport reichte dieses GB auch nicht mehr aus. Da ich als Arbeitsrechner FreeBSD hatte, mit nem Diablo-Java (hat keine Speicherbeschränkung bei Xmx, Xms) und genügend RAM, konnte ich den Speicher auf knapp 2,4GB anheben --> Import kein Problem
Suchoperationen in Listen sind bei deratigen Mengen natürlich anstrengend, aber es ja Maps