stringtranslate.com

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

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

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

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

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

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

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

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

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

function InsertEnd ( dynarray a , element e ) if ( a . size == a . емкость ) // изменяем размер a в два раза по сравнению с текущей емкостью: a . мощность ← а . емкость * 2 // (скопируйте сюда содержимое в новую ячейку памяти) a [ a . размер ] ← е а . размер ← а . размер + 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]

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

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

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

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

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

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

Варианты

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

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

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

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

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

Наивные массивы с изменяемым размером, также называемые «худшей реализацией» массивов с изменяемым размером, сохраняют выделенный размер массива достаточно большим для всех содержащихся в нем данных, возможно, путем вызова realloc для каждого элемента, добавляемого в массив. Наивные массивы с изменяемым размером — это самый простой способ реализации массива с изменяемым размером в C. Они не тратят впустую память, но добавление в конец массива всегда занимает Θ( n ) времени. [19] [22] [23] [24] [25] Линейно растущие массивы предварительно выделяют («отбрасывают») Θ(1) пространство каждый раз, когда изменяют размер массива, что делает их во много раз быстрее, чем наивные массивы с изменяемым размером - - добавление в конец массива по-прежнему занимает время Θ( n ), но с гораздо меньшей константой. Наивные массивы с изменяемым размером и линейно растущие массивы могут быть полезны, когда приложению с ограниченным пространством требуется множество небольших массивов с изменяемым размером; их также часто используют в качестве образовательного примера, ведущего к экспоненциальному росту динамических массивов. [26]

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

C++ и std::vectorRust являются реализациями std::vec::Vecдинамических массивов, как и классы ArrayList[27] , поставляемые с Java API [28] :236  и .NET Framework . [29] [30] : 22 

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

Реализация типа данных Pythonlist представляет собой динамический массив, шаблон роста которого: 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в GLib .

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

Рекомендации

  1. ^ ab См., например, исходный код класса java.util.ArrayList из OpenJDK 6.
  2. ^ Ламберт, Кеннет Альфред (2009), «Физический размер и логический размер», Основы Python: от первых программ через структуры данных , Cengage Learning, стр. 510, ISBN 978-1423902188
  3. ^ Аб Гудрич, Майкл Т .; Тамассиа, Роберто (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. ^ abc «Вектор C++ STL: определение, фактор роста, функции-члены». Архивировано из оригинала 6 августа 2015 г. Проверено 5 августа 2015 г.
  6. ^ «Векторный коэффициент роста 1,5» . comp.lang.c++.модерируется . Группы Google. Архивировано из оригинала 22 января 2011 г. Проверено 5 августа 2015 г.
  7. ^ Список реализации объекта с сайта github.com/python/cpython/, получено 23 марта 2020 г.
  8. ^ Брайс, Хади. «Анализ вектора STL C++: Часть 3 — Емкость и размер». Микротайны . Проверено 5 августа 2015 г.
  9. ^ "Фейсбук/глупость". Гитхаб . Проверено 5 августа 2015 г.
  10. ^ "Ржавчина-ланг/ржавчина" . Гитхаб . Проверено 9 июня 2020 г.
  11. ^ "Голанг/го". Гитхаб . Проверено 14 сентября 2021 г.
  12. ^ "Модель памяти Нима" . zevv.nl. _ Проверено 24 мая 2022 г.
  13. ^ "сбкл/сбкл". Гитхаб . Проверено 15 февраля 2023 г.
  14. ^ Основной доклад дня 1 — Бьерн Страуструп: Стиль C++11 на GoingNative 2012 на канале 9.msdn.com с 45-й минуты или с 44-й минуты
  15. ^ Обработка чисел: почему вы никогда и НИКОГДА не должны снова использовать связанный список в своем коде на kjellkod.wordpress.com
  16. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , факультет компьютерных наук, Университет Ватерлоо
  17. ^ abc Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы седьмой международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. дои : 10.1145/224164.224187.
  18. ^ Гудрич, Майкл Т .; Клосс II, Джон Г. (1999), «Многоуровневые векторы: эффективные динамические массивы для ранговых последовательностей» , Семинар по алгоритмам и структурам данных , Конспект лекций по информатике, 1663 : 205–216, doi : 10.1007/3-540 -48447-7_21, ISBN 978-3-540-66279-2
  19. ^ Аб Ситарски, Эдвард (сентябрь 1996 г.), «HAT: деревья хешированных массивов», Algorithm Alley, Dr. Dobb's Journal , 21 (11)
  20. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (PDF) (Технический отчет CS-99-09), Факультет компьютерных наук, Университет Ватерлоо
  21. ^ Бэгвелл, Фил (2002), Быстрые функциональные списки, хэш-списки, деки и массивы переменной длины, EPFL
  22. ^ Майк Лам. «Динамические массивы».
  23. ^ «Амортизированное время».
  24. ^ «Дерево хешированного массива: эффективное представление массива» .
  25. ^ «Различные понятия сложности».
  26. ^ Питер Канковски. «Динамические массивы в C».
  27. ^ Javadoc наArrayList
  28. ^ Блох, Джошуа (2018). «Эффективная Java: Руководство по языку программирования» (третье изд.). Аддисон-Уэсли. ISBN 978-0134685991.
  29. ^ Класс ArrayList
  30. ^ Скит, Джон. C# в глубине . Мэннинг. ISBN 978-1617294532.
  31. ^ listobject.c (github.com)

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