Структуры данных: динамический массив

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

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

Динамические массивы ограниченного размера и емкость

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

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

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

Геометрическое расширение и амортизированная стоимость

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

function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // изменить размер в два раза 
        // по сравнению с текущей емкостью:
        a.capacity ← a.capacity * 2 
        // скопировать содержимое 
        // в новую ячейку памяти
    a[a.size] ← e
    a.size ← a.size + 1

При вставке n элементов емкости образуют геометрическую прогрессию. Расширение массива на любую постоянную пропорцию a гарантирует, что вставка n элементов занимает в общем O(n) времени, а это означает, что каждая вставка занимает амортизированное постоянное время. Многие динамические массивы также освобождают часть основного хранилища, если его размер падает ниже определенного порога, например 30% емкости. Этот порог должен быть строго меньше, чем 1/a, чтобы обеспечить гистерезис (обеспечить стабильную полосу, чтобы избежать многократного роста и сокращения) и поддерживать смешанные последовательности вставок и удалений с амортизированными постоянными затратами.

Динамические массивы являются распространенным примером при обучении амортизированному анализу.

Фактор роста

Коэффициент роста для динамического массива зависит от нескольких факторов, включая компромисс между пространством-временем и алгоритмы, используемые в самом распределителе памяти. Для фактора роста a среднее время на операцию вставки составляет около a/(a-1), в то время как количество потерянных ячеек ограничено выше (a-1)n. Если в распределителе памяти используется алгоритм первичного размещения, то значения коэффициента роста, такие как a=2, могут привести к тому, что динамическому расширению массива не хватит памяти, даже если значительный объем памяти все еще будет доступен. Были различные обсуждения идеальных значений факторов роста, в том числе предложения по золотому сечению, а также значение 1,5. Однако во многих учебниках a = 2 используется для простоты и анализа.

Ниже приведены факторы роста, используемые несколькими популярными реализациями:

Производительность

Сравнение списковых структур данных

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

Получение или установка значения по определенному индексу (постоянное время)
Перебор элементов по порядку (линейное время, хорошая производительность кеша)
Вставка или удаление элемента в середине массива (линейное время)
Вставка или удаление элемента в конце массива (постоянное амортизированное время)

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

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

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

Варианты

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

Гудрич представил алгоритм динамического массива, называемый многоуровневыми векторами, который обеспечивает производительность O(sqrt(n)) для вставок или удалений с сохранением порядка из середины массива.

Дерево хэшированного массива (HAT) - это алгоритм динамического массива, опубликованный Ситарски в 1996 году. Хэшированное дерево массивов тратит порядка sqrt(n) объема пространства хранения, где n - количество элементов в массиве. Алгоритм имеет O(1) амортизированную производительность при добавлении серии объектов в конец дерева хешированного массива.

В работе 1999 г. Brodnik et al. описали структуру данных многоуровневого динамического массива, которая тратит впустую только sqrt(2) пространства для n элементов в любой момент времени, и они доказывают нижнюю границу, показывающую, что любой динамический массив должен тратить столько места, если операции должны оставаться амортизированными постоянным временем. Кроме того, они представляют вариант, в котором увеличение и уменьшение буфера имеет не только амортизированное, но и наихудшее постоянное время.

Языковая поддержка

C++ std::vector и Rust std::vec::Vec - это реализации динамических массивов, а также классы ArrayList, поставляемые с Java API и .NET Framework.

Общий класс List<>, поставляемый с версией 2.0 .NET Framework, также реализован с использованием динамических массивов. OrderedCollection в Smalltalk - это динамический массив с динамическим начальным и конечным индексами, что делает удаление первого элемента также O(1).

Реализация списка типов данных (list datatype) Python представляет собой динамический массив.

Delphi и D реализуют динамические массивы в основе языка.

Универсальный пакет Ada Ada.Containers.Vectors обеспечивает реализацию динамического массива для данного подтипа.

Многие языки сценариев, такие как Perl и Ruby, предлагают динамические массивы как встроенный примитивный тип данных.

Несколько кроссплатформенных сред предоставляют реализации динамических массивов для C, включая CFArray и CFMutableArray в Core Foundation, а также GArray и GPtrArray в GLib.

Поиск по этому блогу

Alex tools