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

Question

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

Answer 1

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

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

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

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

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

Для меньшего A o _total больше, но вы не тратите так много памяти. Пока он растет геометрически, время вставки равно 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

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

Answer 4

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

Answer 5

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

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

  

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

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

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

  

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

     

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

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

Answer 6

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

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

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

Answer 7

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