Как определить понятие емкости в ArrayLists?

Question

Я понимаю, что емкость - это количество элементов или доступных пробелов в ArrayList, которые могут содержать или не содержать значение, ссылающееся на объект. Я пытаюсь понять больше о концепции потенциала.

Итак, у меня три вопроса:

1) Какими хорошими способами можно определить, какую емкость представляет с точки зрения памяти?

... (непрерывная?) Память, выделенная для ArrayList?

... след памяти ArrayLists на (куча?)?

2) Тогда, если вышеприведенное верно, для изменения емкости требуются некоторые накладные расходы на управление памятью?

3) У кого-нибудь есть пример, где № 2 был или мог быть проблемой производительности? Кроме, может быть, большого количества больших списков ArrayList, чьи возможности постоянно меняются?

Answer 1

1. Класс называется ArrayList, потому что он основан на массиве.Емкость - это размер массива, для которого требуется блок непрерывной динамической памяти.Однако обратите внимание, что сам массив содержит только ссылки на элементы, которые являются отдельными объектами в куче.
2. Увеличение емкости требует выделения нового, большего массива и копирования всех ссылок изстарый массив - новый, после чего старый становится пригодным для сборки мусора.
3. Вы привели основной случай, когда производительность может быть проблемой.На практике я никогда не видел, чтобы это действительно становилось проблемой, поскольку объекты-элементы обычно занимают гораздо больше памяти (и, возможно, процессорного времени), чем список.

Answer 2

ArrayList реализован так:

class ArrayList {
  private Object[] elements;
}

Емкость - это размер этого массива.

Теперь, если ваша емкость равна 10, и вы добавляете 11-й элемент, ArrayList сделает это:

Object[] newElements = new Object[capacity * 1.5];
System.arraycopy(this.elements, newElements);
this.elements = newElements;

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

С другой стороны, если указать емкость 1 000 000 и добавить только 3 элемента в ArrayList, это тоже довольно плохо.

Правило большого пальца: если вы знаете емкость, укажите ее. Если вы не уверены, но знаете верхнюю границу, укажите это. Если вы просто не уверены, используйте значения по умолчанию.

Answer 3

Емкость, как вы ее описали - непрерывная память, выделенная для ArrayList для хранения значений. ArrayList хранит все значения в массиве и автоматически изменяет размер массива для вас. Это приводит к накладным расходам на управление памятью при изменении размера.

Если я правильно помню, Java увеличивает размер резервного массива ArrayList с размера N до размера 2N + 2, когда вы пытаетесь добавить еще один элемент, который может занять емкость. Я не знаю, к какому размеру он увеличивается, когда вы используете метод insert (или аналогичный) для вставки в определенное положение за пределами емкости или даже разрешает ли это.

Вот пример, который поможет вам подумать о том, как это работает. Изобразите каждый пробел между | s как ячейку в массиве поддержки:

| | |

размер = 0 (не содержит элементов), емкость = 2 (может содержать 2 элемента).

|1| |

размер = 1 (содержит 1 элемент), емкость = 2 (может содержать 2 элемента).

|1|2|

размер = 2, емкость = 2. Добавление другого элемента:

|1|2|3| | | |

размер увеличен на 1, емкость увеличена до 6 (2 * 2 + 2). Это может быть дорого с большими массивами, так как выделение большой смежной области памяти может потребовать небольшой работы (в отличие от LinkedList, который выделяет много маленьких фрагментов памяти), потому что JVM должен искать подходящее местоположение и может попросить у ОС больше памяти. Также дорого копировать большое количество значений из одного места в другое, что будет сделано после обнаружения такого региона.

Мое эмпирическое правило таково: если вы знаете емкость, которая вам потребуется, используйте ArrayList, потому что будет только одно распределение, и доступ будет очень быстрым. Если вы не знаете требуемой емкости, используйте LinkedList, поскольку добавление нового значения всегда требует одинакового объема работы, и копирование не требуется.

Answer 4

1) Какими хорошими способами можно определить, какую емкость представляет с точки зрения памяти?

... (непрерывная?) Память, выделенная для ArrayList?

Да, ArrayList поддерживается массивом, который представляет собой размер внутреннего массива.

... объем памяти ArrayLists на (куче?)?

Да, чем больше размер массива, тем больше занимаемого массива пространства.

2) Тогда, если вышеприведенное верно, для изменения емкости требуются некоторые накладные расходы на управление памятью?

Это так. Когда список становится достаточно большим, выделяется больший массив и содержимое копируется. Предыдущий массив может быть отброшен и помечен для сбора мусора.

3) У кого-нибудь есть пример, где № 2 был или мог быть проблемой производительности? Кроме, может быть, большого количества больших списков ArrayList, чья емкость постоянно изменяется?

Да, если вы создаете ArrayList с начальной емкостью 1 (например), и ваш список значительно расширяется. Если вы заранее знаете количество элементов для хранения, вам лучше запросить начальную емкость такого размера.

Однако Я думаю, что это должно быть низким в вашем списке приоритетов, хотя копирование массива может происходить очень часто, оно оптимизировано с ранних стадий Java и не должно вызывать беспокойства. Думаю, лучше было бы выбрать правильный алгоритм. Помните: Преждевременная оптимизация - корень всего зла

См. Также: Когда использовать LinkedList вместо ArrayList