Динамический массив

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение:

Массив — набор однотипных переменных, доступ к которым осуществляется по индексу. Динамический массив может изменять свой размер в зависимости от количества элементов в нём.

Операции

Определим операции, которые мы будем применять к динамическому массиву:

get(i)

Возвращает значение [math]i[/math]-ой ячейки массива. Время выполнения — [math]O(1)[/math].

set(i,x)

В [math]i[/math]-ую ячейку массива записывается элемент [math]x[/math]. Время выполнения — [math]O(1)[/math].

add(x)

Добавление в массив элемента [math]x[/math]. Время выполнения — [math]O(1)[/math]; в худшем случае, при котором необходимо перенести все элементы из текущего массива во вдвое больший массив — [math]O(n)[/math] ([math]n[/math] — размер массива).

del()

Удаляет последний элемент массива. В случае, если количество элементов в массиве в [math]C[/math] раз меньше его длины, то происходит сжатие в [math]B[/math] раз. ([math]C,B[/math] — константы, зависящие от реализации). Время выполнения операции в худшем случае — [math]O(n)[/math].

size()

Возвращает количество элементов массива. Время выполнения — [math]O(1)[/math].

Амортизационная стоимость каждой операции

Пусть наш массив расширяется в [math]2[/math] раза, и уменьшается в [math]2[/math] раза, когда длина массива в [math]4[/math] раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет [math]O(1)[/math].

Метод предоплаты

Стоимость операции add(x)

Иллюстрация

Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили [math]i[/math]-ый элемент, мы будем класть по одной монетке к элементам с номерами [math]i[/math] и [math]i-\frac{n}{2}[/math]). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — [math]3[/math], и среднее время её работы — [math]O(1)[/math].

Стоимость операции del()

При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции [math]i \bmod \dfrac{n}{4}[/math]. Тогда даже в самом худшем случае (только что расширились, а потом [math]\dfrac{n}{4}[/math] удалили) у каждого элемента из первых [math]\dfrac{n}{4}[/math] будет по монете и на удаление надо будет потратить только [math]1[/math] монету.

Метод потенциалов

За потенциал примем число: [math]\Phi(c, s) = \begin{cases} 2s-c, & \text{if } s\geqslant\frac{1}{2}c \\ \frac{1}{2}c-s, & \text{if } s\lt \frac{1}{2}c \end{cases}[/math], где [math]c[/math] — размер массива, [math]s[/math] — число элементов массива.

Стоимость операции add(x)

• [math]\frac{s}{c} = 1[/math], массив расширяется: [math] a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 [/math]

• [math]1\gt \frac{s}{c}\geqslant\frac{1}{2}[/math], массив не расширяется: [math]a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3[/math]

• [math]\frac{s}{c}\lt \frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}[/math], массив не расширяется:

[math]a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+3s-\frac{3}{2}c= 3 + \frac{s}{c}3c-\frac{3}{2}c \lt 3+\frac{3}{2}c-\frac{3}{2}c=3[/math]

• [math]\frac{s}{c}\lt \frac{1}{2}, \frac{s+1}{c}\lt \frac{1}{2}[/math], массив не расширяется: [math]a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0[/math]

В итоге, средняя стоимость операции — [math]3[/math], а среднее время работы — [math]O(1)[/math].

Стоимость операции del()

• [math]\frac{s}{c}=\frac{1}{4}[/math], массив сужается: [math]a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1[/math]
• [math]\frac{1}{4}\lt \frac{s}{c}\lt \frac{1}{2}[/math], массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2[/math]
• [math]\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}\lt \frac{1}{2}\Rightarrow s=\frac{1}{2}c[/math], массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2[/math]
• [math]\frac{s}{c}\gt \frac{1}{2}[/math], массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0[/math]

Средняя стоимость операции — [math]2[/math], а среднее время работы — [math]O(1)[/math].

Динамические массивы в современных языках программирования

Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.

С++ — vector

В С++ динамический массив используется в структуре vector, она описана в STL(<vector>). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в [math]2[/math] раза при компиляции GNU C++ и в [math]1.5[/math] раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен [math]0[/math].

Java — ArrayList

В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в [math]1.5[/math] раза. Причем начальный размер равен [math]10[/math]. Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

Источники информации

• Wikipedia — Dynamic array
• Wikipedia — Динамический массив