Динамический массив
В информатике динамический массив , расширяемый массив , массив с изменяемым размером , динамическая таблица , изменяемый массив или список массивов — это с произвольным доступом и переменным размером, структура данных списка которая позволяет добавлять или удалять элементы. Он поставляется со стандартными библиотеками многих современных основных языков программирования . Динамические массивы преодолевают ограничения статических массивов , которые имеют фиксированную емкость, которую необходимо указать при выделении .
Динамический массив — это не то же самое, что динамически выделяемый массив или массив переменной длины , каждый из которых представляет собой массив, размер которого фиксируется при выделении массива, хотя динамический массив может использовать такой массив фиксированного размера в качестве обратного массива. конец. [ 1 ]
Динамические массивы и емкость ограниченного размера
[ редактировать ]Простой динамический массив может быть создан путем выделения массива фиксированного размера, обычно большего, чем количество сразу требуемых элементов. Элементы динамического массива хранятся последовательно в начале базового массива, а оставшиеся позиции ближе к концу базового массива зарезервированы или не используются. Элементы можно добавлять в конец динамического массива за постоянное время, используя зарезервированное пространство, пока это пространство не будет полностью использовано. Когда все пространство занято и необходимо добавить дополнительный элемент, размер базового массива фиксированного размера необходимо увеличить. Обычно изменение размера обходится дорого, поскольку оно включает в себя выделение нового базового массива и копирование каждого элемента из исходного массива. Элементы можно удалять из конца динамического массива за постоянное время, поскольку изменение размера не требуется. Количество элементов, используемых содержимым динамического массива, называется его логическим размером или размером , а размер базового массива называется динамическим массивом. емкость или физический размер , который является максимально возможным размером без перемещения данных. [ 2 ]
Массив фиксированного размера будет достаточен в приложениях, где максимальный логический размер фиксирован (например, по спецификации) или может быть рассчитан до выделения массива. Динамический массив может быть предпочтительнее, если:
- максимальный логический размер неизвестен или его трудно вычислить до выделения массива
- считается, что максимальный логический размер, заданный спецификацией, вероятно, изменится
- амортизированная стоимость изменения размера динамического массива существенно не влияет на производительность или скорость реагирования.
Геометрическое расширение и амортизированная стоимость
[ редактировать ]Чтобы избежать многократных затрат на изменение размера, динамические массивы изменяются на большую величину, например, в два раза, и используют зарезервированное пространство для будущего расширения. Операция добавления элемента в конец может работать следующим образом:
function insertEnd(dynarray a, element e)
if (a.size == a.capacity)
// resize a to twice its current capacity:
a.capacity ← a.capacity * 2
// (copy the contents to the new memory location here)
a[a.size] ← e
a.size ← a.size + 1
При n вставке элементов мощности образуют геометрическую прогрессию . Расширение массива на любую постоянную пропорцию a гарантирует, что вставка n элементов в целом займет O ( n ) , а это означает, что каждая вставка занимает амортизированное постоянное время. Многие динамические массивы также освобождают часть базового хранилища, если его размер падает ниже определенного порога, например 30 % емкости. Этот порог должен быть строго меньше 1/ a, чтобы обеспечить гистерезис (обеспечивать стабильный диапазон во избежание многократного роста и сжатия) и поддерживать смешанные последовательности вставок и удалений с амортизированной постоянной стоимостью.
Динамические массивы являются распространенным примером при обучении амортизированному анализу . [ 3 ] [ 4 ]
Фактор роста
[ редактировать ]Коэффициент роста динамического массива зависит от нескольких факторов, включая компромисс между пространством и временем и алгоритмы, используемые в самом распределителе памяти. Для фактора роста a среднее время на операцию вставки составляет около a /( a −1), а количество потраченных впустую ячеек ограничено сверху ( a −1) n [ нужна ссылка ] . Если распределитель памяти использует алгоритм распределения по первому варианту , то значения коэффициента роста, такие как = 2, могут привести к нехватке памяти при расширении динамического массива, даже если значительный объем памяти все еще может быть доступен. [ 5 ] Были различные дискуссии по поводу идеальных значений фактора роста, включая предложения по золотому сечению , а также по значению 1,5. [ 6 ] Однако во многих учебниках a = 2. для простоты и анализа используется значение [ 3 ] [ 4 ]
Ниже приведены факторы роста, используемые в нескольких популярных реализациях:
| Выполнение | Фактор роста ( а ) |
|---|---|
| Список массивов Java [ 1 ] | 1.5 (3/2) |
| Python PyListObject [ 7 ] | ~1,125 (n + (n >> 3)) |
| Microsoft Visual С++ 2013. [ 8 ] | 1.5 (3/2) |
| Г++ 5.2.0 [ 5 ] | 2 |
| Кланг 3.6 [ 5 ] | 2 |
| Facebook глупость/FBVector [ 9 ] | 1.5 (3/2) |
| Ржавая вещь [ 10 ] | 2 |
| Перейти кусочками [ 11 ] | между 1,25 и 2 |
| Нет последовательностей [ 12 ] | 2 |
| SBCL ( Common Lisp ) Векторы [ 13 ] | 2 |
| Список С# ( .NET 8) | 2 |
Производительность
[ редактировать ]| Пик (индекс) |
Изменить (вставить или удалить) в… | Лишнее пространство, средний | |||
|---|---|---|---|---|---|
| Начало | Конец | Середина | |||
| Связанный список | Θ( п ) | Я(1) | Θ(1) — известный конечный элемент; Θ( n ), неизвестный конечный элемент |
Θ( п ) [ 14 ] [ 15 ] | Θ( п ) |
| Множество | Я(1) | — | — | — | 0 |
| Динамический массив | Я(1) | Θ( п ) | Θ(1) амортизировано | Θ( п ) | Θ( п ) [ 16 ] |
| Сбалансированное дерево | Θ(логарифм n) | Θ(логарифм n) | Θ(логарифм n ) | Θ(логарифм n ) | Θ( п ) |
| произвольного доступа Список | Θ(логарифм n) [ 17 ] | Я(1) | — [ 17 ] | — [ 17 ] | Θ( п ) |
| Дерево хешированного массива | Я(1) | Θ( п ) | Θ(1) амортизировано | Θ( п ) | Θ(√ п ) |
Динамический массив имеет производительность, аналогичную массиву, с добавлением новых операций по добавлению и удалению элементов:
- Получение или установка значения по определенному индексу (постоянное время)
- Перебор элементов по порядку (линейное время, хорошая производительность кэша)
- Вставка или удаление элемента в середине массива (линейное время)
- Вставка или удаление элемента в конце массива (постоянное амортизированное время)
Динамические массивы извлекают выгоду из многих преимуществ массивов, включая хорошую локальность ссылок и использование кэша данных , компактность (низкое использование памяти) и произвольный доступ . Обычно они имеют лишь небольшие фиксированные дополнительные затраты на хранение информации о размере и емкости. Это делает динамические массивы привлекательным инструментом для построения кэширования , удобных для структур данных . Однако в таких языках, как Python или Java, которые применяют семантику ссылок, динамический массив обычно не хранит фактические данные, а скорее хранит ссылки на данные, которые находятся в других областях памяти. В этом случае последовательный доступ к элементам массива фактически будет включать доступ к нескольким несмежным областям памяти, поэтому многие преимущества удобства кэширования этой структуры данных будут потеряны.
По сравнению со связанными списками динамические массивы имеют более быструю индексацию (постоянное время по сравнению с линейным временем) и, как правило, более быструю итерацию из-за улучшенной локальности ссылки; однако динамическим массивам требуется линейное время для вставки или удаления в произвольном месте, поскольку все последующие элементы должны быть перемещены, в то время как связанные списки могут делать это за постоянное время. Этот недостаток смягчается вариантами буфера пробелов и многоуровневых векторов, обсуждаемыми в разделе «Варианты» ниже. Кроме того, в сильно фрагментированной области памяти может быть дорого или невозможно найти непрерывное пространство для большого динамического массива, тогда как связанные списки не требуют непрерывного хранения всей структуры данных.
Сбалансированное дерево может хранить список, при этом достаточно эффективно обеспечивая все операции как динамических массивов, так и связанных списков, но и вставка в конце, и итерация по списку выполняются медленнее, чем для динамического массива, в теории и на практике, из-за отсутствия непрерывное хранение и накладные расходы на обход дерева/манипулирование.
Варианты
[ редактировать ]Буферы пробелов похожи на динамические массивы, но позволяют эффективно выполнять операции вставки и удаления, сгруппированные вблизи одного и того же произвольного места. Некоторые реализации деков используют деки массива , которые позволяют амортизированную вставку/удаление с постоянным временем на обоих концах, а не только на одном конце.
Гудрич [ 18 ] представил алгоритм динамического массива, называемый многоуровневыми векторами , который обеспечивает O ( n 1/ к ) производительность при вставках и удалениях из любого места массива и O ( k ) get и set, где k ≥ 2 — постоянный параметр.
Дерево хешированных массивов (HAT) — это алгоритм динамических массивов, опубликованный Ситарски в 1996 году. [ 19 ] Дерево хешированного массива теряет порядок n 1/2 объем памяти, где n — количество элементов массива. Алгоритм имеет амортизированную производительность O (1) при добавлении серии объектов в конец дерева хешированного массива.
В статье 1999 года [ 20 ] Бродник и др. описать многоуровневую структуру данных динамического массива, которая тратит только n 1/2 места для n элементов в любой момент времени, и они доказывают нижнюю границу, показывающую, что любой динамический массив должен тратить столько места, чтобы операции оставались амортизированными с постоянным временем. Кроме того, они представляют вариант, в котором увеличение и уменьшение буфера не только амортизирует, но и в худшем случае постоянное время.
Бэгвелл (2002) [ 21 ] представил алгоритм VList, который можно адаптировать для реализации динамического массива.
Наивные массивы с изменяемым размером, также называемые «худшей реализацией» массивов с изменяемым размером, сохраняют выделенный размер массива достаточно большим для всех содержащихся в нем данных, возможно, путем вызова realloc для каждого элемента, добавляемого в массив. Наивные массивы изменяемого размера — это самый простой способ реализации массива изменяемого размера в C. Они не тратят впустую память, но добавление в конец массива всегда занимает Θ( n ) времени. [ 19 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] Линейно растущие массивы предварительно выделяют («тратят») пространство Θ(1) каждый раз, когда изменяют размер массива, что делает их во много раз быстрее, чем наивные массивы с изменяемым размером — добавление в конец массива по-прежнему занимает Θ( n ) времени. но с гораздо меньшей константой. Наивные массивы с изменяемым размером и линейно растущие массивы могут быть полезны, когда приложению с ограниченным пространством требуется множество небольших массивов с изменяемым размером; они также часто используются в качестве образовательного примера, ведущего к экспоненциальному росту динамических массивов. [ 26 ]
Языковая поддержка
[ редактировать ]C ++ std::vector и Раста std::vec::Vec являются реализациями динамических массивов, как и ArrayList[ 27 ] классы, поставляемые с Java API [ 28 ] : 236 и .NET Framework . [ 29 ] [ 30 ] : 22
Общий List<> Класс, поставляемый с версией 2.0 .NET Framework, также реализован с помощью динамических массивов. Smalltalk 's OrderedCollection представляет собой динамический массив с динамическим начальным и конечным индексом, что делает удаление первого элемента также O (1).
Python list Реализация типа данных представляет собой динамический массив, шаблон роста которого: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76,... [ 31 ]
Delphi и D реализуют динамические массивы в основе языка.
Есть Ada.Containers.Vectors универсальный пакет обеспечивает реализацию динамического массива для данного подтипа.
Многие языки сценариев, такие как Perl и Ruby, предлагают динамические массивы в качестве встроенного примитивного типа данных .
Несколько кросс-платформенных платформ предоставляют реализации динамических массивов для C , в том числе CFArray и CFMutableArray в Core Foundation и GArray и GPtrArray в ГЛиб .
Common Lisp обеспечивает элементарную поддержку векторов изменяемого размера, позволяя настраивать встроенные array тип можно изменить , а место вставки — указателем заполнения .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б См., например, исходный код класса java.util.ArrayList из OpenJDK 6 .
- ^ Ламберт, Кеннет Альфред (2009), «Физический размер и логический размер» , «Основы Python: от первых программ через структуры данных» , Cengage Learning, стр. 510, ISBN 978-1423902188
- ^ Jump up to: а б Гудрич, Майкл Т .; Тамассиа, Роберто (2002), «1.5.2 Анализ реализации расширяемого массива», Разработка алгоритмов: основы, анализ и примеры из Интернета , Wiley, стр. 39–41 .
- ^ Jump up to: а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «17.4 Динамические таблицы». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 416–424. ISBN 0-262-03293-7 .
- ^ Jump up to: а б с «Вектор C++ STL: определение, коэффициент роста, функции-члены» . Архивировано из оригинала 6 августа 2015 г. Проверено 5 августа 2015 г.
- ^ «векторный коэффициент роста 1,5» . comp.lang.c++.модерируется . Группы Google. Архивировано из оригинала 22 января 2011 г. Проверено 5 августа 2015 г.
- ^ Список реализации объекта с сайта github.com/python/cpython/, получено 23 марта 2020 г.
- ^ Брайс, Хади. «Анализ вектора STL в C++: Часть 3 — Емкость и размер» . Микротайны . Проверено 5 августа 2015 г.
- ^ «фейсбук/глупость» . Гитхаб . Проверено 5 августа 2015 г.
- ^ "ржавчина-ланг/ржавчина" . Гитхаб . Проверено 9 июня 2020 г.
- ^ «голанг/гоу» . Гитхаб . Проверено 14 сентября 2021 г.
- ^ «Модель памяти Ним» . zevv.nl. Проверено 24 мая 2022 г.
- ^ "сбкл/сбкл" . Гитхаб . Проверено 15 февраля 2023 г.
- ^ Основной доклад дня 1 — Бьерн Страуструп: Стиль C++11 на GoingNative 2012 на канале Channel9.msdn.com с 45-й минуты или с 44-й минуты.
- ^ Обработка чисел: почему вы никогда и НИКОГДА не должны снова использовать связанный список в своем коде на kjellkod.wordpress.com
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , факультет компьютерных наук, Университет Ватерлоо
- ^ Jump up to: а б с Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы седьмой международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. дои : 10.1145/224164.224187 .
- ^ Гудрич, Майкл Т .; Клосс II, Джон Г. (1999), «Многоуровневые векторы: эффективные динамические массивы для ранговых последовательностей» , Семинар по алгоритмам и структурам данных , Конспект лекций по информатике, 1663 : 205–216 , doi : 10.1007/3-540 -48447-7_21 , ISBN 978-3-540-66279-2
- ^ Jump up to: а б Ситарски, Эдвард (сентябрь 1996 г.), «HAT: деревья хешированных массивов» , Algorithm Alley, Dr. Dobb's Journal , 21 (11)
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (PDF) (Технический отчет CS-99-09), Факультет компьютерных наук, Университет Ватерлоо
- ^ Бэгвелл, Фил (2002), Быстрые функциональные списки, хэш-списки, деки и массивы переменной длины , EPFL
- ^ Майк Лам. «Динамические массивы» .
- ^ «Амортизированное время» .
- ^ «Дерево хешированного массива: эффективное представление массива» .
- ^ «Различные понятия сложности» .
- ^ Питер Канковски. «Динамические массивы в C» .
- ^ Javadoc на
ArrayList - ^ Блох, Джошуа (2018). «Эффективная Java: Руководство по языку программирования» (третье изд.). Аддисон-Уэсли. ISBN 978-0134685991 .
- ^ Класс ArrayList
- ^ Скит, Джон. C# в глубине . Мэннинг. ISBN 978-1617294532 .
- ^ listobject.c (github.com)
Внешние ссылки
[ редактировать ]- Словарь алгоритмов и структур данных NIST: динамический массив
- VPOOL — реализация динамического массива на языке C.
- CollectionSpy — профилировщик Java с явной поддержкой отладки проблем, связанных с ArrayList и Vector.
- Структуры открытых данных. Глава 2. Списки на основе массивов , Пэт Морин