Pourquoi commencer une liste de tableaux avec une capacité initiale?

Question

L'habitude, le constructeur de ArrayList est:

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

Mais il y a aussi une surcharge du constructeur avec un paramètre pour sa capacité initiale:

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

Pourquoi est-il utile de créer un ArrayList avec une capacité initiale lorsque nous pouvons ajouter à cela que nous s'il vous plaît?

Answer 1

Si vous savez à l'avance ce que la taille de l' ArrayList va être, il est plus efficace de spécifier la capacité initiale. Si vous ne le faites pas, le tableau interne devra être réaffectées à plusieurs reprises que la liste s'accroît.

La plus grande de la liste finale, plus le temps de vous sauver en évitant les réaffectations.

Cela dit, même sans pré-affectation, l'insertion d' n éléments à l'arrière de l' ArrayList est garanti pour le total des O(n) du temps. En d'autres termes, l'ajout d'un élément est la méthode de l'amortissement constante de temps de l'opération. Ceci est réalisé en ayant chaque réaffectation augmenter la taille de la matrice de façon exponentielle, en général d'un facteur d' 1.5. Avec cette approche, le nombre total d'opérations peut être démontré O(n).

Answer 2

Parce qu' ArrayList est une façon dynamique de redimensionnement de la matrice de structure de données, ce qui signifie qu'il est implémenté sous la forme d'un tableau avec une initiale (par défaut) de taille fixe. Quand c'est rempli, le tableau sera étendu à un lit double de taille. Cette opération est costful, si vous voulez vous aussi peu que possible.

Donc, si vous savez que votre limite supérieure est de 20 éléments, puis la création de la matrice avec une longueur initiale de 20 est mieux que d'utiliser une valeur par défaut, disons, 15 puis la redimensionner à l' 15*2 = 30 et utiliser seulement 20.

P. S. - Comme AmitG dit, le facteur d'expansion de la mise en œuvre est spécifique (dans ce cas - (oldCapacity * 3)/2 + 1)

Answer 3

La taille par défaut de la liste de tableaux est 10.

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

Donc, si vous allez à ajouter plus de 100 enregistrements, vous pouvez voir les frais généraux de la réallocation de mémoire.

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

Donc, si vous avez une idée sur le nombre d'éléments qui seront stockées dans la liste de tableaux de son mieux pour créer Arraylist avec cette taille au lieu de commencer par 10, puis d'aller sur l'augmenter.

Answer 4

J'ai en fait écrit un post de blog sur le sujet il y a 2 mois. L'article est pour le C#' List<T> mais de Java ArrayList a très semblable à la mise en œuvre. Depuis ArrayList est mis en œuvre à l'aide d'un tableau dynamique, il augmente en taille sur demande. Donc, la raison de la capacité du constructeur est de l'optimisation.

Lorsque l'un de ces redimensionnements de fonctionnement se produit, la liste de tableaux, copie le contenu du tableau dans un nouveau tableau qui est le double de la capacité de l'ancien. Cette opération s'exécute en O(n) fois.

Exemple

Voici un exemple de la façon dont l' ArrayList serait l'augmentation de la taille:

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

Si la liste commence avec une capacité de 10, lors de la 11e élément est ajouté, il est en augmentation en 50% + 1 de 16. Le 17 élément de l' ArrayList est à nouveau augmentée de 25 et ainsi de suite. Considérons maintenant l'exemple où nous sommes en train de créer une liste où la capacité souhaitée est déjà connu comme 1000000. La création de l' ArrayList sans la taille constructeur appellera ArrayList.add 1000000 temps qui prend O(1) normalement ou O(n) sur redimensionner.

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

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

1000000 + 1000000 = 2000000 opérations

Java vs C#

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

Références

• Mon blog sur C#List<T>
• Java est ArrayList code source

Answer 5

Réglage de la taille d'une liste de tableaux, par exemple, à l' ArrayList<>(100), réduit le nombre de fois que la ré-allocation de la mémoire interne de a à 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 - ArrayList peut être étendu si nécessaire. Que cela ne vous montrent pas, c'est que la taille de la liste de tableaux généralement double (à noter toutefois que la nouvelle taille dépend de votre mise en œuvre). Ce qui suit est cité Oracle:

"Chaque liste de tableaux, par exemple, a une capacité. La capacité est de la taille de la matrice utilisée pour stocker les éléments dans la liste. Il est toujours à moins aussi grand que la taille de la liste. Lorsque des éléments sont ajoutés à une Liste de tableaux, de sa capacité augmente automatiquement. Les détails de la croissance la politique ne sont pas spécifiés au-delà du fait que l'ajout d'un élément a constant amorti coût de temps."

Évidemment, si vous n'avez aucune idée de ce genre de gamme, vous serez en détention, à la définition de la taille ne sera probablement pas une bonne idée, cependant, si vous disposez d'une gamme spécifique à l'esprit, réglage d'une capacité initiale permettra d'accroître l'efficacité de mémoire.