хватайте -30% на все до 18 ноября
до 18 ноября
Хватай скидки -30% на все!
Черная пятница

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

Автор — Владимир Балун

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

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

1. Что такое статический массив?

Статический массив (static array) — это структура данных, которая хранит последовательность элементов одного типа данных. Размер такого массива задается при создании и в дальнейшем остается неизменным
Пример статического массива двухбайтовых элементов, где каждый элемент идет через 2 байта (адреса здесь и в последующих примерах указаны условно исключительно для визуализации)
Данные в статическом массиве располагаются последовательно, без каких-либо пропусков между элементами. Благодаря этому обеспечивается очень компактное хранение информации.

Это связано с тем, что в памяти хранятся только сами элементы массива. Дополнительные структуры, такие как указатели или служебные индексы (как, например, в связных списках), отсутствуют.

Слева и справа от статического массива располагается память, которая ему не принадлежит. Поэтому добавить новый элемент перед первым или после последнего элемента невозможно.
Слева и справа находится чужая память
По обе стороны массива могут находиться совершенно другие области памяти, в которых размещены другие данные или переменные программы. Именно поэтому массив нельзя просто «расширить», используя соседнюю память.

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

В рассматриваемом примере массив состоит из четырех элементов, то есть его длина равна 4.
Данная структура состоит из четырех элементов, то есть ее длина = 4
У статического массива есть еще одно важное преимущество по сравнению со многими другими статическими структурами данных.

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

2. Обращение к элементу массива

В большинстве языков программирования индексация статического массива начинается с нуля.

Предположим, массив называется data, и мы хотим обратиться к элементу data[2], чтобы прочитать его значение или записать новое.

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

У каждого массива есть адрес начала — адрес памяти, с которого начинается хранение его элементов. Аналогично и большинство других переменных имеют собственный адрес в памяти.

Представим, что адрес начала массива равен:

 ptr = 0x00 

На первый взгляд может показаться, что для получения адреса элемента с индексом 2 достаточно прибавить индекс к адресу:

 0x00 + 2 = 0x02 

Однако такой результат будет неверным. Причина заключается в том, что каждый элемент массива занимает 2 байта, а значит необходимо учитывать размер каждого элемента.

Поэтому индекс умножается на размер элемента (size = 2), после чего полученное смещение прибавляется к адресу начала массива.

 data[idx] == *(ptr + idx * size) 

Для второго элемента вычисление будет выглядеть следующим образом:

 data[2] == *(0x00 + 2 * 2) 
Формула поиска элемента с нужным индексом
Ключевая особенность этой операции заключается в том, что количество элементов в массиве никак не влияет на время доступа.

Современная оперативная память (RAM, Random Access Memory) позволяет обратиться к любому байту памяти напрямую. В данном случае программа просто вычисляет адрес нужного элемента по формуле и сразу получает к нему доступ.
Не имеет значения, содержит структура 10 элементов, 1000 элементов или 10 миллионов элементов — вычисление адреса выполняется одинаково.

Поэтому асимптотическая сложность обращения к элементу статического массива по индексу является константной: O(1).

3. Что такое динамический массив?

Динамический массив (Dynamic array) — это структура данных, размер которой может меняться во время выполнения программы
Пример структуры динамического массива на языке C++:
Пример динамического массива
Его основа является обычным статическим массивом, дополненным несколькими служебными полями:
  • ptr — указатель на начало массива;
  • size — количество элементов, которые сейчас находятся в массиве;
  • capacity — емкость массива, то есть максимальное количество элементов, которое можно разместить без выделения новой памяти.

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

4. Вставка элемента в массив

Вставка в конец динамического массива

Рассмотрим, как динамическая структура увеличивает свой размер.

Предположим, что в рассматриваемом примере поле size = 2. Это означает, что первые два элемента уже заняты, а следующий свободный элемент находится по индексу 2.
Обращение по индексу к элементу 2
Представим, что необходимо вставить элемент со значением 6. Для этого достаточно обратиться к свободной позиции по индексу и записать туда новое значение.
Вставка элемента со значением «6»
Операция вставки выглядит следующим образом:

 data[size] = x; 
 size++; 

Сначала через указатель data происходит обращение к элементу с индексом size, затем в эту позицию записывается значение x, после чего увеличивается поле size, т. е. выполняем инкремент.

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

Таким образом, если в динамической структуре еще есть свободное место, асимптотическая сложность вставки в конец составляет: O(1).
Изменение значения size с «2» на «3» в структуре данных

Вставка в начало динамического массива

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

Поэтому перед вставкой необходимо освободить место в начале массива. Для этого все существующие элементы последовательно сдвигаются на одну позицию вправо.
Сдвигаем все элементы вправо на одну ячейку
После этого в первую ячейку записывается новое значение, например 7.
Записываем на место первого элемента добавляемое значение «7»
В худшем случае придётся сдвинуть (n−1) элементов массива. Следовательно, время выполнения такой операции линейно зависит от размера массива, а ее асимптотическая сложность равна: O(n).

Именно поэтому вставка в конец массива выполняется быстро, а вставка в начало — значительно медленнее.
Происходит сдвиг элементов вправо и освобождение места для нового элемента
Добавление элемента «7» на освободившееся место и изменение size с «3» на «4»

Вставка в заполненный массив, или операция реаллокации

Теперь рассмотрим ситуацию, когда необходимо вставить новый элемент в конец массива, но свободного места уже не осталось.

В этом случае справа от динамической структуры также располагается чужая память, поэтому продолжить запись элементов невозможно.
Справа у массива находится чужая память, поэтому новый элемент вставлять некуда
Возникает ситуация, при которой значение size становится равно capacity.

Чтобы продолжить работу, необходимо выполнить реаллокацию — выделить новую область памяти, размер которой больше текущей. Как правило, ее размер увеличивают в два раза.
Шаг 1. Выделение новой области памяти
Выделяется новый массив, который в два раза больше предыдущего. Предположим, что адрес начала новой области памяти равен 0xA0.
Выделяем область памяти в 2 раза больше предыдущей с адресом начала массива 0xA0
Шаг 2. Копирование элементов
После выделения памяти все элементы старого массива последовательно копируются в новый.
Шаг 3. Обновление указателя
После завершения копирования указатель обновляется и начинает ссылаться уже на новую область памяти.
Обновляем указатель 0x00 на 0xA0
Старая структура после этого больше не используется. Если язык программирования использует ручное управление памятью, разработчик должен самостоятельно освободить старую область памяти. Если же используется автоматическое управление памятью, старый массив позднее будет удален сборщиком мусора, когда на него больше не останется ссылок.
Шаг 4. Обновление capacity и вставка нового элемента
После успешной реаллокации остается обновить значение capacity, увеличить его до нового размера, затем добавить новый элемент и увеличить значение size.
Обновляем capacity с «4» до «8», вставляем новый элемент «0» и обновляем size с «4» на «5»
Таким образом, реаллокация состоит из четырёх последовательных действий:
  • Выделение новой области памяти.
  • Копирование элементов.
  • Обновление указателя.
  • Обновление capacity, вставка нового элемента и увеличение size.

5. Амортизационный анализ

Как мы уже увидели, в большинстве случаев вставка элемента в конец динамического массива выполняется за константное время O(1).

Однако иногда свободное место заканчивается. Тогда массив приходится расширять: выделять новую область памяти, копировать в нее все существующие элементы и только после этого выполнять вставку. Такая операция уже имеет линейную сложность — O(n).
Возникает вопрос: какова асимптотическая сложность вставки в конец динамического массива?
Чтобы ответить на него, рассмотрим следующий пример на языке программирования Go:
Здесь создаётся пустая динамическая структура из 8 элементов, после чего элементы исходного массива по одному добавляются в массив copy.
На первый взгляд может показаться, что из-за реаллокаций операция вставки должна иметь квадратичную сложность.

Если рассматривать только худший случай, то действительно во время некоторых вставок потребуется копировать все уже существующие элементы массива. В таком случае можно получить оценку O(n²).

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

Давайте посчитаем, сколько раз удвоится массив из 8 элементов. Предположим, что при каждом расширении емкость массива увеличивается в два раза.

Тогда размер массива будет изменяться следующим образом:

1
1 2
1 2 3 4
1 2 3 4 5 6 7 8
Мы вставляем элементы «1», «1 2», «1 2 3 4» и так до «1 2 3 4 5 6 7 8», т. е. при каждой реаллокации массив удваивается
В данном примере рассматривается самая простая стратегия увеличения размера массива. Если массив каждый раз увеличивается в два раза, то количество реаллокаций будет равно log(n). То есть при увеличении количества элементов в несколько раз число реаллокаций растет значительно медленнее.

Теперь посчитаем, сколько элементов придётся копировать за все время работы. Во время каждой реаллокации копируется содержимое предыдущего массива. В итоге получится следующая последовательность:

n/8
n/4
n/2
...
Просчитываем, сколько раз нам придется перекопировать элементы: n/8, n/4, n/2 и т. д.
Финальную структуру копировать уже не требуется, поскольку после завершения всех вставок он остается последней версией массива.

Таким образом, суммарное количество копируемых элементов можно представить в виде ряда:

 n/8 + n/4 + n/2 + ... 

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

Получается, что суммарное количество операций можно оценить как:

 n + n = 2n 

С точки зрения асимптотики постоянный множитель роли не играет, поэтому итоговая сложность остаётся O(n).

Теперь рассмотрим стоимость одной операции вставки. Да, некоторые операции оказываются дорогими, поскольку требуют перекопировать весь массив, но такие операции происходят крайне редко.

Если разделить суммарную стоимость всех операций на количество выполненных вставок, получится следующая оценка:

 O(n) / n = O(1) 
  • Поясню на простом примере:
    Представим, что у меня есть шкафчик с игрушками. Я постепенно добавляю игрушки в этот шкафчик. Представим, что каждая игрушка, которую мы добавляем в шкафчик, платит небольшой взнос в копилку. Большинство взносов идут на то, чтобы просто положить игрушку. Но когда копилка накопила достаточно, то она тратит эту сумму на покупку нового шкафчика побольше, т. е. на переезд.

    В итоге получается, что каждая игрушка в среднем платит очень мало, потому что дорогие переезды случаются редко и оплачиваются многими будущими дешевыми операциями. Это означает, что n новых игрушек оплачивает стоимость большого переезда.

    Грубо говоря, стоимость переноса всех n-игрушек делится на n-операций, которые они смогут сделать до следующего большого переезда.

Что такое амортизированная константа?

Вставка элемента в конец динамического массива имеет амортизированную константную сложность.

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

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

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

Следовательно, вставка элемента в конец динамического массива имеет амортизированную константную сложность: O(amortized 1).

6. Удаление элемента из динамического массива

Удаление элемента с конца массива

Начнем с самого простого случая — удаления последнего элемента.

Предположим, что в массиве содержится четыре элемента. Чтобы удалить последний из них, достаточно уменьшить значение поля size с 4 до 3.
Для удаления элемента с конца сдвинуть size с «4» на «3»
При этом сам элемент можно даже не занулять. Причина заключается в том, что при следующей вставке программа снова обратится к позиции с индексом 3 и просто перезапишет ее новым значением. Старое значение при этом будет потеряно.

В некоторых реализациях элемент все же может зануляться явно, однако для корректной работы динамического массива это не является обязательным.

Поскольку операция сводится к уменьшению значения size (и, при необходимости, занулению одного элемента), ее асимптотическая сложность является константной: O(1).

Удаление элемента из начала массива

Теперь рассмотрим удаление первого элемента.

Если просто уменьшить значение size с 3 до 2, получится ситуация, при которой первый элемент перестанет использоваться, хотя место под него все еще останется выделенным.
При удалении из начала и изменении size не используется элемент из начала массива
Если повторить такую операцию несколько раз подряд, в начале массива начнут накапливаться неиспользуемые ячейки. Получится, что часть памяти фактически окажется потерянной, несмотря на то что она все еще входит в capacity массива.

Поэтому при удалении первого элемента применяется другой подход. После удаления все оставшиеся элементы последовательно сдвигаются на одну позицию влево.
После удаления элемента из начала постепенно переносим и другие элементы влево
В худшем случае потребуется переместить (n−1) элементов. Следовательно, сложность удаления первого элемента линейно зависит от размера массива и составляет O(n).

Именно поэтому удаление из начала массива считается значительно более дорогой операцией, чем удаление из конца.
Иногда порядок элементов внутри массива не имеет значения. Например, если массив используется просто как набор объектов и не требуется сохранять их последовательность. В этом случае можно воспользоваться небольшим хаком
Вместо того чтобы сдвигать все элементы, достаточно поменять местами первый и последний элементы массива:

 swap(data[0], data[size − 1]) 
Меняем местами первый элемент с последним
Операция обмена выполняется за константное время, поскольку обращения по индексам происходят за O(1). После обмена остается удалить последний элемент массива обычным способом — уменьшить значение size.
Удаляем ещё один элемент и меняем size с «2» на «1»
В результате вся операция также выполняется за константное время O(1).
Однако такой прием можно использовать только тогда, когда порядок элементов не имеет значения. Если необходимо сохранить исходную последовательность элементов, выполнять такую замену нельзя

Уменьшение capacity

После большого количества удалений может возникнуть ситуация, когда массив становится сильно разреженным. Например, большая часть ячеек динамической структуры уже не используется, однако значение capacity остается прежним.

Во многих языках программирования емкость динамической структуры автоматически не уменьшается. Это сделано для того, чтобы при последующих вставках не выполнять повторную реаллокацию.

Однако некоторые реализации динамических структур все же могут уменьшать capacity, если используется лишь небольшая часть выделенной памяти. Например, если заполнено только около 25% массива, может быть выполнена обратная реаллокация.

В этом случае:
  • выделяется новый массив меньшего размера;
  • оставшиеся элементы копируются в него;
  • указатель начинает ссылаться на новую область памяти;
  • значение capacity уменьшается, например, с 4 до 2.
При уменьшении capacity массив релоцируется в меньшую сторону: скопируется второй элемент «2», capacity уменьшится надвое, адрес указателя изменится на 0xB0
Таким образом, динамическая структура способна не только увеличиваться при нехватке памяти, но и уменьшаться, если большая часть выделенной памяти больше не используется.

7. Оптимизация реаллокации массива

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

В подобных системах неожиданная реаллокация может стать серьезной проблемой. Если во время добавления одного элемента потребуется скопировать миллиард элементов, такая операция займет слишком много времени и нарушит требования к производительности системы.
Возникает вопрос: как избежать длительной реаллокации?
Рассмотрим один из возможных подходов. Предположим, имеется небольшой массив из четырех элементов, который скоро полностью заполнится.
Небольшая структура перед расширением для вставки нового элемента
Вместо того чтобы хранить один статический массив, можно одновременно использовать два. При этом второй массив заранее создается в два раза больше первого.
Храним в памяти 2 статических массива, где один в 2 раза меньше другого
Теперь при каждой вставке нового элемента в первый массив одновременно копируются несколько элементов из первого массива во второй. Например, во время каждой операции вставки можно переносить по два элемента.
При вставке нового элемента в малый массив параллельно копируются два элемента из начала в большой массив
Благодаря этому копирование выполняется постепенно. Когда первый массив полностью заполнится, все его элементы уже окажутся перенесены во второй.
Как только первый массив заполняется, новый элемент добавляется во второй, в который уже заранее перенесены все элементы
После этого создается третий массив, который снова в два раза больше предыдущего. Во время работы со вторым массивом элементы начинают постепенно переноситься уже в третий.
Создаем третий массив в 2 раза больше предыдущего и копируем элементы из второго массива уже в него
Первый массив после завершения переноса больше не используется. Если язык программирования использует ручное управление памятью, память освобождается разработчиком. Если используется автоматическое управление памятью, старый массив позднее будет удален сборщиком мусора.
Таким образом, получается классический компромисс:
  • либо при каждой вставке приходится выполнять небольшую дополнительную работу по переносу нескольких элементов;
  • либо программа периодически сталкивается с дорогими реаллокациями, во время которых необходимо скопировать сразу весь массив.
Первый вариант позволяет распределить стоимость копирования между множеством операций и избежать длинных пауз во время работы программы, что особенно важно для систем реального времени.

8. Кейсы использования массивов на практике

Массив — одна из самых фундаментальных и востребованных структур данных в программировании. Практически любое приложение в той или иной степени использует его для хранения информации.

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

Заключение

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

Если хотите подробнее разобраться в работе статических и динамических массивов, то смотрите наше видео с наглядными примерами из курса по структурам данных.

Структуры данных без сложной математики

Бесплатный курс с базой по ассимптотическому анализу — для работы и подготовки к алгоритмическим собеседованиям
Другие статьи