Frage Performance bei Linked List und Array List

[8u3631984]

Hallo zusamen :
Ich habe auf Youtube folgendes Video zum Thema LinkedList und ArrayList mir angesehen :

Ich wollte die Performance in einem kleinem Java Programm messen :
Dazu will ich in eine ArrayList und LinkedList jeweils die gleiche Anzahl von Elementen einfügen und wieder löschen. Nach meinem Verständnis sollte die Linked List deutlich schneller sein.

Hier ist mein Programm :

    public static int numberOfElements = 10000000;
    public static int numberOfActions = 100;

    /**
     * @param args
     */
    public static void main(String[] args) { 
        System.out.println("erzeuge ein ArrayList mit " + numberOfElements + " Elementen");
        ArrayList<Integer> myArrayList = new ArrayList<>();
        listAction(myArrayList);

        System.out.println("--------------------------------");

        System.out.println("erzeuge ein LinkedList mit " + numberOfElements + " Elementen");
        LinkedList<Integer> myLinkedList = new LinkedList<>();
        listAction(myLinkedList);
    }

    public static long actionAddElements(List<Integer> myList){
        var startTimeStamp = System.currentTimeMillis();
        for (int i = 0; i < numberOfElements; i++){
            myList.add(i);
        }
        var endTimeStamp = System.currentTimeMillis();
        var duration = endTimeStamp - startTimeStamp;

        return duration;
    }

    public static long actionRemoveElemnts(List<Integer> myList){
        var startTimeStamp = System.currentTimeMillis();
        for (int i = numberOfElements - 1 ; i >= 0 ; i--){
            myList.remove(i);
        }
        var endTimeStamp = System.currentTimeMillis();
        var duration = endTimeStamp - startTimeStamp;

        return duration;
    }

    public static void listAction(List<Integer> myList){
        long durationAdd = 0;
        long durationRemove = 0;

        for (int i = 0; i < numberOfActions; i++){
            durationAdd += actionAddElements(myList);
            durationRemove += actionRemoveElemnts(myList);
        }

        System.out.println("dauer einfügen " + durationAdd / numberOfActions);
        System.out.println("dauer löschen " + durationRemove / numberOfActions);
    }

Kurz zur Erklärung : In meinen ersten Versuchen war die ArrayList immer schneller. Dher habe ich das Programm umgebaut. Nun werden die Aktionen 100x ausgeführt und der Mittelwert der Zeit zum Hinzufügen und Löschen gebildet :

hier die ausgabe :

erzeuge ein ArrayList mit 10000000 Elementen
dauer einfügen 51 ms
dauer löschen 11 ms
--------------------------------
erzeuge ein LinkedList mit 10000000 Elementen
dauer einfügen 848 ms
dauer löschen 104 ms

Hat jemand eine erklärung dafür

 

[Robert Zenz]

Ich habe mir jetzt das Video nicht angesehen, aber eine ArrayList zu schlagen wenn sie nicht das Array erweitern muss wird sehr schwierig werden. Im Groszen und Ganzen ist ein Hinzufuegen in der ArrayList naemlich:

public void add(LIST_TYPE item) {
    int newCount = count + 1;

    if (newCount >= array.length) {
        array = grow(count * 2);
    }
 
    array[count] = item;

    count = newCount;
}

Also wirklich, wirklich billig wenn nicht das Array vergroeszert werden muss. Dagegen muss in einer LinkedList ein paar Sachen gemacht werden wenn sich das letzte Element aendert.

Hinzu kommt noch dass dein Test-Aufbau ein paar Probleme, zu naechst naemlich Auto-Boxing und dann wahrscheinlich ein Speicherproblem.

Waehrend die Operationen auf der ArrayList sehr billig moeglich sind, insbesondere in dem Moment wo das interne Array einmal grosz genug erweitert worden ist, ist es wirklich nur ein "wie schnell kann ich Elemente in ein Array setzen". Die LinkedList muss mindestens ein neues Objekt je Hinzufuegen erzeugen, erzeugt also 1.000.000.000 Objekte welche auch wieder verworfen werden muessen. Dein Test ist so also nicht aussagekraeftig weil dir irgendwann die Garbage Collection einen Strich durch die Rechnung machen wird. Hinzu kommt dann noch das Auto-Boxing welches ebenfalls Objekte erzeugt welche wieder verworfen werden. Alles nicht ideal, dann fuehrst du beide Tests noch in der selben JVM aus, also der LinkedList-Test "erbt" schonmal einen Speicher der mit Dingen belegt ist.

Im ersten Schritt wuerde ich die Element durch eine fixe Object Instanz ersetzen.

private static final Object ELEMENT_INSTANCE = new Object();

// ...

for (int i = 0; i < numberOfElements; i++){
    myList.add(ELEMENT_INSTANCE);
}

Damit nimmst du hier schonmal unnoetige Objekt-Instanzen raus.

Du kannst dir auch jeder Zeit den Quellcode von ArrayList und LinkedList ansehen, dann kannst du das selbst vermutlich besser verstehen.

 

[LimDul]

https://www.reddit.com/r/javahelp/comments/whnih5

Dein Test macht eine extrem günstig Operation auf die ArrayList - am Ende etwas hinzufügen.

Zudem kommt noch Boxing/Unboxing ins Spiel und der Overhead bei einer LinkedList, dass da immer Objekte erzeugt werden mit Referenzen.

 

[8u3631984]

Vielen dank für die erklärung.

Ich habe nun mal folgende Änderunge vorgenommen :
Ein kleines eigenes Objekt verwendet und ab einer Größe > 2 immer an der zweiten Position einfügen. Nun bekomme ich folgende Ergebnisse :
erzeuge ein ArrayList mit 500000 Elementen
dauer einfügen 13522 ms
dauer löschen 1 ms
--------------------------------
erzeuge ein LinkedList mit 500000 Elementen
dauer einfügen 10 ms
dauer löschen 3 ms

Nun ist der UNterschied deutlicher !!!

 

[mihe7]

dauer löschen 1 ms

Löschst Du noch vom letzten zum ersten Element?

 

[LimDul]

Der Thread ist übrigens ein perfektes Beispiel, warum Performance-Messungen so schwierig sind (Wir misst misst Mist).

Es ist immer die Frage - was messe ich eigentlich? Messe ich den Code, den ich messen will? Oder messe ich was anderes? Was ist eigentlich mein Szenario? Was sind eigentlich die Rahmenbedingungen.

Wie man hier sieht, spielt so viel eine Rolle:

• Werden die Elemente neu erzeugt oder nicht?
• Garbage Collection
• Wo werden die Elemente eingefügt
• Wie werden die Elemente gelöscht

Dann nehmen wir noch hinzu:

• Speichermanagement der JVM
• JIT-Compiler
• Optimierungen der CPU

Am Ende am zwar zwei Zeiten die man vergleichen kann - aber kann man sie auch übertragen auf was anderes? Spätestens da wird es schwer.