[Java] Initial capacity ArrayList

[Bobco]

Mijn vraag is eigenlijk heel simpel: als je met

code:

ArrayList myList = new ArrayList();

een ArrayList aanmaakt, wat is dan het aantal objecten dat je er in kunt stoppen voordat de ArrayList zichzelf moet resizen?

In mijn zoektocht ben ik wel wat info tegengekomen over de capaciteit van andere containers zoals de Vector. Verder heb ik al wel gelezen dat een Vector zichzelf verdubbelt in grootte terwijl een ArrayList zich met 50% vergroot.

[Verwijderd]

Ik zat even in de API docs te kijken, maar daar staat het niet in. Je kunt natuurlijk wel instellen wat die capaciteit moet zijn new ArrayList(100) bijvoorbeeld.

[Alarmnummer]

Anders moet je even de source bekijken. Daar staat het wel in. En als je verder veel aan het verwijderen en toevoegen bent, kan het handiger zijn om een andere liststructuur te gebruiken zoals een linkedlist. Of zelf een hele andere collectie structuur zoals de map als je ook nog een snel wilt zoeken en de volgorde niet van belang is.

[Bobco]

Daar kon ik het inderdaad ook niet vinden. Het gaat mij voornamelijk om situaties waarin je een Collection met een paar objecten er in wilt kopieren naar een ArrayList. De vraag is dan wat sneller is/minder resources vraagt:

Java:

ArrayList myList = new ArrayList(collection.size())
Iterator i = collection.iterator();
while (i.hasNext()) {
  myList.add(i.next());
}

// of

ArrayList myList = new ArrayList(collection);

Als ik de API mag geloven dan is de tweede eigenlijk een kortere manier om het eerste op te schrijven. Bij de ArrayList(Collection c) constructor staat tenminste dat dit een ArrayList oplevert waaraan de objecten zijn toegevoegd in de volgorde waarin de iterator van de Collection de objecten teruggeeft. In het eerste geval geef ik expliciet de capacity op, zodat ik zeker weet dat er geen extra bytes verspild worden. In het tweede geval is het me niet direct duidelijk wat de capacity van myList is na het uitvoeren van de code.

[DaCoTa]

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

Zo te lezen is het JVM specifiek. Ik zag ook geen capacity() oid waar je het aan kunt aflezen. Uit de sourcecode van Sun JVM:

Java:

    /**
     * Constructs an empty list.
     */
    public ArrayList() {
    this(10);
    }

Dat ziet er redelijk arbitrair uit...
Als ik jouw code zo zie, lijkt me de eerste toch sneller omdat je hierbij alle extra resizes bespaart en niet eindigd met een te grote capacity. Nogmaals uit ArrayList.java:

Java:

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.  The <tt>ArrayList</tt> instance has an initial capacity of
     * 110% the size of the specified collection.
     *
     * @param c the collection whose elements are to be placed into this list.
     */
    public ArrayList(Collection c) {
        size = c.size();
    elementData = new Object[(size*110)/100]; // Allow 10% room for growth
        c.toArray(elementData);
    }

Is misschien handig om deze constructie over te nemen maar dan met een exacte size match. Dat zou ook wel eens sneller kunnen zijn dan de Iterator aanpak. Kwestie van benchmarken denk ik.

[ Voor 45% gewijzigd door DaCoTa op 14-01-2003 10:31 ]

[Bobco]

DaCoTa: dat zag ik inderdaad ook in de source voorbijkomen. Maar wat me ook opviel is dat het toevoegen van alle elementen van een andere Collection gewoon gebeurt door eerst te kijken of de oude capaciteit van de array groot genoeg is om de nieuwe elementen toe te voegen. Alleen als het aantal nieuwe elementen groter is dan de bestaande array dan wordt er meteen geresized.

Java:

ArrayList myList = new ArrayList(c.size());
myList.addAll(c);

zou dan de manier zijn om precies goed te sizen.