Динамический массив - Dynamic array

Несколько значений вставляются в конец динамического массива с использованием геометрического расширения. Серые ячейки указывают пространство, зарезервированное для расширения. Большинство вставок выполняются быстро (постоянное время), а некоторые - медленно из-за необходимости перераспределения (Θ ( n ) времени, помеченного черепахами). Логический размер и емкость конечного массива показаны.

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

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

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

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

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

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

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

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

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 , чтобы обеспечить гистерезис (обеспечить стабильную полосу, чтобы избежать многократного роста и сжатия) и поддерживать смешанные последовательности вставок и удалений с амортизированной постоянной стоимостью.

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

Фактор роста

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

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

Реализация Фактор роста ( а )
Java ArrayList 1,5 (3/2)
Python PyListObject ~ 1,125 (п + п >> 3)
Microsoft Visual C ++ 2013 1,5 (3/2)
G ++ 5.2.0 2
Clang 3.6 2
Безумие Facebook / FBVector 1,5 (3/2)
Ржавчина Vec 2
Идти ломтиками от 1,25 до 2

Представление

Сравнение структур данных списка
Подглядывать Изменить (вставить или удалить) в… Избыточное пространство, в
среднем
Начало Конец Середина
Связанный список Θ ( п ) Θ (1) Θ (1), известный концевой элемент;
Θ ( n ), неизвестный конечный элемент 		Время пиктограммы +
Θ (1) 		Θ ( п )
Множество Θ (1) N / A N / A N / A 0
Динамический массив Θ (1) Θ ( п ) Θ (1) с амортизацией Θ ( п ) Θ ( п )
Сбалансированное дерево Θ (журнал n) Θ (журнал n) Θ (журнал n ) Θ (журнал n ) Θ ( п )
Список произвольного доступа Θ (журнал n) Θ (1) N / A N / A Θ ( п )
Дерево хешированных массивов Θ (1) Θ ( п ) Θ (1) с амортизацией Θ ( п ) Θ (√ п )

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

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

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

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

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

Варианты

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

Гудрич представил алгоритм динамического массива, называемый многоуровневыми векторами, который обеспечивает производительность O ( n 1 / k ) для вставок и удалений из любой точки массива, а также O ( k ) получения и установки, где k ≥ 2 - постоянный параметр.

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

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

Багвелл (2002) представил алгоритм VList, который можно адаптировать для реализации динамического массива.

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

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

Универсальный 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тип как настраиваемый и место вставки с помощью указателя заполнения .

использованная литература

  1. ^ a b См., например, исходный код класса java.util.ArrayList из OpenJDK 6 .
  2. ^ Ламберт, Кеннет Альфред (2009), «Физический размер и логический размер» , Основы Python: от первых программ до структур данных , Cengage Learning, стр. 510, ISBN 978-1423902188
  3. ^ a b Гудрич, Майкл Т .; Тамассия, Роберто (2002), «1.5.2 Анализ реализации расширяемого массива», Разработка алгоритмов: основы, анализ и примеры в Интернете , Wiley, стр. 39–41..
  4. ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «17.4 Динамические таблицы». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 416–424. ISBN 0-262-03293-7.
  5. ^ a b c "Вектор C ++ STL: определение, фактор роста, функции-члены" . Архивировано из оригинала на 2015-08-06 . Проверено 5 августа 2015 .
  6. ^ "векторный коэффициент роста 1,5" . comp.lang.c ++. модерируется . Группы Google.
  7. ^ Список реализации объекта из github.com/python/cpython/, получено 23 марта 2020 г.
  8. ^ Брайс, Хади. «Анализ вектора C ++ STL: Часть 3 - Емкость и размер» . Микромистерии . Проверено 5 августа 2015 .
  9. ^ "facebook / глупость" . GitHub . Проверено 5 августа 2015 .
  10. ^ "ржавчина / ржавчина" . GitHub . Проверено 9 июня 2020 .
  11. ^ "golang / go" . GitHub . Проверено 14 сентября 2021 .
  12. ^ Основной доклад дня 1 - Бьярн Страуструп: Стиль C ++ 11 на GoingNative 2012 на channel9.msdn.com с 45-й или 44-й минуты
  13. ^ Обработка чисел: почему вы никогда и НИКОГДА не должны использовать связанный список в своем коде снова на kjellkod.wordpress.com
  14. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF) , Департамент компьютерных наук, Университет Ватерлоо
  15. ^ a b c Крис Окасаки (1995). «Чисто функциональные списки с произвольным доступом». Труды Седьмой Международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. DOI : 10.1145 / 224164.224187 .
  16. ^ Гудрич, Майкл Т .; Клосс II, John G. (1999), "Многоуровневое Vectors: Эффективная динамическая Массивы для ранга на основе последовательностей" , семинар по Алгоритмам и структуры данных , Lecture Notes в области компьютерных наук, 1663 : 205-216 , да : 10,1007 / 3-540 -48447-7_21 , ISBN 978-3-540-66279-2
  17. ^ Sitarski, Эдвард (сентябрь 1996), "HATs: Hashed дерева массива" , алгоритм Alley, журнал доктор Добба , 21 (11)
  18. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (PDF) (Технический отчет CS-99-09), Департамент компьютерных наук, Университет Ватерлоо
  19. ^ Багвелл, Фил (2002), Быстрые функциональные списки, хэш-списки, Deques и массивы переменной длины , EPFL
  20. ^ Javadoc наArrayList
  21. ^ Класс ArrayList

внешние ссылки