De ce începe un ArrayList cu o capacitate inițială?

Dacă știi în avans ce dimensiune de ArrayList va fi, este mult mai eficient pentru a specifica o capacitate inițială. Dacă tu nu't face acest lucru, interne matrice va trebui să fie realocate în mod repetat ca lista creste.

Cea mai mare lista finală, mai mult timp te salva prin evitarea realocări.

Asta a spus, chiar și fără pre-alocarea, introducerea n elemente de la spate de un ArrayList este garantat să ia total O(n) timp. Cu alte cuvinte, adăugarea unui element este un amortizat constantă de timp de funcționare. Acest lucru este realizat de către având fiecare realocare a crește dimensiunea de matrice exponențial, de obicei, cu un factor de 1.5. Cu această abordare, numărul total de operațiuni pot fi de-a dovedit a fi O(n)`.

Pentru ArrayList` este o dinamic redimensionarea matrice structura de date, ceea ce înseamnă că acesta este implementat ca o matrice cu o inițială (default) dimensiune fixă. Când aceasta se umple, gama va fi extinsă la un dublu de dimensiuni una. Această operațiune este costisitoare, așa că vă doresc cât mai puține posibil.

Deci, dacă știți limita superioară este de 20 de elemente, apoi crearea de matrice cu inițială lungime de 20 este mai bună decât folosind un default de, să zicem, 15 și apoi redimensiona pentru 15*2 = 30 și de a folosi numai 20 în timp ce pierde ciclurile de expansiune.

P. S. - Ca AmitG spune, factorul de expansiune este punerea în aplicare specifice (în acest caz (oldCapacity * 3)/2 + 1)

Dimensiunea implicită a Arraylist este 10.

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

Deci, dacă aveți de gând să adăugați 100 sau mai multe înregistrări, puteți vedea aeriene din realocarea de memorie.

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

Deci, dacă aveți vreo idee cu privire la numărul de elemente care vor fi stocate în Arraylist este mai bine pentru a crea Arraylist cu dimensiunea în loc de a începe cu 10 și apoi merge pe creștere.

De fapt am scris un blog pe subiect acum 2 luni. Articolul este pentru C#'s Listă<T> dar Java's ArrayList are o foarte similare în aplicare. Din ArrayList este implementat folosind o gamă dinamică, aceasta crește în dimensiune la cerere. Deci, motiv pentru capacitatea de constructor este pentru optimizarea scopuri.

Atunci când una dintre aceste resizings operațiune are loc, ArrayList copiază conținutul de matrice intr-o noua matrice care este de două ori capacitatea de cea veche. Această operație se execută în O(n) timp.

Exemplu

Aici este un exemplu de cum ArrayList ar crește în mărime de:

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

Deci lista incepe cu o capacitate de 10, atunci când al 11-lea element este adăugat acesta este în creștere de 50% + 116. Pe 17 articol ArrayList este crescut din nou să25și așa mai departe. Acum luați în considerare exemplul de unde am're a crea o listă în cazul în care capacitatea dorită este deja cunoscut ca1000000. CreareaArrayList fără dimensiunea constructorul va numi ArrayList.adauga` `1000000 de ori care are O(1) în mod normal, sau O(n) pe redimensiona.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 operațiuni

Comparați acest lucru cu ajutorul constructorului și apoi a sunat ArrayList.adauga` care este garantat pentru a rula în O(1).

1000000 + 1000000 = 2000000 operațiuni

Java vs C#

Java este ca mai sus, începând de la 10 și în creștere în fiecare resize la 50% + 1. C# pornește de la " 4 " și crește mult mai agresiv, dublarea la fiecare redimensionare. Anii1000000` adaugă exemplu de mai sus pentru C# foloseste 3097084 de operațiuni.

Referințe

• Blog-ul meu post pe C#'s Listă<T>
• Java's ArrayList source code

Setarea dimensiunea inițială de un ArrayList, de exemplu, pentru a ArrayList<>(100), reduce numărul de ori re-alocare de memorie internă trebuie să apară.

Exemplu:

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. 

După cum puteți vedea în exemplul de mai sus - un ArrayList` poate fi extins dacă este necesar să fie. Ce nu - 't vă arăt este că dimensiunea Arraylist de obicei duble (deși rețineți că noua dimensiune depinde de implementare). Următorul text este citat de Oracle:

"Fiecare ArrayList exemplu, are o capacitate. Capacitatea este de dimensiunea matrice folosite pentru a stoca elemente în listă. Este întotdeauna la cel puțin la fel de mare ca dimensiunea listei. Ca elemente sunt adăugate la o ArrayList, capacitatea acestuia de a crește în mod automat. Detaliile de creștere politica nu sunt specificate dincolo de faptul că adăugarea unui element are constantă amortizat costul de timp."

Evident, dacă nu aveți nici o idee de ce fel de gama va fi exploatație, stabilind dimensiunea, probabil, a câștigat't fi o idee bună - cu toate acestea, dacă aveți un anumit interval în minte, stabilind o capacitate inițială va crește eficiența memoriei.

ArrayList poate conține mai multe valori și atunci când faci inițială mare inserții puteți spune ArrayList să aloce o stocare mai mare pentru a începe cu, ca să nu pierdeți cicluri CPU atunci când încearcă să aloce mai mult spațiu pentru elementul următor. Astfel, pentru a aloca un spațiu la început este mai effiecient.

Acest lucru este de a evita eforturile posibile pentru realocarea pentru fiecare obiect.

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

pe plan intern new Object[] este creat.
JVM are nevoie de efort pentru a crea noul Obiect[]atunci când adăugați elementul în arraylist. Dacă tu nu't au codul de mai sus(orice algo crezi) pentru realocarea apoi de fiecare dată când te invocarraylist.add ()", apoi " new Object [] a de a fi creat, care este inutilă și vom pierde timp pentru a crește dimensiunea de 1 pentru fiecare obiecte pentru a fi adăugate. Deci, este mai bine pentru a crește dimensiunea de Obiect[]` cu următoarea formulă.
(JSL a folosit prognozarea formula de mai jos pentru dinamică în creștere arraylist în loc de o creștere de 1 de fiecare dată. Pentru ca să crească este nevoie de efort de către JVM)

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

Am'd spune o optimizare. ArrayList fără capacitate inițială va avea ~10 rânduri goale și se va extinde atunci când faci o adăugați.

Pentru a avea o lista cu exact numărul de elemente de care aveți nevoie pentru a apela trimToSize()

Cred că fiecare ArrayList este creat cu o init valoare capacitatea de a "și 10". Oricum, dacă veți crea un ArrayList fără setarea capacității în cadrul constructorul va fi creat cu o valoare implicită.

Ca pe experienta mea cu ArrayList, oferind o capacitate inițială este un mod frumos de a evita realocarea costurilor. Dar ea poartă un avertisment. Toate sugestiile menționate mai sus spune că unul ar trebui să ofere o capacitate inițială numai atunci când o estimare aproximativă a numărului de elemente este cunoscut. Dar când am încerca să dea o capacitate inițială, fără nici o idee, cantitatea de memorie rezervate și nefolosite va fi o pierdere, deoarece nu poate fi necesară odată ce lista este completat cu numărul necesar de elemente. Ceea ce vreau să spun este, putem fi pragmatic la început, în timp ce alocarea de capacitate, și apoi găsi o modalitate inteligentă de a ști necesar minim de capacitate la runtime. ArrayList oferă o metodă numită ensureCapacity(int minCapacity). Dar apoi, unul a găsi un mod inteligent...

Am testat ArrayList cu și fără initialCapacity și am surprinzătoare rezultat
Când m-am stabilit LOOP_NUMBER la 100.000 sau mai puțin rezultatul este că stabilirea initialCapacity este eficient.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10

Dar când m-am stabilit LOOP_NUMBER la 1.000.000 rezultatul modificări:

list1Stop-list1Start = 40
list2Stop-list2Start = 66

În cele din urmă, am putut't ne dăm seama cum funcționează?!
Mostre de cod:

 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));
}

Am testat pe windows8.1 și jdk1.7.0_80