Почему Collections.addAll должен быть быстрее, чем c.addAll

Question

Документы Java API говорят следующее о Collections.addAll

Поведение этого вспомогательного метода идентично поведению c.addAll (Arrays.asList (elements)), но этот метод, вероятно, будет работать значительно быстрее в большинстве реализаций.

Так что, если я правильно понимаю, а) медленнее, чем б):

а)

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

б)

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

Может кто-нибудь объяснить мне, почему это так?

изм: пример исправленного кода. THX до полигенных смазок

Answer 1

Давайте подробнее рассмотрим два из них:

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

Вот что происходит:

1. varags + autoboxing создает Integer[]
2. Arrays.asList создает List<Integer>, поддерживаемый массивом
3. addAll перебирает Collection<Integer>, используя Iterator<Integer>

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

Вот что происходит:

1. varargs + autoboxing создает Integer[]
2. addAll перебирает массив (вместо Iterable<Integer>)

Теперь мы видим, что b) может быть быстрее, потому что:

• Arrays.asList звонок пропущен, т.е. посредник не создан List.
• Поскольку элементы задаются в массиве (благодаря механизму varargs), их итерация может быть быстрее, чем при использовании Iterator.

Тем не менее, если профилирование не показывает иное, разница вряд ли будет "значительной". Не оптимизируйте преждевременно. Хотя классы Java Collection Framework могут работать медленнее, чем массивы, они работают более чем адекватно для большинства приложений.

API ссылки

• Collections.addAll(Collection<? super T> c, T... elements) - переменные, т.е. на основе массива
• Collection.addAll(Collection<? extends E> c) - Collection на основе

Смотри также

• Руководство по языку Java / Автобокс
• Руководство по языку Java / Varargs
• Effective Java 2nd Edition, Item 25: Предпочитать списки массивам

Похожие вопросы

• Массив или Список в Java. Что быстрее?

---

Резюме

• Если вы добавляете элементы из массива, вы можете использовать Collections.addAll(col, arr)
  • Помните, что varargs также делаются с использованием массивов
• Если вы добавляете элементы из Collection, используйте col.addAll(otherCol)
  • До НЕ например Collections.addAll(col, otherCol.toArray())
    • Такой обходной путь, вероятно, будет медленнее!
• Дело не в том, что один в высшей степени быстрее другого
  • Речь идет о пропуске ненужных шагов, учитывая текущую ситуацию

Answer 2

Единственная причина, по которой он может быть быстрее, состоит в том, что он избегает вызова Arrays.asList, который должен быть относительно дешевым, поскольку он просто оборачивает массив.Некоторые реализации Collection, например LinkedList, преобразуют переданную коллекцию обратно в массив перед добавлением элементов, вызывая дополнительные издержки.

С другой стороны, ArrayList.addAll выделяет необходимое пространство один раз перед добавлением любых элементов и поэтому долженБыстрее, когда Collections.addAll требует многократного изменения размера массива резервных копий.

В итоге, Collections.addAll может быть быстрее при многократном добавлении в коллекцию только нескольких элементов, но я сомневаюсь, что этот случай когда-либо будетузкое место в производительности.

Answer 3

Вот (приблизительные) связанные функции стоимости сложности времени для каждого из этапов, упомянутых @polygenelubricants:

a) 3 итерации по списку аргументов ~ = C (3N)

b) 2 итерации по списку аргументов ~ = C (2N)

Ясно, что они оба O (N), но подход b) сохраняет ~ N сравнений по сравнению с подходом a). Надеюсь, это будет полезно всем, кто интересуется количественным объяснением.

Answer 4

(Давайте построим на платформе SE 6)

Все зависит от фактической реализации коллекции. В вашем примере мы имеем

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

и addAll метод в ArrayList переопределяется. Никаких итераций. Вот источник:

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

Как вы могли заметить, c.toArray() также зависит от фактической реализации. Опять же, в вашем случае Arrays.asList() приводит к ArrayList, чья версия метода toArray() выглядит следующим образом:

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

Этот статический метод основан на System.arraycopy

На самом деле мы имеем дело с двумя вызовами System.arraycopy, что на самом деле не так уж и плохо, потому что это нативный метод, специально оптимизированный для текущей операционной системы.

Итак, подведем итоги в стиле мистера Полигенубрикантс:

1. varags + autoboxing создает Integer[]
2. Arrays.asList создает ArrayList<Integer>
3. ArrayList.addAll звонки System.arraycopy(size) x2, размер = 5

В вашем случае 5 объектов в массиве Collections.addAll, конечно, быстрее. НО не имеет значения при таком маленьком размере массива. С другой стороны, если это было, скажем, 100k элементов в массиве, то col.addAll(Arrays.asList(...)) гораздо более эффективно, потому что с нативным методом это единственный memcpy / memmove, с которым мы имеем дело, а не 100k итераций / операций копирования.

И снова, все зависит от реализации коллекции. LinkedList например будет перебирать его, как и ожидалось.