stringtranslate.com

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

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

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

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

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

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

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

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

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

function insertEnd ( dynarray a , element e ) if ( a . size == a . capacity ) // изменяет размер a до удвоенного текущего размера: a . capacity ← a . capacity * 2 // (скопируйте содержимое в новое место памяти здесь) 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 [ необходима цитата ] . Если распределитель памяти использует алгоритм распределения по принципу «первый подходящий» , то такие значения фактора роста, как a = 2, могут привести к тому, что расширение динамического массива исчерпает память, даже если значительный объем памяти все еще может быть доступен. [5] Были различные обсуждения идеальных значений фактора роста, включая предложения по золотому сечению , а также значение 1,5. [6] Однако во многих учебниках  для простоты и целей анализа используется a = 2. [3] [4]

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

Реализация типа данных Pythonlist представляет собой динамический массив, шаблон роста которого следующий: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... [29]

В основе языков Delphi и D лежат динамические массивы.

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

Многие языки сценариев, такие как 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. ^ ab Goodrich, Michael T. ; Tamassia, Roberto (2002), "1.5.2 Анализ реализации расширяемого массива", Algorithm Design: Foundations, Analysis and Internet Examples , Wiley, стр. 39–41.
  4. ^ ab Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "17.4 Динамические таблицы". Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 416–424. ISBN 0-262-03293-7.
  5. ^ abc "C++ STL vector: definition, growth factor, member functions". Архивировано из оригинала 2015-08-06 . Получено 2015-08-05 .
  6. ^ "фактор роста вектора 1,5". comp.lang.c++.moderated . Группы Google. Архивировано из оригинала 2011-01-22 . Получено 2015-08-05 .
  7. ^ Реализация объекта списка с github.com/python/cpython/, получено 23.03.2020.
  8. ^ Brais, Hadi. "Dissecting the C++ STL Vector: Часть 3 - Емкость и размер". Micromysteries . Получено 2015-08-05 .
  9. ^ "facebook/folly". GitHub . Получено 2015-08-05 .
  10. ^ "rust-lang/rust". GitHub . Получено 2020-06-09 .
  11. ^ "golang/go". GitHub . Получено 2021-09-14 .
  12. ^ "Модель памяти Ним". zevv.nl . Получено 2022-05-24 .
  13. ^ "sbcl/sbcl". GitHub . Получено 2023-02-15 .
  14. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, Э.Д. (1999), Изменяемые массивы в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , Кафедра компьютерных наук, Университет Ватерлоо
  15. ^ abc Крис Окасаки (1995). «Чисто функциональные списки случайного доступа». Труды Седьмой международной конференции по языкам функционального программирования и архитектуре компьютеров : 86–95. doi :10.1145/224164.224187.
  16. ^ Гудрич, Майкл Т.; Клосс II, Джон Г. (1999), «Многоуровневые векторы: эффективные динамические массивы для ранговых последовательностей» , Практикум по алгоритмам и структурам данных , Lecture Notes in Computer Science, 1663 : 205–216, doi :10.1007/3-540-48447-7_21, ISBN 978-3-540-66279-2
  17. ^ ab Sitarski, Edward (сентябрь 1996 г.), "HAT: деревья хэшированных массивов", Algorithm Alley, Журнал доктора Добба , 21 (11)
  18. ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, Э.Д. (1999), Изменяемые массивы в оптимальном времени и пространстве (PDF) (технический отчет CS-99-09), Кафедра компьютерных наук, Университет Ватерлоо
  19. ^ Багвелл, Фил (2002), Быстрые функциональные списки, хэш-списки, деки и массивы переменной длины, EPFL
  20. ^ Майк Лэм. «Динамические массивы».
  21. ^ «Амортизированное время».
  22. ^ «Дерево хэшированного массива: эффективное представление массива».
  23. ^ «Разные представления о сложности».
  24. ^ Питер Канковски. «Динамические массивы в C».
  25. ^ Javadoc наArrayList
  26. ^ Блох, Джошуа (2018). «Effective Java: Programming Language Guide» (третье изд.). Addison-Wesley. ISBN 978-0134685991.
  27. ^ Класс ArrayList
  28. ^ Скит, Джон. C# in Depth . Мэннинг. ISBN 978-1617294532.
  29. ^ listobject.c (github.com)

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