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

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

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

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

Поддержка в языках программирования[править | править код]

Динамические массивы могут поддерживаться либо на уровне синтаксиса самого языка программирования, либо на уровне системных библиотек. Описание динамического массива может синтаксически отличаться от описания статического, но может и быть таким же. Во втором случае, как правило, все массивы в языке являются потенциально динамическими, и только от программиста зависит, использовать ли это свойство в каждом конкретном случае. При поддержке динамических массивов посредством системных библиотек они обычно реализуются в виде классов (в смысле ООП) или шаблонов (т. н. «дженериков»); описание массива в этом случае представляет собой инстанцирование класса или конкретизацию шаблона. В зависимости от языка, динамические массивы могут быть только одномерными массивами или иметь размерность два и более.

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

Реализация[править | править код]

Для массивов с возможностью динамического изменения размера при реализации приходится находить «золотую середину» между несколькими противоречивыми требованиями.

  1. Эффективность по памяти — реализация не должна приводить к существенному перерасходу памяти.
  2. Эффективность по производительности, которая включает в себя:
    • минимальные накладные расходы на изменение размера массива;
    • сохранение, по возможности, константного времени доступа на чтение/запись к элементам массива.
  3. Совместимость с обычными статическими массивами на низком уровне. Например, необходимым условием для применения динамического массива в вызовах функций API операционной системы может быть обязательное размещение элементов массива в непрерывном блоке физической оперативной памяти в порядке, соответствующем индексации массива. Если такое требование не выполняется, динамические массивы окажется невозможно использовать в сочетании с низкоуровневым кодом.

В зависимости от приоритета тех или иных требований выбирается отвечающий им способ реализации.

Массивы переменной длины[править | править код]

Реализация массивов переменной длины мало отличается от реализации обычных статических массивов. Массив элементов типа T переменной длины обычно хранится в непрерывном блоке оперативной памяти размером , где N — число элементов, указываемое при описании (создании) массива. То есть описание массива переменной длины, фактически, просто маскирует динамическое выделение памяти. Разница может состоять в том, что (например, как в Си стандарта C99 и позже) массиву переменной длины выделяется память на стеке, как другим автоматическим переменным, в то время как типовой способ динамического выделения памяти (в Си — функция malloc) выделяет память в куче. Кроме того, для массива переменной длины компилятор, как правило, автоматически генерирует код освобождения памяти при выходе объявленного массива из области видимости.

Перемещение массива в памяти[править | править код]

Наиболее распространённой для типичных процедурных компилируемых языков является реализация изменения размера массива путём перемещения его в динамической памяти.

  • Под массив выделяется фрагмент ОЗУ, размер которого больше требуемого т. н. логического размера (size или length). Количество элементов, которое фактически может быть размещено в этой памяти, называется ёмкостью (capacity) динамического массива. Текущая длина массива хранится в отдельном счётчике. Она может использоваться для определения текущего размера, а также для контроля выхода за границы массива, если язык поддерживает такой контроль. Таким образом, в действительности динамический массив — это массив фиксированного размера, в котором занята только часть ячеек.
  • Команда увеличения размера массива, если новый размер не превышает ёмкости, просто изменяет счётчик длины массива до нужного размера. С самим массивом никаких изменений при этом не происходит.
  • Команда увеличения размера, в которой новый размер превышает ёмкость, приводит к перемещению массива в памяти:
  1. выделяется новый фрагмент ОЗУ, размер которого превышает размер массива;
  2. содержимое массива копируется во вновь выделенную память;
  3. размер и ёмкость массива изменяются устанавливаются в новые значения;
  4. в служебной структуре, хранящей данные массива, значение указателя на данные массива меняется на новое;
  5. запускается команда освобождения ранее выделенного под массив фрагмент ОЗУ; если язык поддерживает автоматическое управление памятью, то освобождение ранее выделенной под массив памяти обычно остаётся за сборщиком мусора.
  • Команда уменьшения размера массива может приводить к перемещению его в памяти, если в результате её выполнения процент занятых ячеек в массиве падает ниже определённого значения. Перемещение при этом проводится по той же схеме, что и в случае команды увеличения массива.

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

  • Начальная ёмкость и приращение ёмкости при увеличении размера. Может задаваться либо относительной величиной (определённая доля от логической длины массива), либо абсолютным приращением сверх требуемой длины массива. Чем больше эти параметры, тем позже, при том же режиме заполнения массива, потребуется следующее перемещение, но и тем больше памяти потенциально останется неиспользуемой. Расширение массива на любой постоянный коэффициент гарантирует, что вставка n-элементов займет O(n) времени, это означает, что каждая вставка занимает конкретное, определенное время. Численное значение этого коэффициента приводит к разным показателям: среднее время вставки операции составляет a/(a-1), в то время как число потраченных впустую ячеек составляет (a-1)n. Значение этой константы в различных приложениях и библиотеках может быть разным: во многих учебниках используют значение 2, но в реализации ArrayList языка Java используется коэффициент 3/2, в некоторых других случаях используют a=9/8.
  • Минимальная ёмкость. Обычно задаётся из соображений эффективности, чтобы не терять производительность при частых изменениях размеров небольших массивов. Практически её установка означает, что все динамические массивы размером менее минимальной ёмкости в действительности будут терять память.
  • Процент минимального заполнения массива. Определяет, когда будет происходить перемещение после сокращения размера массива. Чем больше эта величина, тем чаще при уменьшении размера массива будет происходить перемещение. Чем она меньше, тем больше памяти при уменьшении размера массива будет оставаться занятой, но не используемой.

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

Другие динамические алгоритмы размещения[править | править код]

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

Использование[править | править код]

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

В отсутствие в языке поддержки динамических массивов решение типичных задач обработки входных данных неопределённого размера сводится к одной из стратегий:

  • выделение статического массива заведомо достаточного размера для полного размещения данных;
  • выделение статического массива относительно небольшого размера и использование его в качестве буфера: входные данные частями последовательно загружаются в массив, обрабатываются и выводятся по частям;
  • применение иных динамических структур данных, например, списков.

Первый вариант практически применим только когда размер набора входных данных меняется в небольшом, жёстко ограниченном диапазоне (например, в текстовой обработке ограничение в 1000 знаков на строку вполне приемлемо). В противном случае выбор маленького массива будет ограничивать функциональность программы, а большого (так, чтобы заведомо хватило для любых входных данных) приведёт к неэффективному расходованию памяти. Буферизация обработки усложняет алгоритм по сравнению с первым вариантом. А другие динамические структуры данных в задачах обработки больших последовательностей простых данных по эффективности не могут сравниться с массивом.

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

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

Примеры[править | править код]

Паскаль[править | править код]

Динамические массивы поддерживаются Delphi, FreePascal, но не Turbo Pascal.

var
  byteArray : Array of Byte; // Одномерный массив
  multiArray : Array of Array of string;  // Многомерный массив
  ...
begin
  ... 
  // Установить размер одномерного массива в n элементов 
  SetLength (byteArray, n); 
  // Доступ к динамическому массиву аналогичен доступу к обычному.
  // Индексация всегда начинается с нуля, индексы - всегда целые.
  byteArray[0] := 10;
  // Изменить размер до m элементов.
  SetLength(byteArray, m);
  ...
  // Установить размер двумерного массива в X*Y элементов
  SetLength(multiArray, X, Y);
  muliArray[7,35] := 'ru.wikipedia.org';
  ...
end.

Си[править | править код]

В самом языке Си нет динамических массивов, но функции стандартной библиотеки malloc, free и realloc позволяют реализовать массив переменного размера:

  int *mas = (int*)malloc(sizeof(int) * n);  // Создание массива из n элементов типа int
  ...
  mas = (int*)realloc(mas, sizeof(int) * m); // Изменение размера массива с n на m с сохранением содержимого
  ...
  free(mas); // Освобождение памяти после использования массива

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

Многомерный динамический массив может быть создан как массив указателей на массивы:

int **A = (int **)malloc(N*sizeof(int *));
for(int i = 0; i < N; i++) {
    A[i] = (int *)malloc(M*sizeof(int));
}

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

Некоторые компиляторы Си предоставляют нестандартную библиотечную функцию void *alloca(size_t size), несколько упрощающую работу с динамическими массивами. Эта функция выделяет память не в куче, как malloc, а на стеке, и эта память автоматически освобождается при достижении оператора return. То есть при выделении памяти динамического массива этой функцией его не нужно удалять вручную, но такой массив невозможно вернуть из функции в точку вызова.

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

  void func(int arraySize) {
    int mas[arraySize]; // Описание массива переменной длины
    for (int i = 0; i < arraySize; ++i) {
      mas[i] = anotherFunc(i); // Обращение к элементам массива
    }
    ... 
  }

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

С++[править | править код]

В C++ поддерживаются функции работы с памятью из стандартной библиотеки Си, но их использование не рекомендуется. Массив переменной длины здесь также можно выделить с помощью стандартных команд работы с динамической памятью new и delete:

  // Создание массива длиной n
  int *mas = new int[n]; 
  ... 
  // Освобождение памяти массива
  delete []mas;

Как и в случае с Си, здесь требуется отслеживать время жизни массива, чтобы избежать утечки памяти или, наоборот, преждевременного освобождения памяти. Аналога realloc здесь нет, так что изменить размер массива можно только вручную, выделив новую память нужного размера и перенеся в неё данные.

Библиотечным решением является шаблонный класс std::vector:

  std::vector<int> mas; // Создать пустой вектор
  mas.reserve(100);     // Выделить вектору память под 100 элементов (размер останется нулевым)
  mas.resize(50);       // Задать размер вектора в 50 элементов
  mas[i] = i;           // Обращение к элементу по индексу
  mas.push_back(100);   // Добавить элемент
  x = mas.back;         // Обращение к последнему элементу
  mas.pop_back();       // Удалить последний элемент
  std::cout << mas.size() << " " << mas.capacity() << "\n"; // Вывести ёмкость и размер
  mas.shrink_to_fit();  // Уменьшить ёмкость до размера

std::vector имеет множество методов и переопределённых операторов, часть из которых показана выше на примере. Они позволяют обращаться по индексу, изменять в любую сторону размер массива, использовать его как стек. Управляемым является не только актуальный размер, но и ёмкость вектора, что позволяет оптимизировать процесс выделения памяти. Стандарт C++ требует от реализации обязательного выполнения условий:

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

Ссылки[править | править код]