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

Question

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

Answer 1

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

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

Если вы вставите n элементов и вы увеличите коэффициент A по мере необходимости, то будет выполнено o _total = n + ΣA ⁱ [0 A n] операций. В худшем случае вы используете 1/A от выделенной памяти.

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

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

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

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

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

Answer 2

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

Answer 3

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

Скажем, мы начинаем с 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 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. Однако в абсолютном выражении удвоение будет иметь тенденцию быть более эффективным в обычном сценарии.