В информатике , в динамический массив , расширяемым массивом , перезначительном массив , динамическую таблицу , изменяемый массив или список массива является произвольным доступом , список с переменной размер структуры данных , которая позволяет элементам быть добавлены или удалены. Он поставляется со стандартными библиотеками на многих современных основных языках программирования. Динамические массивы преодолевают ограничение статических массивов , которые имеют фиксированную емкость, которую необходимо указать при распределении.
Динамический массив - это не то же самое, что динамически выделяемый массив, который представляет собой массив , размер которого фиксируется при выделении массива, хотя динамический массив может использовать такой массив фиксированного размера в качестве серверной части. [1]
Динамические массивы и емкость ограниченного размера [ править ]
Простой динамический массив может быть создан путем выделения массива фиксированного размера, обычно большего, чем количество элементов, требуемых немедленно. Элементы динамического массива хранятся непрерывно в начале базового массива, а оставшиеся позиции ближе к концу базового массива зарезервированы или не используются. Элементы могут быть добавлены в конец динамического массива за постоянное времяиспользуя зарезервированное пространство, пока это пространство не будет использовано полностью. Когда все пространство израсходовано и нужно добавить дополнительный элемент, тогда необходимо увеличить размер базового массива фиксированного размера. Обычно изменение размера является дорогостоящим, поскольку оно включает выделение нового базового массива и копирование каждого элемента из исходного массива. Элементы могут быть удалены с конца динамического массива за постоянное время, так как изменение размера не требуется. Число элементов, используемых содержимым динамического массива, - это его логический размер или размер , а размер базового массива называется емкостью динамического массива или физическим размером , который является максимально возможным размером без перемещения данных. [2]
Массив фиксированного размера будет достаточным в приложениях, где максимальный логический размер фиксирован (например, по спецификации) или может быть вычислен до выделения массива. Динамический массив может быть предпочтительнее, если:
- максимальный логический размер неизвестен или его трудно вычислить до выделения массива
- считается, что максимальный логический размер, указанный в спецификации, вероятно, изменится
- амортизированная стоимость изменения размера динамического массива не оказывает существенного влияния на производительность или быстродействие
Геометрическое расширение и амортизированная стоимость [ править ]
Чтобы избежать затрат на многократное изменение размера, динамические массивы изменяют размер на большую величину, например удваивают размер, и используют зарезервированное пространство для будущего расширения. Операция добавления элемента в конец может работать следующим образом:
function insertEnd ( dynarray a , element e ) if ( a . size == a . capacity ) // изменить размер a в два раза больше его текущей емкости: a . емкость ← a . capacity * 2 // (скопируйте содержимое в новое место в памяти) a [ a . размер ] ← е а . размер ← a . размер + 1При вставке n элементов емкости образуют геометрическую прогрессию . Расширение массива любой постоянной пропорцией a гарантирует, что вставка n элементов занимает в целом O ( n ) времени, что означает, что каждая вставка занимает амортизированное постоянное время. Многие динамические массивы также освобождают часть базового хранилища, если его размер падает ниже определенного порога, например 30% от емкости. Этот порог должен быть строго меньше 1 / a , чтобы обеспечить гистерезис. (обеспечить стабильную полосу, чтобы избежать повторного увеличения и уменьшения) и поддерживать смешанные последовательности вставок и удалений с амортизированной постоянной стоимостью.
Динамические массивы являются распространенным примером при обучении амортизированному анализу . [3] [4]
Фактор роста [ править ]
Фактор роста для динамического массива зависит от нескольких факторов, включая компромисс между пространством и временем и алгоритмы, используемые в самом распределителе памяти. Для фактора роста a среднее время на операцию вставки составляет примерно a / ( a -1), в то время как количество потраченных впустую клеток ограничено выше ( a -1) n [ необходима ссылка ] . Если в распределителе памяти используется алгоритм распределения первого соответствия , то значения коэффициента роста, такие как a = 2, могут вызвать нехватку памяти при динамическом расширении массива, даже если значительный объем памяти все еще может быть доступен. [5]Были различные дискуссии об идеальных значениях фактора роста, включая предложения по золотому сечению, а также по значению 1,5. [6] Однако во многих учебниках для простоты и анализа используется a = 2. [3] [4]
Ниже приведены факторы роста, используемые несколькими популярными реализациями:
| Выполнение | Фактор роста ( а ) |
|---|---|
| Java ArrayList [1] | 1,5 (3/2) |
| Python PyListObject [7] | ~ 1,125 (п + п >> 3) |
| Microsoft Visual C ++ 2013 [8] | 1,5 (3/2) |
| G ++ 5.2.0 [5] | 2 |
| Clang 3.6 [5] | 2 |
| Безумие Facebook / FBVector [9] | 1,5 (3/2) |
| Ржавчина Vec [10] | 2 |
Производительность [ править ]
| Связанный список | Множество | Динамический массив | Сбалансированное дерево | Список произвольного доступа | Дерево хешированных массивов | |
|---|---|---|---|---|---|---|
| Индексирование | Θ ( п ) | Θ (1) | Θ (1) | Θ (журнал n) | Θ (log n) [11] | Θ (1) |
| Вставить / удалить в начале | Θ (1) | Нет данных | Θ ( п ) | Θ (журнал n) | Θ (1) | Θ ( п ) |
| Вставить / удалить в конце | Θ (1) когда известен последний элемент ; Θ ( n ) когда последний элемент неизвестен | Нет данных | Θ (1) с амортизацией | Θ (журнал n ) | Не указано [11] | Θ (1) с амортизацией |
| Вставить / удалить посередине | время поиска + Θ (1) [12] [13] | Нет данных | Θ ( п ) | Θ (журнал n ) | Не указано [11] | Θ ( п ) |
| Пустое пространство (в среднем) | Θ ( п ) | 0 | Θ ( n ) [14] | Θ ( п ) | Θ ( п ) | Θ ( √ п ) |
Динамический массив имеет производительность, аналогичную массиву, с добавлением новых операций для добавления и удаления элементов:
- Получение или установка значения по определенному индексу (постоянное время)
- Итерация по элементам по порядку (линейное время, хорошая производительность кеша)
- Вставка или удаление элемента в середине массива (линейное время)
- Вставка или удаление элемента в конце массива (постоянное амортизированное время)
Динамические массивы выигрывают от многих преимуществ массивов, включая хорошую локальность ссылок и использование кэша данных , компактность (низкое использование памяти) и произвольный доступ . Обычно у них есть только небольшие фиксированные дополнительные накладные расходы для хранения информации о размере и емкости. Это делает динамические массивы привлекательным инструментом для создания структур данных, удобных для кеширования . Однако в таких языках, как Python или Java, которые применяют семантику ссылок, динамический массив обычно не будет хранить фактические данные, а скорее будет хранить ссылки.к данным, которые находятся в других областях памяти. В этом случае последовательный доступ к элементам в массиве фактически будет включать доступ к нескольким несмежным областям памяти, поэтому многие преимущества дружественности к кэшу этой структуры данных теряются.
По сравнению со связанными списками динамические массивы имеют более быстрое индексирование (постоянное время по сравнению с линейным временем) и, как правило, более быструю итерацию из-за улучшенной локальности ссылки; однако динамические массивы требуют линейного времени для вставки или удаления в произвольном месте, так как все следующие элементы должны быть перемещены, а связанные списки могут делать это за постоянное время. Этот недостаток смягчается за счет использования гэп-буфера и многоуровневых векторных вариантов, обсуждаемых ниже в разделе « Варианты» . Кроме того, в сильно фрагментированной области памяти может быть дорого или невозможно найти непрерывное пространство для большого динамического массива, тогда как связанные списки не требуют, чтобы вся структура данных хранилась непрерывно.
Сбалансированное дерево может хранить список, обеспечивая при этом всех операциях как в динамических массивах и связанные списки достаточно эффективно, но и введение в конце и итерации по списку медленнее , чем для динамического массива, в теории и на практике, из - за не- непрерывное хранилище и накладные расходы на обход / управление деревом.
Варианты [ править ]
Промежуточные буферы похожи на динамические массивы, но позволяют выполнять эффективные операции вставки и удаления, сгруппированные в одном и том же произвольном месте. Некоторые DEQUE реализация использует двусторонние очереди массива , которые позволяют амортизированное постоянное время ввода / удаление на обоих концах, а не только с одной стороны.
Гудрич [15] представил алгоритм динамического массива, называемый многоуровневыми векторами, который обеспечивает производительность O (n 1 / k ) для вставок и удалений из любого места в массиве, а также O (k) получения и установки, где k ≥ 2 - постоянный параметр.
Дерево хэшированных массивов (HAT) - это алгоритм динамического массива, опубликованный Ситарски в 1996 году. [16] Дерево хешированных массивов расходует впустую n 1/2 объема памяти, где n - количество элементов в массиве. Алгоритм имеет амортизированную производительность O (1) при добавлении серии объектов в конец дерева хешированного массива.
В статье 1999 г. [17] Brodnik et al. описывают многоуровневую структуру данных динамического массива, которая тратит только n 1/2 пространства для n элементов в любой момент времени, и они доказывают нижнюю границу, показывающую, что любой динамический массив должен тратить столько места, если операции должны оставаться амортизированными в постоянное время . Кроме того, они представляют вариант, при котором увеличение и уменьшение буфера не только амортизировало, но и в худшем случае постоянное время.
Bagwell (2002) [18] представил алгоритм VList, который можно адаптировать для реализации динамического массива.
Языковая поддержка [ править ]
C ++ «s std::vectorи ржавчины » ы std::vec::Vecявляются реализациями динамических массивов, как и ArrayList[19] классы , поставляемые с Java API и .NET Framework . [20]
Универсальный List<>класс, поставляемый с .NET Framework версии 2.0, также реализован с помощью динамических массивов. Smalltalk «s OrderedCollectionпредставляет собой динамический массив с динамическим начальным и конечным-индексом, что делает удаление первого элемента также O (1).
Python «s listреализация типа данных представляет собой динамический массив.
Delphi и D реализуют динамические массивы в ядре языка.
Ада «s Ada.Containers.Vectorsобщий пакет обеспечивает динамическую реализацию массива для данного подтипа.
Многие языки сценариев, такие как Perl и Ruby, предлагают динамические массивы как встроенный примитивный тип данных .
Несколько рамок кроссплатформенных обеспечивают динамические реализации массивов для C , в том числе CFArrayи CFMutableArrayв Основном фонде , а также GArrayи GPtrArrayв БОЙКОМ .
Common Lisp обеспечивает элементарную поддержку векторов изменяемого размера, позволяя настраивать встроенный arrayтип как настраиваемый и место вставки с помощью указателя заполнения .
Ссылки [ править ]
- ^ a b См., например, исходный код класса java.util.ArrayList из OpenJDK 6 .
- ^ Ламберт, Кеннет Альфред (2009), «Физический размер и логический размер» , Основы Python: от первых программ до структур данных , Cengage Learning, стр. 510, ISBN 978-1423902188
- ^ a b Гудрич, Майкл Т .; Тамассия, Роберто (2002), «1.5.2 Анализ реализации расширяемого массива», Разработка алгоритмов: основы, анализ и примеры в Интернете , Wiley, стр. 39–41..
- ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «17.4 Динамические таблицы». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 416–424. ISBN 0-262-03293-7.
- ^ a b c «Вектор C ++ STL: определение, фактор роста, функции-члены» . Архивировано из оригинала на 2015-08-06 . Проверено 5 августа 2015 .
- ^ "векторный коэффициент роста 1,5" . comp.lang.c ++. модерируется . Группы Google.
- ^ Список реализации объекта из github.com/python/cpython/, получено 23 марта 2020 г.
- ^ Брайс, Хади. «Анализ вектора C ++ STL: Часть 3 - Емкость и размер» . Микромистерии . Проверено 5 августа 2015 .
- ^ "facebook / глупость" . GitHub . Проверено 5 августа 2015 .
- ^ "ржавчина / ржавчина" . GitHub . Проверено 9 июня 2020 .
- ^ a b c Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Труды Седьмой Международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. DOI : 10.1145 / 224164.224187 .
- ^ Основной доклад дня 1 - Бьярн Страуструп: Стиль C ++ 11 на GoingNative 2012 на channel9.msdn.com с 45-й или 44-й минуты
- ^ Обработка чисел: почему вы никогда, никогда, НИКОГДА не должны использовать связанный список в своем коде снова на kjellkod.wordpress.com
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF) , Департамент компьютерных наук, Университет Ватерлоо
- ^ Гудрич, Майкл Т .; Клосс II, John G. (1999), "Многоуровневое Vectors: Эффективная динамическая Массивы для ранга на основе последовательностей" , семинар по Алгоритмам и структуры данных , Lecture Notes в области компьютерных наук, 1663 : 205-216 , да : 10,1007 / 3-540 -48447-7_21 , ISBN 978-3-540-66279-2
- ^ Ситарски, Эдвард (сентябрь 1996 г.), «Шляпы: деревья массива хеширования» , Аллея алгоритмов, журнал доктора Добба , 21 (11)
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (PDF) (Технический отчет CS-99-09), Департамент компьютерных наук, Университет Ватерлоо
- ^ Багвелл, Фил (2002), Быстрые функциональные списки, хеш-списки, Deques и массивы переменной длины , EPFL
- ^ Javadoc на
ArrayList - ^ Класс ArrayList
Внешние ссылки [ править ]
- Словарь алгоритмов и структур данных NIST: динамический массив
- VPOOL - реализация динамического массива на языке Си.
- CollectionSpy - профилировщик Java с явной поддержкой для отладки проблем, связанных с ArrayList и Vector.
- Структуры открытых данных - Глава 2 - Списки на основе массивов , Пат Морин
