Подтвердить что ты не робот

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

Документы API Java API говорят о Collections.addAll

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

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

а)

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

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

отредактирован: исправленный пример кода. спасибо до polygenelubricants

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

  • varags + autoboxing создает Integer[]
  • Arrays.asList создает List<Integer>, поддерживаемый массивом
  • addAll выполняет итерацию по Collection<Integer> с помощью Iterator<Integer>
// b)
Collections.addAll(col, 1, 2, 3, 4, 5);

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

  • varargs + autoboxing создает Integer[]
  • addAll выполняет итерацию по массиву (вместо Iterable<Integer>)

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

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

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

Ссылки API

См. также

Связанные вопросы

Резюме

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

Ответ 2

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

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

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

Ответ 3

(построим на платформе 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, что не так уж плохо, потому что это собственный метод, специально оптимизированный для текущей операционной системы.

Итак, суммируем все это в стиле г-на полигеновых смазочных материалов:

  • varags + autoboxing создает Integer[]
  • Arrays.asList создает ArrayList<Integer>
  • ArrayList.addAll вызывает System.arraycopy(size) x2, size = 5

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

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

Ответ 4

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

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

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

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