Pourquoi Collections.addAll est-il censé être plus rapide que c.addAll

Question

L' API Java docs dire le suit à propos de l' Collections.addAll

Le comportement de cette commodité méthode est identique à celle de c.addAll(Tableaux.asList(éléments de)), mais cette méthode est susceptible de fonctionner beaucoup plus rapidement dans la plupart des implémentations.

Donc, si je comprends bien, un) est plus lent que b):

a)

Collection<Integer> col = new ArrayList<Integer>();
col.addAll(Arrays.asList(1, 2, 3, 4, 5));

b)

Collection<Integer> col = new ArrayList<Integer>();
// Collections.addAll(col, Arrays.asList(1, 2, 3, 4, 5)); <-- won't compile
Collections.addAll(col, 1, 2, 3, 4, 5);

Quelqu'un peut-il m'expliquer, pourquoi c'est?

modifié: code corrigé exemple. thx pour polygenelubricants

Answer 1

Prenons regarder de plus près les deux d'entre eux:

// a)
col.addAll(Arrays.asList(1, 2, 3, 4, 5));

Voici ce qui arrive:

1. varags + l'autoboxing crée Integer[]
2. Arrays.asList crée un List<Integer> soutenu par le tableau
3. addAll itère sur un Collection<Integer> l'aide Iterator<Integer>

// b)
Collections.addAll(col, 1, 2, 3, 4, 5);

Voici ce qui arrive:

1. varargs + l'autoboxing crée Integer[]
2. addAll itère sur un tableau (au lieu d' Iterable<Integer>)

Nous pouvons maintenant voir que b) peut être plus rapide car:

• Arrays.asList appel est ignoré, c'est à dire sans intermédiaire List est créé.
• Puisque les éléments sont donnés dans un tableau (grâce à varargs mécanisme), l'itération sur eux peut être plus rapide que l'utilisation d' Iterator.

Cela dit, à moins que le profilage montre le contraire, la différence n'est pas susceptible d'être "significatif". Ne pas optimiser prématurément. Alors que Java Cadre de Collecte des classes peut être plus lent que les tableaux, ils effectuent plus de manière adéquate pour la plupart des applications.

API liens

• Collections.addAll(Collection<? super T> c, T... elements) - varargs c'est à dire basée sur la baie
• Collection.addAll(Collection<? extends E> c) - Collection-en fonction

Voir aussi

• Le Langage Java/Guide De L'Autoboxing
• Le Langage Java/Guide De Varargs
• Efficace Java 2nd Edition, Article 25: Préférez les listes de tableaux

Questions connexes

• Tableau ou une Liste en Java. Ce qui est plus rapide ?

---

Résumé

• Si vous êtes en train d'ajouter des éléments d'un tableau, vous pouvez utiliser Collections.addAll(col, arr)
  • Rappelez-vous que varargs sont également effectués à l'aide de tableaux
• Si vous ajoutez des éléments à partir d'un Collection, utilisez col.addAll(otherCol)
  • Ne PAS par exemple, Collections.addAll(col, otherCol.toArray())
    • Ces rond-point sera probablement plus lent!
• Ce n'est pas que l'on est extrêmement plus rapide que les autres
  • C'est de sauter les étapes inutiles compte tenu de la situation actuelle

Answer 2

La seule raison pour laquelle il pourrait être plus rapide est qu'il évite l'appel à des Tableaux.asList qui devrait être relativement bon marché, comme il vient d'enveloppe le tableau. Certains de Collecte mises en œuvre, par exemple LinkedList convertir le passé de la collection de revenir à un tableau avant d'ajouter les éléments, provoquant une surcharge supplémentaire.

D'autre part, ArrayList.addAll alloue l'espace nécessaire une fois avant d'ajouter des éléments et devrait donc être beaucoup plus rapide lorsque les Collections.addAll nécessite plusieurs redimensionnement de la sauvegarde de la matrice.

En résumé, les Collections.addAll pourrait être plus rapide lors de l'ajout répété que quelques éléments d'une collection, mais je doute que cette affaire ne serait jamais un goulot d'étranglement des performances.

Answer 3

(Nous allons construire sur SOI Plate-forme de 6)

Tout dépend de la perception effective de la mise en œuvre. Dans votre exemple, nous avons

Collection<Integer> col = new ArrayList<Integer>();

et addAll méthode de ArrayList est surchargé. Pas d'itérations que ce soit. Voici le code source:

public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
    int numNew = a.length;
ensureCapacity(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
return numNew != 0;
}

Comme vous pouvez le remarquer c.toArray() dépend également de la mise en œuvre effective. Encore une fois, dans votre cas Arrays.asList() résultats en ArrayList laquelle est la version de toArray() méthode ressemble à ceci:

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

Cette méthode statique est basée sur System.arraycopy

Donc en fait ce que nous traitons ici est de deux appels d' System.arraycopy ce qui n'est pas mal fait parce que c'est une méthode native, spécialement optimisé pour le fonctionnement actuel du système.

Donc, pour résumer le tout dans M. polygenelubricants style:

1. varags + l'autoboxing crée Integer[]
2. Arrays.asList crée un ArrayList<Integer>
3. ArrayList.addAll des appels System.arraycopy(size)x2, taille = 5

Dans votre cas, de 5 objets dans le tableau Collections.addAll est de cource plus rapide. MAIS hors de propos avec une telle petite taille de la matrice. D'autre part, si c'était, disons, 100 k éléments dans un tableau alors col.addAll(Arrays.asList(...)) est beaucoup plus efficace, cause auprès méthode native c'est un seul memcpy/memmove-nous concernés par opposition à 100k itérations/les opérations de copie.

Et encore une fois, tout dépend de la collection de la mise en œuvre. LinkedList par exemple va se répéter sur elle comme cela a été prévu.

Answer 4

Voici les fonctions de coût de complexité temporelle (approximatives) associées pour chacune des étapes mentionnées par @polygenelubricants:

a) 3 itérations sur la liste des arguments ~ = C (3N)

b) 2 itérations sur la liste d'arguments ~ = C (2N)

Il est clair qu'ils sont tous les deux O (N) mais l'approche b) permet d'économiser ~ N comparaisons sur l'approche a). J'espère que cela sera utile à toute personne intéressée par une explication quantitative.