ArrayList schneller als LinkedHashMap?

[Friedhelm]

Hallo,

Wie ist Eure Erfahrung mit LinkedHashMap und ArrayList bzgl. der Geschwindigkeit?

Ich habe eine Liste mit ca. 1000 Objekten. Dabei ist mir aufgefallen, dass wenn ich die Liste komplett durchlaufe, ist ArrayList immer noch schneller als mit einer LinkedHashMap.


Beispiel ArrayList:
ArrayList<Box> boxes = new ArrayList<Box>();
for(int i=0;i<boxes.size();i++) System.out.println(boxes.boxname);


Beispiel LinkedHashMap:
Enumeration e = boxes.keys();
while (e.hasMoreElements()) {
String name = (String)e.nextElement();
System.out.println(name + " --> " + boxes.get(name).boxname );
}


Problem ist aber... wegen der Geschwindigkeit müsste ich somit eine ArrayList verwenden, wenn die ganze Liste durchlaufen werden soll. Nur ist ja wohl eine LinkedHashMap viel schneller, wenn ich nur 1 Objekt aus den 1000 erhalten möchte ( boxes.get("Boxname") )

Grund ist... es sind OpenGL Boxen die 60 Mal in der Sekunde neu gezeichnet werden sollen, aber ich auch einzelne Objekte aus der Liste suchen lasse.

1. Soll ich trotz des Geschwindigkeitsverlustes (ca. 5-8 FPS von 60 FPS) eine LinkedHashMap verwenden?
2. Lohnt sich eine LinkedHashMap nicht bei max. 25 Objekten in der Liste (ist dann eine ArrayList immer noch bei einem Komplett-Suchdurchlauf schneller)?

Wäre die beste Lösung man führt 2 Listen parallel, eine LinkedHashMap (für gezielte Objektsuche) und eine ArrayList für komplette Druchläufe, oder gibt es noch eine bessere Lösung für mein Problem?

 

[LoR]

//Edit gelöscht

 

[Friedhelm]

Problem gelöst.

Ich habe einfach eine HashMap in die ArrayList eingebaut. Funktioniert super 🙂

 

[Marco13]

Enumeration ist eigentlich veraltet, man sollte stattdessen Iteratoren verwenden. Abgesehen davon ist es natürlich ganz schlecht, über die keys zu iterieren, und für jeden Key nochmal einen Lookup für die value zu machen! Statt des geposteten Codestücks solltest du eher

        LinkedHashMap<String, Integer> m = new LinkedHashMap<String, Integer>();
        for (Entry<String, Integer> entry : m.entrySet())
        {
            System.out.println(entry.getKey()+" -> "+entry.getValue());
        }

machen. Das könnte dann u.U. immernoch etwas langsamer sein als bei einer ArrayList, aber was dort gemacht wird ist dann eigentlich das gleiche wie bei einer LinkedList, d.h. der Unterschied dürfte nicht mehr so dramatisch sein.

 

[Friedhelm]

Ja, das könnte hinhauen. Bei der LinkedHashMap hat mich bei der Schleife immer gestört, dass für jedes Element die Value erst über den Key geholt werden muss.

Aber die Lösung die ich habe, mit der HashMap die den Namen des Objektes mit der Indexposition des Objektes in der ArrayList speichert, finde ich doch noch einen Tick optimaler 😀

So habe ich FullSpeed aber auch gezielt und schnell ein Objekt aus 1000 parat.

 

[Marco13]

Eigentlich würde man das ja testen, ggf. mit einem Profilerlauf. Aber wenn man unbedingt indizierten Zugriff UND Map-Lookups braucht, kann man das natürlich machen. Oft gibt es einen Tradeoff zwischen Speicherplatzbedarf und Geschwindigkeit, aber bei 1000 Elementen in einer zeitkritischen Anwendung würde man wohl eher auf letztere Wert legen.

 

[maki]

An dieser Stelle sei auch FindBugs empfohlen, das findet u.a. solche Stellen und meldet sie:

Enumeration e = boxes.keys();
while (e.hasMoreElements()) {
String name = (String)e.nextElement();
System.out.println(name + " --> " + boxes.get(name).boxname );
}

 

[Ullenboom]

LinkedHashMap und ArrayList haben zwei völlig unterschiedliche Aufgaben.

a) wenn du schnell assoziierte Werte zu einem Schlüssel haben möchtest: HashMap

b) wenn du die Reihenfolge beim Einfügen brauchst und auf Postionen zurückgreifen möchtest: ArrayList

c) wenn die Reihenfolge UND schneller Schlüsselzugriff nötig ist, nutzte LinkedHashMap. Diese Doppelfunktion hat aber ihren Preis

Demnach: Wenn nur die Reihenfolge wichtig ist, bzw. vielleicht das sogar nicht, sondern einfach nur ein Container zu ablaufen, dann ist ArrayList die beste Wahl. (Vorher mit der Größe vorbelegen.)

Grüße

Christian

 

[Marco13]

d) Wenn Reihenfolge, schneller Schlüsselzugiff UND indizierter Zugriff nötig ist, bist du gescrewed 😀

Dann muss man sich eben was überlegen...

EDIT: Ach, indizierter Zugriff wird hier gar nicht gebraucht... da hab' ich wohl den Thread verwechselt 😳 Aber wie es mit LinkedHashMap gehen würde, steht ja oben schon 🙂