#java #performance #collections #arraylist
#java #Производительность #Коллекции #arraylist
Вопрос:
Есть ли какие-либо преимущества в производительности, если я вызываю метод ArrayList.ensureCapacity(). В каком случае целесообразно использовать этот метод?
Ответ №1:
Преимущество в производительности реализуется в тех случаях, когда вы собираетесь добавить несколько элементов в список и знаете, сколько вы собираетесь добавлять. Вызывая ensureCapacity(int) , вы вызываете изменение размера базового массива один раз, а не потенциально много раз.
Однако обратите внимание, что на самом деле вам редко нужно вызывать этот метод; обычно вы либо создаете экземпляр ArrayList с известной емкостью, либо в случаях, когда размер списка неизвестен, вам, вероятно, следует рассмотреть возможность использования LinkedList вместо.
Также обратите внимание, что стратегия изменения размера ArrayList обычно реализуется таким образом, что копирование массива является редкой операцией (например, емкость может увеличиваться на 50% каждый раз, когда массив заполняется). Другими словами, даже если вы не вызываете ensureCapacity заранее, вы вряд ли заметите какое-либо замедление в своем коде.
Комментарии:
1. Вы, вероятно, имели в виду «или в тех случаях, когда размер списка неизвестен «. Я не думаю, что это достаточная причина предпочесть LinkedList над ArrayList. ArrayList почти всегда работает быстрее, за исключением случаев, когда список большой и у вас частые вставки / удаления в / из начала списка или внутри итерации.
2. LinkedList практически при любых обстоятельствах — ужасная идея, она тратит больше памяти (намного больше), чем ArrayList, если накладывает дополнительную косвенность (промах кэша), что делает LinkedList наихудшей возможной структурой данных для итерации. Единственным преимуществом является вставка в середине во время итерации. Преимущество ensureCapacity() можно заметить с аргументом в диапазоне миллионов и начиная с ванильного arraylist .
3. @JBNizet, если удаление происходит во время итерации, сама итерация в linkedlist — это огромная цена, которую нужно заплатить.
4. @bestnsss: Вам не кажется, что это немного обобщение? Предположим, я программирую встроенную систему, в которой проблема с памятью. Я создаю ArrayList и добавляю 10M. Затем я удаляю 9,9 млн элементов; на данный момент базовый массив все еще имеет длину 10 м. Кроме того, предположим, мне нужно предсказуемое время вставки? Необходимость ждать полной копии массива во время изменения размера списка может вызвать всевозможные проблемы с производительностью в некоторых ситуациях, дело в том, что наихудшее время вставки — O (n), а не O (1).
5. @bestsss: это не то, что я наблюдаю в своем микро-бенчмарке. См. pastebin.com/mSWCzYhW . Удаление каждого четного элемента LinkedList с 10000 элементами на 2 порядка быстрее, чем то же самое в ArrayList. Однако простое повторение списка действительно намного быстрее с ArrayList. (JDK7)
Ответ №2:
Приложение может увеличить емкость экземпляра ArrayList перед добавлением большого количества элементов с помощью операции ensureCapacity . Это может уменьшить объем дополнительного перераспределения.
ArrayList.ensureCapacity() При необходимости увеличивает емкость этого экземпляра ArrayList, чтобы гарантировать, что он может содержать по крайней мере количество элементов, указанное в аргументе минимальной емкости.