Schnelligkeit einer Collection

[Gast]

Moin,

was sollte man verwenden wenn man viel in einer Collection sucht, ich schreibe nur einmal in die Collection und die übrige Aufgabe besteht aus suchen? List, ArrayList, Vector, Tree, Map???????

 

[SlaterB]

Map

 

[Beni]

Set? Wenn es nur um die Existenz eines Suchelementes geht.

 

[Kim Stebel]

TreeMap oder TreeSet, beide haben worst case-Zugriffszeiten von log(n).
Slater: Map ist nur das Interface, über die Performance entscheidet aber die Implementierung...

 

[Guest]

Set? Wenn es nur um die Existenz eines Suchelementes geht.

Es geht um eine Reihe von Suchoperationen und unter umständen sollte auch nach mehreren Einträgen hintereinander gesucht werden, so in der Art: Was ist nach einem Offset von xy in den nächsten 5 Einträgen vorhanden,

 

[tfa]

TreeMap oder TreeSet, beide haben worst case-Zugriffszeiten von log(n).

Was ist schlecht an HashMap oder HashSet? Damit kann man noch schneller Daten finden ( O(n)=1 ).

 

[Kim Stebel]

ach inserts spielen ja keine rolle..okay..

 

[SlaterB]

in jedem Fall verwendet das jeweilige Set intern eh die zugehörige Map

> Was ist nach einem Offset von xy in den nächsten 5 Einträgen vorhanden,

LinkedHashMap, wenn in korrekter Reihenfolge eingefügt,
wenn die Collection auch sortieren soll, wäre da wirklich ein Tree vorteilhaft, LinkedXYTree habe ich auf die Schnelle nicht in der API gesehen


wenn du mit Offset eh nur 'Element 37' meinst, dann wär natürlich ne List angebracht, ArrayList

 

[tfa]

Aber wenn die Reihenfolge eine Rolle spielt (wie hier offensichtlich), muss er wohl doch TreeMap nehmen.

 

[Beni]

Eine TreeMap sortiert ihren Inhalt nach dem Schlüssel, nicht nach der Einfügereihenfolge. Kommt jetzt natürlich draufan wie das mit diesen "nächsten 5 Einträgen" gemeint ist...

@Gast: beschreib doch mal das ganze Problem, dann kann man besser sagen was benötigt oder nicht benötigt wird.

 

[ARadauer]

um wie viele elemente gehts eigentlich ungefähr?

 

[Guest]

Es geht so um 30000-70000 Einträge (also Strings), ich verwende jetzt mal eine List<String>, funktioniert ganz gut

 

[Marco13]

Wenn es eine ArrayList ist, ist sowas wie
String s = list.get(50000);
schnell. Wenn es eine LinkedList ist, ist es u.U. gähnend langsam. Aber das ist ja einer der Gründe, warum man List verwendet, und nicht dediziert LinkedList oder ArrayList: Man kann nachher die Implementierung ändern, und schaun, was schneller ist...