ArrayList oder LinkedList?

[Novanic]

Hi Leute,

bisher habe ich eigentlich immer konsequent ArrayList verwendet. Nun habe ich aber erfahren, dass die LinkedList bei Hinzufügen/Entfernen performanter, im Direktzugriff aber langsamer sein soll. Gilt der Direktzugriff nur für die Methode "Object get(Object o)" oder auch für den Iterator?

Wäre es dann sinnvoll auf die LinkedList umzusteigen, wenn ich nur den Iterator verwende oder gibt es noch performantere Collections als ArrayList und LinkedList?

Danke schonmal im Voraus!

Gruß Nova

 

[SlaterB]

jo, bei get wird die Liste von Anfang oder Ende aus durchlaufen,
beim Iterator von Element zu Element gesprungen

was nun das performanteste ist
(z.B. Vergleich ArrayList get(i) <-> LinkedList Iterator)
ist müßig herauszufinden,
wenn dir was daran liegt, dann teste es selber
(eine Frage hier ist natürlich berechtigt)

wichtiger erscheint mir, die LANGSAMEN Stellen zu umgehen,
also nicht große LinkedList mit get(i) durchlaufen und auch nicht in ArrayList ständig einfügen/ entfernen,
wenn man das richtig gemacht hat, müsste man doch >90% der Performanz erreicht haben, der Rest ist nicht mehr so wichtig

(Meinung, kein Wissen )

 

[byte]

Das musst Du von Fall zu Fall entscheiden, welche dieser Listen besser ist. ArrayList wird intern durch ein Array realisiert und hat somit schnellere Zugriffszeiten. Als Konsequenz bedeutet das aber, dass das interne Array zunächst eine feste Maximalgröße bekommt. Wenn Du jetzt immer mehr Elemente hinzufügst, muss das Array irgendwann intern vergrößert werden. Dann leidet die Performance. Dieses Problem hast Du bei der LinkedList nicht. Die wird halt einfach als verkettete Liste realisiert.

Lange Rede kurzer Sinn: Wenn Du weisst, dass nur maximal n Elemente in der Liste sein werden, dann nimm eine ArrayList. Dabei kannst Du auch schon die maximale Größe mitgeben. Wenn die Anzahl der Elemente in der Liste beliebig ist, dann bietet sich eine LinkedList an.

 

[Marco13]

LinkedList:

add: O(1)
remove: O(n)
indexOf: O(n)
get: O(n)

ArrayList:

add: O(1)
remove: O(n)
indexOf: O(n)
get: O(1)


Der einzige relevante Unterschied ist der direkte Zugriff auf ein Element mit "get(index)": Dort ist die ArrayList schneller. Ansonsten ist theoretisch kein Unterschied (und praktisch ist der Unterschied vmtl. vernachlässigbar)

EDIT: Ark hatte Recht, die Zeiten bei "get" waren vertauscht (im abschließenden Satz stand's dann aber richtig)

 

[Ark]

@Marco13: Ist das nicht gerade genau anders herum? ???:L

Ark

 

[SlaterB]

zumindest das
LinkedList:
remove: O(n)
finde ich doch recht fraglich,
müssen nicht einfach zwei Referenzen aktualisiert werden?

gut, die Position muss gefunden werden, aber fällt das nicht an dieser Stelle weniger ins Gewicht als das Kopieren bei
ArrayList:
remove: O(n)
?

kommt natürlich immer drauf an, wie man die Elemente bestimmt, an welche Stelle sie stehen usw.,
ein Beispiel von mir:

public class Test2
{
    public static void main(String[] args)
        throws Exception
    {
        ArrayList<Integer> zahlen = new ArrayList<Integer>(1000);

        ArrayList<Integer> a = new ArrayList<Integer>(1000);
        LinkedList<Integer> l = new LinkedList<Integer>();
        for (int i = 0; i < 1000; i++)
        {
            Integer integer = Integer.valueOf(i);
            zahlen.add(integer);
            a.add(integer);
            l.add(integer);
        }
        Collections.shuffle(zahlen);

        testRemove(l, zahlen);
        testRemove(a, zahlen);
        testRemove(l, zahlen);
        testRemove(a, zahlen);
    }


    public static void testRemove(List<Integer> l, List<Integer> zahlen)
    {
        long time = System.currentTimeMillis();
        Integer integer = null;
        for (int i = 0; i < 10000; i++)
        {
            for (int j = 0; j < 1000; j++)
            {
                integer = zahlen.get(j);
                l.remove(integer);
                l.add(integer);
            }
        }
        long diff = System.currentTimeMillis() - time;
        System.out.println("time: " + diff + ", for List: " + l.getClass().getSimpleName());
    }
}

->
time: 813, for List: LinkedList
time: 10859, for List: ArrayList
time: 766, for List: LinkedList
time: 10860, for List: ArrayList

 

[Marco13]

Ja, das Kopieren bei remove benötigt natürlich Zeit - genauso wie das Vergrößern des Arrays bei "add". Trotzdem ist die Zeit asymptotisch linear. (Wenn beim Einfügen die Kapazität immer um 1 erhöht werden würde, hätte das Einfügen von n Elementen z.B. auch eine Quadratische Laufzeit). Aber schließlich müssen bei einem remove aus einer Liste mit n Elementen höchstens n Elemente kopiert werden, und damit ist und bleibt es O(n). Dass in der Praxis der konstante Faktor relevant sein kann, sollte man vielleicht nochmal hervorheben.

Und wie repräsentativ/verläßlich dein Testprogramm (mit add und remove!) ist, ist eine andere Frage... :wink:

import java.util.*;

public class Test2
{
    public static void main(String[] args)
        throws Exception
    {
        ArrayList<Integer> zahlen = new ArrayList<Integer>(10000);

        ArrayList<Integer> a = new ArrayList<Integer>(10000);
        LinkedList<Integer> l = new LinkedList<Integer>();
        for (int i = 0; i < 10000; i++)
        {
            Integer integer = Integer.valueOf(i);
            zahlen.add(integer);
            a.add(integer);
            l.add(integer);
        }
        Collections.shuffle(zahlen);

        testRemove(l, zahlen);
        testRemove(a, zahlen);
        testRemove(l, zahlen);
        testRemove(a, zahlen);
    }


    public static void testRemove(List<Integer> l, List<Integer> zahlen)
    {
        long time = System.currentTimeMillis();
        Integer integer = null;
        for (int i = 0; i < 100; i++)
        {
            for (int j = 0; j < 1000; j++)
            {
                integer = zahlen.get(j);
                l.remove(integer);
                l.add(integer);
            }
        }
        long diff = System.currentTimeMillis() - time;
        System.out.println("time: " + diff + ", for List: " + l.getClass().getSimpleName());
    }
}

Ausgabe:

time: 12407, for List: LinkedList
time: 10875, for List: ArrayList
time: 12593, for List: LinkedList
time: 10891, for List: ArrayList

 

[SlaterB]

gemein, den Suchaufwand durch die Länge der Liste so hochzutreiben

 

[Marco13]

Man könnte die Tests auch an einelementigen Listen machen :wink: Das ist im wesentlichen das Prinzip von "LSORT", einem Sortierprogramm, das in konstanter Zeit läuft, also O(1) hat. Es wurde am Fachbereich für Ineffiziente Algorithmen und Datenstrukturen an der Rautavistischen Universität Eschweilerhof entwickelt:

http://ru-eschweilerhof.de/cs/fb17/algodat/vortrag/img15.html

 

[Wildcard]

Solche Tests halte ich für irreführend.
Wer sagt mir denn das der Hot Spot Compiler

          for (int j = 0; j < 1000; j++)
            {
                integer = zahlen.get(j);
                l.remove(integer);
                l.add(integer);
            }

In VM xy nicht zum wesentlich günstigeren Iterator (dann man immer verwenden sollte) umbaut?

 

[SlaterB]

meinst du zahlen.get(j)?
das ist doch nicht Bestandteil des Tests,
wenn es umgebaut wird, dann für beide Listen gleich, eh egal

 

[Marco13]

Wer sagt mir denn das der Hot Spot Compiler [...] In VM xy nicht zum wesentlich günstigeren Iterator [...] umbaut?

Das sagt einem ein Test, bei dem man den JIT mal abschaltet.

(dann man immer verwenden sollte)

Warum? Jedenfalls ist er beim reinen Durchlaufen langsamer als eine for-Schleife - egal ob mit JIT oder ohne....

 

[Wildcard]

Warum? Jedenfalls ist er beim reinen Durchlaufen langsamer als eine for-Schleife - egal ob mit JIT oder ohne....

Aber nicht bei einer LinkedList die sequentiell durchlaufen werden soll. Daher sollte man ja immer den Iterator oder die foreach Schleife nehmen, denn wenn man sich an den Grundsatz 'Zum Interface hin zu programmieren' hält, ist die dahinterliegende Implementierung der List in den meisten Fällen unbekannt.

 

[Wildcard]

meinst du zahlen.get(j)?
das ist doch nicht Bestandteil des Tests,
wenn es umgebaut wird, dann für beide Listen gleich, eh egal

Nicht egal. Die ArrayList wird mit dem Iterator eventuell minimal langsamer, während die LinkedList viel schneller wird.

 

[SlaterB]

aber zahlen.get(j) ist IMMER eine ArrayList und wird nur nebenbei ZUM Test benutzt,
ist nicht Teil des Tests

 

[Wildcard]

aber zahlen.get(j) ist IMMER eine ArrayList und wird nur nebenbei ZUM Test benutzt,
ist nicht Teil des Tests

grml grml .... stimmt... :wink: