Почему векторный массив удваивается?

Question

Почему классическая реализация Vector (ArrayList для Java) удваивает свой внутренний размер массива при каждом расширении вместо того, чтобы утроить или увеличить его в четыре раза?

Answer 1

При расчете среднего времени вставки в вектор необходимо учитывать нерастущие вставки и растущие вставки.

Назовите общее количество операций для вставки n элементов o _всего , а среднее o _{среднее} .

Если вы вставите n предметов, и вы увеличитесь в A раз по мере необходимости, тогда будет o _всего = n + & Sigma ; A ⁱ [0 A n] операций. В худшем случае вы используете 1 / A выделенного хранилища.

Интуитивно, A = 2 означает, что в худшем случае у вас есть o _всего = 2n , поэтому o _{среднее} - это O (1), и в худшем случае вы используете 50% выделенного хранилища.

Для большего A у вас есть меньшее o _общее , но больше потраченного впустую хранилища.

Для меньших A , o _всего больше, но вы не тратите так много времени на хранение. Пока он растет геометрически, время вставки равно O (1), но константа будет увеличиваться.

Для факторов роста 1,25 (красный), 1,5 (голубой), 2 (черный), 3 (синий) и 4 (зеленый) эти графики показывают эффективность точечного и среднего размера (соотношение размера / выделенного пространства; чем больше, тем лучше ) слева и время эффективности (соотношение вставок / операций; чем больше, тем лучше) справа для вставки 400 000 элементов. 100% эффективности пространства достигается для всех факторов роста непосредственно перед изменением размера; случай для A = 2 показывает эффективность по времени между 25% и 50% и эффективность использования пространства около 50%, что хорошо для большинства случаев:

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

Answer 2

Экспоненциальное удвоение размера массива (или строки) - хороший компромисс между наличием достаточного количества ячеек в массиве и потерей слишком большого количества памяти.

Скажем, мы начинаем с 10 элементов:

1 - 10
2 - 20
3 - 40
4 - 80
5 - 160

Когда мы утраиваем размер, мы слишком быстро растем

1 - 10
2 - 30
3 - 90
4 - 270
5 - 810

На практике вы бы выросли, может быть, в 10 или 12 раз. Если вы утроите, вы, возможно, сделаете это 7 или 8 раз - время выполнения для перераспределения - это несколько раз, это достаточно мало, чтобы беспокоиться о нем, но вы с большей вероятностью полностью превысите требуемый размер.

Answer 3

Любой кратный является компромиссом. Сделайте его слишком большим, и вы потеряете слишком много памяти. Сделайте его слишком маленьким, и вы будете тратить много времени на перераспределение и копирование. Я полагаю, что есть дублирование, потому что оно работает и его очень легко реализовать. Я также видел проприетарную STL-подобную библиотеку, которая использует 1,5 как множитель для того же самого - я думаю, что ее разработчики решили удвоить тратить слишком много памяти.

Answer 4

Если бы вы выделяли блок памяти необычного размера, то когда этот блок освобождается (либо потому, что вы изменяете его размер, либо он получает GC'd), в памяти возникает дыра необычного размера, которая может вызвать головные боли для менеджера памяти. Поэтому обычно предпочтительнее распределять память по двум степеням. В некоторых случаях базовый менеджер памяти будет выдавать вам блоки только определенных размеров, а если вы запросите странный размер, он округляется до следующего большего размера. Поэтому вместо того, чтобы запрашивать 470 единиц, возвращать 512 в любом случае, а затем снова изменять размер, как только вы используете все 470, которые вы просили, лучше всего просто попросить 512 для начала.

Answer 5

Лично я думаю, что это произвольный выбор. Мы могли бы использовать базу e вместо базы 2 (вместо удвоения только кратного размера на (1 + e).)

Если вы собираетесь добавлять большое количество переменных к вектору, тогда было бы полезно иметь высокую базу (чтобы уменьшить количество копий, которые вы будете делать.) С другой стороны, если вам нужно хранить только несколько членов на avg, тогда низкая база будет в порядке и уменьшит количество накладных расходов, следовательно, ускорит процесс.

База 2 - это компромисс.

Answer 6

Если вы спрашиваете о конкретной реализации Java Vector и ArrayList , то это не обязательно удваивается при каждом расширении.

Из Javadoc для вектора:

Каждый вектор пытается оптимизировать управление хранением, поддерживая capacity и capacityIncrement. Емкость всегда как минимум равна размеру вектора; обычно он больше, потому что по мере добавления компонентов к вектору память вектора увеличивается кусками до размера capacityIncrement. Приложение может увеличить емкость вектора перед вставкой большого количества компонентов; это уменьшает количество постепенного перераспределения.

Один из конструкторов для вектора позволяет указать начальный размер и приращение емкости для вектора. Класс Vector также предоставляет ensureCapacity(int minCapacity) и setSize(int newSize) для ручной настройки минимального размера вектора и для изменения размера вектора самостоятельно.

Класс ArrayList очень похож:

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

Приложение может увеличить емкость экземпляра ArrayList, прежде чем добавлять большое количество элементов с помощью операции sureCapacity. Это может уменьшить количество добавочного перераспределения.

Если вы спрашиваете об общей реализации вектора, тогда выбор увеличения размера и на сколько компромисс. Как правило, векторы поддерживаются массивами. Массивы имеют фиксированный размер. Изменение размера вектора, поскольку он заполнен, означает, что вы должны скопировать все элементы массива в новый, больший массив. Если вы сделаете ваш новый массив слишком большим, то вы выделите память, которую вы никогда не будете использовать. Если он слишком мал, копирование элементов из старого массива в новый, более крупный массив может занять слишком много времени - операция, которую вы не хотите выполнять очень часто.

Answer 7

Нет никаких причин для удвоения производительности по сравнению с утроением или увеличением в четыре раза, поскольку все они имеют одинаковые профили производительности O. Однако в абсолютном выражении в обычном сценарии удвоение будет более экономичным.