Warum eine ArrayList mit einer anfänglichen Kapazität starten?

149

Der übliche Konstruktor von ArrayListist:

ArrayList<?> list = new ArrayList<>();

Es gibt aber auch einen überladenen Konstruktor mit einem Parameter für seine Anfangskapazität:

ArrayList<?> list = new ArrayList<>(20);

Warum ist es nützlich, eine ArrayListmit einer anfänglichen Kapazität zu erstellen, wenn wir sie nach Belieben anhängen können?

rauben
quelle
17
Haben Sie versucht, den ArrayList-Quellcode anzuzeigen?
AmitG
@ Joachim Sauer: Manchmal bekommen wir eine Erkenntnis, wenn wir die Quelle sorgfältig lesen. Ich habe es versucht, wenn er die Quelle gelesen hat. Ich habe deinen Aspekt verstanden. Vielen Dank.
AmitG
ArrayList ist schlecht leistungsfähig, warum sollten Sie eine solche Struktur verwenden
PositiveGuy

Antworten:

196

Wenn Sie im Voraus wissen, wie groß die Größe ArrayListsein wird, ist es effizienter, die anfängliche Kapazität anzugeben. Wenn Sie dies nicht tun, muss das interne Array wiederholt neu zugewiesen werden, wenn die Liste wächst.

Je größer die endgültige Liste ist, desto mehr Zeit sparen Sie, indem Sie die Neuzuweisungen vermeiden.

Das Einfügen von nElementen auf der Rückseite eines ArrayListwird jedoch auch ohne vorherige Zuweisung garantiert die gesamte O(n)Zeit in Anspruch nehmen . Mit anderen Worten, das Anhängen eines Elements ist eine amortisierte Operation mit konstanter Zeit. Dies wird erreicht, indem jede Neuzuweisung die Größe des Arrays exponentiell erhöht, typischerweise um einen Faktor von 1.5. Mit diesem Ansatz kann die Gesamtzahl der Operationen angezeigt werdenO(n) .

NPE
quelle
5
Obwohl es eine gute Idee ist, bekannte Größen vorab zuzuweisen, ist es normalerweise nicht schrecklich, dies nicht zu tun: Für eine Liste mit einer endgültigen Größe von n müssen Sie etwa log (n) neu zuweisen , was nicht viel ist.
Joachim Sauer
2
@ PeterOlson O(n log n)würde log nArbeitszeiten machen n. Das ist eine grobe Überschätzung (obwohl technisch korrekt mit großem O, da es eine Obergrenze ist). Es kopiert insgesamt s + s * 1,5 + s * 1,5 ^ 2 + ... + s * 1,5 ^ m (so dass s * 1,5 ^ m <n <s * 1,5 ^ (m + 1)) Elemente. Ich bin nicht gut in Summen, daher kann ich Ihnen nicht die genaue Mathematik auf den Kopf stellen (für die Größenänderung von Faktor 2 ist es 2n, also kann es 1,5n sein, geben oder nehmen Sie eine kleine Konstante), aber das tut es nicht. ' Nehmen Sie nicht zu viel Schielen, um zu sehen, dass diese Summe höchstens einen konstanten Faktor größer als n ist. Es werden also O (k * n) Kopien benötigt, was natürlich O (n) ist.
1
@delnan: Kann damit nicht streiten! ;) Übrigens, ich mochte dein Schielargument sehr; werde es meinem Trickrepertoire hinzufügen.
NPE
6
Es ist einfacher, mit dem Verdoppeln zu argumentieren. Angenommen, Sie verdoppeln sich, wenn Sie voll sind, beginnend mit einem Element. Angenommen, Sie möchten 8 Elemente einfügen. Fügen Sie eine ein (Kosten: 1). Zwei einfügen - doppelt, ein Element kopieren und zwei einfügen (Kosten: 2). Drei einfügen - doppelt, zwei Elemente kopieren, drei einfügen (Kosten: 3). Fügen Sie vier ein (Kosten: 1). Fünf einfügen - doppelt, vier Elemente kopieren, fünf einfügen (Kosten: 5). Fügen Sie sechs, sieben und acht ein (Kosten: 3). Gesamtkosten: 1 + 2 + 3 + 1 + 5 + 3 = 16, was der doppelten Anzahl eingefügter Elemente entspricht. Anhand dieser Skizze können Sie nachweisen, dass die durchschnittlichen Kosten im Allgemeinen zwei pro Einsatz betragen .
Eric Lippert
9
Das ist der Zeitaufwand . Sie können jedoch auch feststellen, dass sich die Menge des verschwendeten Speicherplatzes im Laufe der Zeit geändert hat und manchmal 0% und manchmal nahezu 100% beträgt. Durch Ändern des Faktors von 2 auf 1,5 oder 4 oder 100 oder was auch immer ändert sich die durchschnittliche Menge an verschwendetem Speicherplatz und die durchschnittliche Zeit, die für das Kopieren aufgewendet wird. Die zeitliche Komplexität bleibt jedoch im Durchschnitt linear, unabhängig vom Faktor.
Eric Lippert
41

Da ArrayListes sich um eine Array- Datenstruktur mit dynamischer Größenänderung handelt, bedeutet dies, dass sie als Array mit einer anfänglichen (Standard-) festen Größe implementiert ist. Wenn dies gefüllt ist, wird das Array auf ein doppelt großes Array erweitert. Dieser Vorgang ist kostspielig, daher möchten Sie so wenig wie möglich.

Wenn Sie also wissen, dass Ihre Obergrenze 20 Elemente beträgt, ist es besser, das Array mit einer Anfangslänge von 20 zu erstellen, als einen Standardwert von beispielsweise 15 zu verwenden. Ändern Sie dann die Größe auf 15*2 = 3020 und verwenden Sie nur 20, während Sie die Zyklen für die Erweiterung verschwenden.

PS - Wie AmitG sagt, ist der Expansionsfaktor implementierungsspezifisch (in diesem Fall (oldCapacity * 3)/2 + 1)

Iulius Curt
quelle
9
es ist tatsächlichint newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
25

Die Standardgröße von Arraylist ist 10 .

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    this(10);
    } 

Wenn Sie also 100 oder mehr Datensätze hinzufügen, können Sie den Aufwand für die Neuzuweisung von Speicher sehen.

ArrayList<?> list = new ArrayList<>();    
// same as  new ArrayList<>(10);      

Wenn Sie also eine Vorstellung von der Anzahl der Elemente haben, die in Arraylist gespeichert werden, ist es besser, Arraylist mit dieser Größe zu erstellen, anstatt mit 10 zu beginnen und diese dann weiter zu erhöhen.

xyz
quelle
Es gibt keine Garantie, dass die Standardkapazität für JDK-Versionen in Zukunft immer 10 sein wird -private static final int DEFAULT_CAPACITY = 10
vikingsteve
17

Ich habe vor 2 Monaten einen Blog-Beitrag zum Thema geschrieben. Der Artikel ist für C #, List<T>aber Java ArrayListhat eine sehr ähnliche Implementierung. Da ArrayListes mithilfe eines dynamischen Arrays implementiert wird, nimmt es bei Bedarf an Größe zu. Der Grund für den Kapazitätskonstruktor liegt also in Optimierungszwecken.

Wenn eine dieser Größenänderungsvorgänge ausgeführt wird, kopiert die ArrayList den Inhalt des Arrays in ein neues Array, das doppelt so groß ist wie das alte. Diese Operation läuft in O (n) Zeit.

Beispiel

Hier ist ein Beispiel, wie sich die ArrayListGröße erhöhen würde:

10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308

Die Liste beginnt also mit einer Kapazität von 10: Wenn das 11. Element hinzugefügt wird, wird es um 50% + 1bis erhöht 16. Ab dem 17. Punkt ArrayListwird der Wert erneut erhöht 25und so weiter. Betrachten Sie nun das Beispiel, in dem wir eine Liste erstellen, in der die gewünschte Kapazität bereits als bekannt ist 1000000. Wenn Sie den ArrayListKonstruktor ohne Größe erstellen, werden ArrayList.add 1000000Zeiten aufgerufen , die normalerweise O (1) oder O (n) beim Ändern der Größe benötigen.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 Operationen

Vergleichen Sie dies mit dem Konstruktor und rufen Sie dann auf, ArrayList.addwas garantiert in O (1) ausgeführt wird .

1000000 + 1000000 = 2000000 Operationen

Java vs C #

Java ist wie oben und beginnt bei 10und erhöht jede Größenänderung bei 50% + 1. C # beginnt bei 4und steigt viel aggressiver an und verdoppelt sich bei jeder Größenänderung. Das 1000000Beispiel von oben für C # verwendet 3097084Operationen.

Verweise

Daniel Imms
quelle
9

Durch Festlegen der Anfangsgröße einer ArrayList, z. B. auf ArrayList<>(100), wird die Häufigkeit der Neuzuweisung des internen Speichers verringert.

Beispiel:

ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2, 
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added. 

Wie Sie im obigen Beispiel sehen, ArrayListkann ein bei Bedarf erweitert werden. Dies zeigt Ihnen jedoch nicht, dass sich die Größe der Arraylist normalerweise verdoppelt (beachten Sie jedoch, dass die neue Größe von Ihrer Implementierung abhängt). Folgendes wird aus Oracle zitiert :

"Jede ArrayList-Instanz verfügt über eine Kapazität. Die Kapazität entspricht der Größe des Arrays, in dem die Elemente in der Liste gespeichert werden. Sie ist immer mindestens so groß wie die Listengröße. Wenn Elemente zu einer ArrayList hinzugefügt werden, wächst ihre Kapazität automatisch. Die Details der Wachstumspolitik werden nicht über die Tatsache hinaus spezifiziert, dass das Hinzufügen eines Elements konstante amortisierte Zeitkosten verursacht. "

Wenn Sie keine Ahnung haben, welchen Bereich Sie halten werden, ist das Einstellen der Größe wahrscheinlich keine gute Idee. Wenn Sie jedoch einen bestimmten Bereich im Auge haben, erhöht das Einstellen einer anfänglichen Kapazität die Speichereffizienz .

dsgriffin
quelle
3

ArrayList kann viele Werte enthalten. Wenn Sie große anfängliche Einfügungen vornehmen, können Sie ArrayList anweisen, zunächst einen größeren Speicher zuzuweisen, um keine CPU-Zyklen zu verschwenden, wenn versucht wird, mehr Speicherplatz für das nächste Element zuzuweisen. Daher ist es effizienter, am Anfang etwas Platz zuzuweisen.

Sanober Malik
quelle
3

Dies dient dazu, mögliche Anstrengungen zur Neuzuweisung für jedes einzelne Objekt zu vermeiden.

int newCapacity = (oldCapacity * 3)/2 + 1;

intern new Object[]erstellt wird.
JVM muss erstellt werden, new Object[]wenn Sie ein Element zur Arrayliste hinzufügen. Wenn Sie nicht über Code haben (jede algo Sie denken) für die Neuaufteilung jedes Mal dann , wenn Sie rufen arraylist.add()dann new Object[]muss erstellt werden , die sinnlos ist , und wir verlieren Zeit Größe für jede von 1 zu erhöhen und jede Objekte hinzugefügt werden. Daher ist es besser, die Größe Object[]mit der folgenden Formel zu erhöhen .
(JSL hat die unten angegebene Forcasting-Formel für dynamisch wachsende Arraylisten verwendet, anstatt jedes Mal um 1 zu wachsen. Da das Wachstum von JVM Anstrengungen erfordert)

int newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
quelle
ArrayList führt keine Neuzuweisung für jede einzelne durch add- es verwendet bereits intern eine Wachstumsformel. Daher wird die Frage nicht beantwortet.
AH
@AH Meine Antwort ist für negative Tests . Bitte lesen Sie zwischen den Zeilen. Ich sagte: "Wenn Sie keinen obigen Code (wie Sie denken) für die Neuzuweisung haben, muss jedes Mal, wenn Sie arraylist.add () aufrufen, ein neues Objekt [] erstellt werden, das sinnlos ist und wir verlieren Zeit." und der Code ist int newCapacity = (oldCapacity * 3)/2 + 1;der, der in der ArrayList-Klasse vorhanden ist. Denken Sie immer noch, dass es unbeantwortet bleibt?
AmitG
1
Ich denke immer noch, dass es nicht beantwortet wird: In ArrayListder amortisierten Umverteilung erfolgt auf jeden Fall mit jedem Wert für die anfängliche Kapazität. Und die Frage ist: Warum überhaupt einen nicht standardmäßigen Wert für die Anfangskapazität verwenden? Außerdem: "Lesen zwischen den Zeilen" ist in einer technischen Antwort nicht erwünscht. ;-)
AH
@AH Ich antworte wie, was passiert wäre, wenn wir keinen Neuzuweisungsprozess in ArrayList hätten. So ist die Antwort. Versuche den Geist der Antwort zu lesen :-). Ich weiß es besser In ArrayList erfolgt die amortisierte Neuzuweisung in jedem Fall mit einem beliebigen Wert für die Anfangskapazität.
AmitG
2

Ich denke, jede ArrayList wird mit einem Init-Kapazitätswert von "10" erstellt. Wenn Sie also eine ArrayList erstellen, ohne die Kapazität im Konstruktor festzulegen, wird sie mit einem Standardwert erstellt.

sk2212
quelle
2

Ich würde sagen, es ist eine Optimierung. ArrayList ohne anfängliche Kapazität hat ~ 10 leere Zeilen und wird beim Hinzufügen erweitert.

Um eine Liste mit genau der Anzahl der Elemente zu erhalten, müssen Sie trimToSize () aufrufen.

Daniel Magnusson
quelle
0

Nach meiner Erfahrung mit ArrayListist die Angabe einer Anfangskapazität ein guter Weg, um Umverteilungskosten zu vermeiden. Aber es ist eine Einschränkung. Alle oben genannten Vorschläge besagen, dass man die Anfangskapazität nur dann bereitstellen sollte, wenn eine grobe Schätzung der Anzahl der Elemente bekannt ist. Wenn wir jedoch versuchen, eine anfängliche Kapazität ohne Ahnung anzugeben, wird die reservierte und nicht verwendete Speichermenge eine Verschwendung sein, da sie möglicherweise nie benötigt wird, sobald die Liste mit der erforderlichen Anzahl von Elementen gefüllt ist. Was ich damit sagen möchte, ist, dass wir am Anfang pragmatisch sein können, während wir Kapazitäten zuweisen, und dann einen intelligenten Weg finden, um die erforderliche minimale Kapazität zur Laufzeit zu ermitteln. ArrayList bietet eine Methode namens ensureCapacity(int minCapacity). Aber dann hat man einen klugen Weg gefunden ...

Tushar Patidar
quelle
0

Ich habe ArrayList mit und ohne initialCapacity getestet und habe ein überraschendes Ergebnis erhalten.
Wenn ich LOOP_NUMBER auf 100.000 oder weniger setze, ist das Ergebnis, dass das Setzen von initialCapacity effizient ist.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10


Wenn ich LOOP_NUMBER auf 1.000.000 setze, ändert sich das Ergebnis zu:

list1Stop-list1Start = 40
list2Stop-list2Start = 66


Schließlich konnte ich nicht herausfinden, wie es funktioniert?!
Beispielcode:

 public static final int LOOP_NUMBER = 100000;

public static void main(String[] args) {

    long list1Start = System.currentTimeMillis();
    List<Integer> list1 = new ArrayList();
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list1.add(i);
    }
    long list1Stop = System.currentTimeMillis();
    System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));

    long list2Start = System.currentTimeMillis();
    List<Integer> list2 = new ArrayList(LOOP_NUMBER);
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list2.add(i);
    }
    long list2Stop = System.currentTimeMillis();
    System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}

Ich habe unter Windows 8.1 und JDK1.7.0_80 getestet

Hamedz
quelle
1
Hallo, leider beträgt die aktuelle TimeMillis-Toleranz (abhängig) bis zu hundert Millisekunden, was bedeutet, dass das Ergebnis kaum zuverlässig ist. Ich würde vorschlagen, eine benutzerdefinierte Bibliothek zu verwenden, um es richtig zu machen.
Bogdan