Pourquoi démarrer une ArrayList avec une capacité initiale?

149

Le constructeur habituel de ArrayListest:

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

Mais il existe aussi un constructeur surchargé avec un paramètre pour sa capacité initiale:

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

Pourquoi est-il utile de créer un ArrayListavec une capacité initiale alors que nous pouvons y ajouter à notre guise?

Rob
la source
17
Avez-vous essayé de voir le code source ArrayList?
AmitG
@Joachim Sauer: Parfois, nous en prenons conscience lorsque nous lisons attentivement la source. J'essayais s'il avait lu la source. J'ai compris votre aspect. Merci.
AmitG
ArrayList est une période peu performante, pourquoi voudriez-vous utiliser une telle structure
PositiveGuy

Réponses:

196

Si vous savez à l'avance quelle sera la taille de la ArrayList, il est plus efficace de spécifier la capacité initiale. Si vous ne le faites pas, le tableau interne devra être réalloué à plusieurs reprises au fur et à mesure que la liste s'allonge.

Plus la liste finale est longue, plus vous gagnez de temps en évitant les réallocations.

Cela dit, même sans pré-allocation, l'insertion d' néléments à l'arrière d'un ArrayListest garanti pour prendre un O(n)temps total . En d'autres termes, l'ajout d'un élément est une opération à temps constant amorti. Pour ce faire, chaque réallocation augmente la taille du tableau de façon exponentielle, généralement d'un facteur de 1.5. Avec cette approche, le nombre total d'opérations peut être démontréO(n) .

NPE
la source
5
Bien que pré-allouer des tailles connues soit une bonne idée, ne pas le faire n'est généralement pas terrible: vous aurez besoin de réallocations de log (n) pour une liste avec une taille finale de n , ce qui n'est pas beaucoup.
Joachim Sauer
2
@PeterOlson O(n log n)ferait des heures de log ntravail n. C'est une surestimation grossière (bien que techniquement correcte avec un grand O car il s'agit d'une limite supérieure). Il copie s + s * 1,5 + s * 1,5 ^ 2 + ... + s * 1,5 ^ m (tel que s * 1,5 ^ m <n <s * 1,5 ^ (m + 1)) éléments au total. Je ne suis pas doué pour les sommes, donc je ne peux pas vous donner le calcul précis du haut de ma tête (pour le facteur de redimensionnement 2, c'est 2n, donc ça peut être 1,5n en donnant ou en prenant une petite constante), mais ce n'est pas le cas. Il faut trop plisser les yeux pour voir que cette somme est au plus un facteur constant supérieur à n. Donc, il prend O (k * n) copies, ce qui est bien sûr O (n).
1
@delnan: Je ne peux pas discuter avec ça! ;) BTW, j'ai vraiment aimé votre argument de loucher; l'ajoutera à mon répertoire de trucs.
NPE
6
Il est plus facile de faire l'argument avec le doublement. Supposons que vous doubliez une fois plein, en commençant par un élément. Supposons que vous souhaitiez insérer 8 éléments. Insérez-en un (coût: 1). Insérez deux - double, copiez un élément et insérez deux (coût: 2). Insérez trois - double, copiez deux éléments, insérez trois (coût: 3). Insérez quatre (coût: 1). Insérez cinq - double, copiez quatre éléments, insérez cinq (coût: 5). Insérez six, sept et huit (coût: 3). Coût total: 1 + 2 + 3 + 1 + 5 + 3 = 16, soit le double du nombre d'éléments insérés. À partir de ce croquis, vous pouvez prouver que le coût moyen est de deux par insert en général.
Eric Lippert
9
C'est le coût en temps . Vous pouvez également voir que la quantité d' espace gaspillé a changé avec le temps, étant de 0% parfois et proche de 100% parfois. Changer le facteur de 2 à 1,5 ou 4 ou 100 ou quoi que ce soit change la quantité moyenne d'espace perdu et le temps moyen passé à copier, mais la complexité temporelle reste linéaire en moyenne quel que soit le facteur.
Eric Lippert
41

Parce qu'il ArrayLists'agit d'une structure de données de tableau de redimensionnement dynamique , ce qui signifie qu'elle est implémentée en tant que tableau avec une taille fixe initiale (par défaut). Lorsque celui-ci est rempli, la matrice sera étendue à une double taille. Cette opération est coûteuse, vous en voulez donc le moins possible.

Donc, si vous savez que votre limite supérieure est de 20 éléments, il est préférable de créer le tableau avec une longueur initiale de 20 que d'utiliser une valeur par défaut de, disons, 15, puis de le redimensionner 15*2 = 30et de n'utiliser que 20 tout en gaspillant les cycles d'expansion.

PS - Comme le dit AmitG, le facteur d'expansion est spécifique à l'implémentation (dans ce cas (oldCapacity * 3)/2 + 1)

Iulius Curt
la source
9
il est en faitint newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
25

La taille par défaut de Arraylist est de 10 .

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

Ainsi, si vous comptez ajouter 100 enregistrements ou plus, vous pouvez voir la surcharge de la réallocation de mémoire.

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

Donc, si vous avez une idée du nombre d'éléments qui seront stockés dans Arraylist, il est préférable de créer Arraylist avec cette taille au lieu de commencer par 10, puis de l'augmenter.

xyz
la source
Il n'y a aucune garantie que la capacité par défaut sera toujours de 10 pour les versions JDK à l'avenir -private static final int DEFAULT_CAPACITY = 10
vikingsteve
17

J'ai en fait écrit un article de blog sur le sujet il y a 2 mois. L'article est pour C # List<T>mais Java ArrayLista une implémentation très similaire. Comme il ArrayListest implémenté à l'aide d'un tableau dynamique, sa taille augmente à la demande. Donc, la raison du constructeur de capacité est à des fins d'optimisation.

Lorsqu'une de ces opérations de redimensionnement se produit, ArrayList copie le contenu du tableau dans un nouveau tableau qui est deux fois la capacité de l'ancien. Cette opération s'exécute en temps O (n) .

Exemple

Voici un exemple de la façon dont la ArrayListtaille augmenterait:

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

Ainsi, la liste commence avec une capacité de 10, lorsque le 11e élément est ajouté, il est augmenté de 50% + 1à 16. Sur le 17e élément, le ArrayListest à nouveau augmenté 25et ainsi de suite. Prenons maintenant l'exemple où nous créons une liste dans laquelle la capacité souhaitée est déjà connue sous le nom de 1000000. La création du ArrayListconstructeur sans la taille appellera des ArrayList.add 1000000temps qui prennent O (1) normalement ou O (n) lors du redimensionnement.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 opérations

Comparez cela en utilisant le constructeur, puis en appelant ArrayList.addce qui est garanti pour s'exécuter dans O (1) .

1000000 + 1000000 = 2000000 opérations

Java contre C #

Java est comme ci-dessus, commençant à 10et augmentant chaque redimensionnement à 50% + 1. C # commence à 4et augmente beaucoup plus agressivement, doublant à chaque redimensionnement. L' 1000000exemple ajoute ci-dessus pour C # utilise des 3097084opérations.

Références

Daniel Imms
la source
9

La définition de la taille initiale d'une ArrayList, par exemple à ArrayList<>(100), réduit le nombre de fois que la réallocation de la mémoire interne doit se produire.

Exemple:

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. 

Comme vous le voyez dans l'exemple ci-dessus, un ArrayListpeut être développé si nécessaire. Ce que cela ne vous montre pas, c'est que la taille de la liste Arraylist double généralement (mais notez que la nouvelle taille dépend de votre implémentation). Ce qui suit est cité par Oracle :

«Chaque instance ArrayList a une capacité. La capacité est la taille du tableau utilisé pour stocker les éléments dans la liste. Elle est toujours au moins aussi grande que la taille de la liste. Au fur et à mesure que les éléments sont ajoutés à une ArrayList, sa capacité augmente automatiquement. Les détails de la politique de croissance ne sont pas précisés au-delà du fait que l'ajout d'un élément a un coût en temps amorti constant. "

Évidemment, si vous n'avez aucune idée du type de plage que vous tiendrez, définir la taille ne sera probablement pas une bonne idée - cependant, si vous avez une plage spécifique en tête, la définition d'une capacité initiale augmentera l'efficacité de la mémoire. .

dsgriffin
la source
3

ArrayList peut contenir de nombreuses valeurs et lorsque vous effectuez des insertions initiales importantes, vous pouvez indiquer à ArrayList d'allouer un stockage plus important pour commencer afin de ne pas gaspiller de cycles de processeur lorsqu'il tente d'allouer plus d'espace pour l'élément suivant. Ainsi, allouer de l'espace au début est plus efficace.

Sanober Malik
la source
3

Ceci afin d'éviter d'éventuels efforts de réallocation pour chaque objet.

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

new Object[]est créé en interne .
La JVM a besoin d'efforts pour créer new Object[]lorsque vous ajoutez un élément dans l'arraylist. Si vous n'avez pas de code ci-dessus (n'importe quel algo que vous pensez) pour la réallocation, alors chaque fois que vous appelez, arraylist.add()il new Object[]faut créer ce qui est inutile et nous perdons du temps pour augmenter la taille de 1 pour chaque objet à ajouter. Il est donc préférable d'augmenter la taille de Object[]avec la formule suivante.
(JSL a utilisé la formule de prévision donnée ci-dessous pour une arraylist en croissance dynamique au lieu d'augmenter de 1 à chaque fois. Parce que la croissance nécessite des efforts de la part de JVM)

int newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
la source
ArrayList n'effectuera pas de réallocation pour chaque élément add- il utilise déjà une formule de croissance en interne. La question n’est donc pas répondue.
AH
@AH Ma réponse est un test négatif . Veuillez lire entre les lignes. J'ai dit "Si vous n'avez pas de code ci-dessus (n'importe quel algo que vous pensez) pour la réallocation, alors chaque fois que vous invoquez arraylist.add (), alors un nouvel Object [] doit être créé, ce qui est inutile et nous perdons du temps." et le code est int newCapacity = (oldCapacity * 3)/2 + 1;présent dans la classe ArrayList. Pensez-vous toujours qu'il reste sans réponse?
AmitG
1
Je pense toujours qu'il n'y a pas de réponse: dans ArrayListla réallocation amortie a lieu en tout cas avec une valeur quelconque pour la capacité initiale. Et la question est la suivante: pourquoi utiliser une valeur non standard pour la capacité initiale? En plus de cela: "lire entre les lignes" n'est pas quelque chose de souhaité dans une réponse technique. ;-)
AH
@AH Je réponds comme, que s'était-il passé si nous n'avions pas de processus de réallocation dans ArrayList. Telle est la réponse. Essayez de lire l'esprit de la réponse :-). Je connais mieux Dans ArrayList, la réallocation amortie a lieu dans tous les cas avec une valeur quelconque pour la capacité initiale.
AmitG
2

Je pense que chaque ArrayList est créé avec une valeur de capacité d'initialisation de "10". Donc de toute façon, si vous créez une ArrayList sans définir de capacité dans le constructeur, elle sera créée avec une valeur par défaut.

sk2212
la source
2

Je dirais que c'est une optimisation. ArrayList sans capacité initiale aura ~ 10 lignes vides et se développera lorsque vous effectuez un ajout.

Pour avoir une liste avec exactement le nombre d'éléments dont vous avez besoin d'appeler trimToSize ()

Daniel Magnusson
la source
0

D'après mon expérience avec ArrayList, donner une capacité initiale est un bon moyen d'éviter les coûts de réaffectation. Mais cela mérite une mise en garde. Toutes les suggestions mentionnées ci-dessus indiquent qu'il ne faut fournir la capacité initiale que si une estimation approximative du nombre d'éléments est connue. Mais lorsque nous essayons de donner une capacité initiale sans aucune idée, la quantité de mémoire réservée et inutilisée sera un gaspillage car elle ne sera peut-être jamais nécessaire une fois que la liste est remplie jusqu'au nombre requis d'éléments. Ce que je dis, c'est que nous pouvons être pragmatiques au début lors de l'allocation de capacité, puis trouver un moyen intelligent de connaître la capacité minimale requise au moment de l'exécution. ArrayList fournit une méthode appelée ensureCapacity(int minCapacity). Mais alors, il faut trouver un moyen intelligent ...

Tushar Patidar
la source
0

J'ai testé ArrayList avec et sans initialCapacity et j'ai obtenu un résultat surprenant.
Quand je règle LOOP_NUMBER à 100 000 ou moins, le résultat est que le réglage initialCapacity est efficace.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10


Mais lorsque je règle LOOP_NUMBER sur 1 000 000, le résultat devient:

list1Stop-list1Start = 40
list2Stop-list2Start = 66


Enfin, je n'ai pas compris comment ça marche?!
Exemple de code:

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

J'ai testé sur windows8.1 et jdk1.7.0_80

Hamedz
la source
1
salut, malheureusement, la tolérance de currentTimeMillis est de jusqu'à cent millisecondes (selon), ce qui signifie que le résultat n'est guère fiable. Je suggère d'utiliser une bibliothèque personnalisée pour le faire correctement.
Bogdan