LinkedList 33x schneller als ArrayList oder “Kenne deine API!”

Für meine Arbeit schreibe ich zum Test gerade ein kleines Plugin für ImageJ, indem ich unter anderem einen Region-Fill Algorithmus brauche – leider tut’s der filler von ImageJ hier nicht – also schnell was selbst zusammengehackt:

Startpunkt initialisieren und in eine Liste damit
while (Liste nicht leer) {
   hole ersten Punkt P aus der Liste
   prüfe Eigenschaften von p.x/p.y auf dem Bild
   if (Eigenschaften erfüllt){
      füge der Liste die Punkte darüber, darunter, rechts und links hinzu
   }
}

Vorher eine ArrayList entsprechend groß initialisiert, damit die nicht dynamisch wachsen muss und gut ist’s.

Moment – in vielen Iterationen werden hinten an der Liste 4 Punkte angefügt. Das geht mit der ArrayList schön schnell, wie man im ArrayList Quellcode unschwer erkennt (wenn die Liste groß genug ist). Aber in jeder Iteration wird vorne das erste Element entnommen. – Ein Blick in den ArrayList-Quellcode offenbart ein “System.arraycopy(elementData, index+1,  elementData, index, numMoved);“. Oha – das riecht eigentlich eher nach einer LinkedList.

Also: Methode profilen, Listentyp ändern, nochmal profilen (mit dem NetBeans Profiler ja kein Thema). Ergebnis: LinkedList ist wie erwartet viel schneller. Ohne meinen ganzen sonstigen Code reduziert sich der Testfall in etwa auf folgende Testklasse:

public class ListTest {

    public static void main(String[] args) {
        List al = new ArrayList(31000);
        List ll = new LinkedList();
        long a = System.currentTimeMillis();
        testWith(al);
        long b = System.currentTimeMillis();
        testWith(ll);
        long c = System.currentTimeMillis();

        System.out.println("ArrayList: "+(b - a) + " ms");
        System.out.println("LinkedList: "+(c - b) + " ms");
    }

    private static void testWith(List list) {
        list.add(new Point(0, 0));
        int i = 10000;
        Point p;
        while (!list.isEmpty()) {
            p = list.remove(0);
            if (i-- > 0) {
                list.add(new Point(p.x, p.y - 1));
                list.add(new Point(p.x - 1, p.y));
                list.add(new Point(p.x + 1, p.y));
                list.add(new Point(p.x, p.y + 1));
            }
        }
    }
}

Das Speedstepping am Notebook nicht vergessen, sonst fährt die CPU am anfang ja noch nicht auf Vollgas und schon rennt der Test. Die ArrayList habe ich auch extra noch mit mehr Elementen initialisiert, als jemals reinkommen. Ausserdem geht die Initialisierung auch nicht in die Messung ein (ist im Vergeich mit dem Rest zwar eh vernachlässigbar klein, aber damit niemand auf die Idee kommt, der Vergleich wäre unfair …).

Ausgabe:
ArrayList: 860 ms  = 100%
LinkedList: 31 ms  = 3,6%

Sieht man sich die API und den Quellcode der beiden Klassen an, verwundert das Ergebnis nicht wirklich. Der unterschied skaliert natürlich auch mit der Anzahl der Iterationen.


Fazit

Ist ArrayList also schlecht? – Klares NEIN! Nur für genau diesen Anwendungfall (vielfaches Einfügen am Ende, vielfaches Herausnehmen am Anfang, kein Zugriff auf Elemente irgendwo dazwischen nötig) ist die ArrayList der Speicherstruktur der LinkedList einfach unterlegen, die genau auf diesen Punkten optimal funktioniert.

Ergo: Know your API! Man sollte sein Handwerkszeug kennen und nicht blindlings einfach das verwenden was man sonnst auch immer nimmt und hoffen, dass Java ein allmächtiges Werkzeug ist, das einem alle Arbeit abnimmt (und dann nacher groß jammern, dass in C++ ja eh alles viel schneller geht). Und wenn man Zweifel hat, ruhig mal einen Blick in den Sourcecode werfen und ausprobieren 😉