В компютърните науки динамичният масив е масив с променлив размер, в който могат да се добавят или премахват елементи. Той се поддържа от стандартните библиотеки в много от модерните програмни езици.
Динамичният масив не бива да се бърка с динамично разпределения масив, чийто размер е предварително определен още при неговата декларация, макар че динамичният масив може да използва точно такъв масив с предварително известен брой елементи за своя подложка.See, for example, the source code of java.util.ArrayList class from OpenJDK 6
Динамични масиви с ограничен размер и капацитет Най-елементарният динамичен масив може да се създаде, чрез заделянето на масив с фиксиран размер и разделянето му на две части: първата част съхранява елементите на динамичния масив, а втората част се резервира или въобще не се използва. Така ние можем да добавяме или премахваме елементи в края на динамичния масив, използвайки резервираната памет, докато тя не се изчерпа. Броя на елементите използвани от съдържанието на един динамичен масив са неговия логически размер или просто размер, докато размерът на свободната част от масива се нарича капацитет или физически размер на динамичния масив, който е възможно най-големия размер без да се налага презаделяне на памет. Lambert, Kenneth Alfred (2009), "Physical size and logical size", Fundamentals of Python: From First Programs Through Data Structures (Cengage Learning), p. 510
При апликациите, където логическия размер е ограничен, структурите от данни с фиксиран размер са напълно достатъчни. Въпреки че това не е много добра практика ако по-късно се наложи използването на допълнителна памет, която в конкретния случай няма как да се набави. Един програмист би предпочел да пише код и да прави всеки масив способен да се преоразмерява, след което отново да се връща към масив с фиксиран размер по време на програмната оптимизация. Преоразмеряването може обаче да се окаже доста скъпо струващо удоволствие, което често се изразява с копирането на цялото съдържание на масива.
Геометрична експанзия и амортизирана стойност Преоразмеряването изисква много висок разход, тъй като включва изграждането на още един масив с увеличен размер следван от копие на елементите от „стария“ в „новия“ масив. За да се избегне тази процедура всеки път когато се добавя нов елемент, динамичните масиви се уголемяват като удвояват обема си (вместо с една единица). По този начин се резервира място за бъдещи елементи. Добавянето на елемент в края може да работи по следния начин:
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 елементи, капацитетът образуват геометрична прогресия. Разширяване на масива от всеки постоянен процент гарантира, че поставянето на N елементи отнема O (N) време като цяло, което означава, че всяка манипулация отнема амортизирано константно време. Стойността на този дял води до компромис пространство-време: средното време за една операция на вмъкване е приблизително а/(а-1), докато броя на загубените клетки е допълнително ограничен до (а-1)n. Изборът на „a“ е независим от приложението, но е обща употреба а = 2.
Много динамични масиви също заделят част от основната памет, ако техния размер падне под определен праг (например, 30% от капацитета).
Динамичните масиви са често срещан пример, когато преподава амортизиран анализ.Goodrich, Michael T.; Tamassia, Roberto (2002), „1.5.2 Analyzing an Extendable Array Implementation“, Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39 – 41.Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) . „17.4 Dynamic tables“. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416 – 424
Растежен фактор Растежният фактор на динамичния масив зависи от няколко фактора, пространство-време и алгоритми, използвани в самия алокатор. За растежния фактор „а“, средното време за вмъкване на операцията е а(а-1), докато броят пропилените клетки е ограничен до (а-1)n. Ако разпределителят на паметта използва първия подходящ алгоритъм за разпределение, а след това стойността на растежния фактор (както а = 2), може да предизвика динамично разширяване на масива до изчерпване на паметта, въпреки че значително количество на памет все още може да бъде на разположение."C++ STL vector: definition, growth factor, member functions ". Посетен на 5 август 2015. Има различни спорове за идеалните стойности на растежния фактор, включително предложения за Златното сечение, както и стойността на 1.5."vector growth factor of 1.5". comp.lang.c++.moderated. Google Groups. Много от учебниците, обаче, използват а=2 за опростяване и за аналитични цели.Goodrich, Michael T.; Tamassia, Roberto (2002), „1.5.2 Analyzing an Extendable Array Implementation“, Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39 – 41.Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) . „17.4 Dynamic tables“. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416 – 424
Приложение Растежен фактор (а) Java ArrayListSee, for example, the source code of java.util.ArrayList class from OpenJDK 6 1,5 (3/2) Python PyListObjectList object implementation from python.org, Посетен на 27 септември 2011. 1,125 (9/8) Microsoft Visual C++ 2013Brais, Hadi. "Dissecting the C++ STL Vector: Part 3 – Capacity & Size". Micromysteries. Посетен на 5 август 2015. 1,5 (3/2) G++ 5.2.0 2 Clang 3.6 2 Facebook folly/FBVector "facebook/folly". GitHub. Посетен на 5 август 2015. 1,5 (3/2)
Производителност Динамичният масив има производителност, близка до тази на обикновения масив, но с допълнение на нови операции като добавяне и премахване на елементи: Взимане или променяне на стойност от даден индекс (константно време) Обхождане на елементите подред (линейно време с добра производителност на кеша) Добавяне или изтриване на елемент от средата на масива (линейно време) Добавяне или изтриване на елемент от края на масива (амортизирано константно време) +Сравнение на структури от данниСвързан списъкМасивДинамичен масивБалансирано дървоСписък с произволен достъпИндексацияΘ(n)Θ(1)Θ(1)Θ(log n)Θ(log n)Вмъкване/изтриване от началотоΘ(1)N/AΘ(n)Θ(log n)Θ(1)Вмъкване/изтриване от краяΘ(n) когато последният елемент е неизвестен Θ(1) когато последният елемент е известенN/AΘ(1)Θ(log n)Θ(log n)Вмъкване/изтриване от средатаΘ(1)N/AΘ(n)Θ(n)Θ(log n)
Те се възползват от многото предимства на обикновените масиви, включвайки добра референтна локалност и добър процесорен кеш, компактност (употреба на малко памет) и произволен достъп. Случва се понякога да имат някакво малко фиксирано допълнително натоварване при съхранението на информация за размера и капацитета си. Въпреки това динамичните масиви са много удобни инструменти за създаване на структури от данни, които минимално товарят кеша. В езици като Python или Java обаче, които налагат референтна семантика, динамичният масив не съхранява данните в себе си, а в него се съдържат референциите на данните, намиращи се в други части на паметта. В този случай, в последователното достъпване на елементи в масива се включва и претърсване на множество далечни части в паметта.
В сравнение със свързания списък, динамичните масиви имат по-бърз достъп до индексите и по-бързо обхождане поради подобрената референтна локалност, обаче изискват линейно време да добавят или премахват данните от произволните места в паметта, тъй като всеки следващ елемент трябва да се премести докато свързаният списък това може да го направи в константно време. Този недостатък е смекчен благодарение на празния буфер и вариациите на стъпаловидните вектори. Също така във високо фрагментирана област на паметта, намирането на съседно свободно пространство за голям динамичен масив, може да отнеме повече време или дори да е невъзможно. Докато свързаните списъци не изискват цялата структура от данни да бъде съхранявана последователно.
Балансираното дърво може да съхранява списък докато предоставя всичките операции, които имат динамичните масиви и свързаните списъци. Умее да ги изпълнява сравнително бързо и ефективно, но производителността при добавянето на елементи в края и обхождането на листа е по-малка от тази на динамичния масив. Това се дължи на непоследователното съхранение и натоварването при манипулацията на данни в дървото.
Варианти Празните буфери са подобни на динамичните масиви, но позволяват ефикасно вмъкване и заличаване на операции близко до същите случайни локации. Някои deque изпълнения използват deque масиви, които позволяват постоянно амортизирано времево вмъкване/премахване и на двата края, вместо само на единия.
ГуудричGoodrich, Michael T.; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences", Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 1663: 205 – 216 представя алгоритъм на динамичен масив, наречен стъпаловидни вектори, който предоставя O(n1/2) изпълнения за редови запазващите вмъквания или премахвания от средата на масива.
Hashed Array Tree(HAT) е алгоритъм на динамичен масив публикуван от Ситарски през 1999.Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal 21 Hashed Array Tree губи редовия n1/2 размер от съхранителното пространство, където n е числото на елемента в масива. Когато се добавят серии от обекти към края на Hashed Array Tree, алгоритъмът има O(1) амортизирани изпълнения.
През 1999 вестникът,Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo Brodnik et al. описва стъпаловидна дата структури на динамичен масив, които губят само n1/2 пространство за n елементи при всяка точка от времето и доказват, че всеки масив трябва да изгуби толкова пространство ако иска да запази операциите постоянно амортизирано времеви. В допълнение, те представят вариант където разрастването и смаляването на буфера не само амортизира ами и е в най-лошия случай постоянно времеви.
Багуел (2002) Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays представя VList алгоритъма, който може да бъде адаптиран да изпълнява динамичен масив.
Езикова поддръжка std::vector на C++ е изпълнение на динамични масиви, както и класа ArrayListJavadoc on ArrayList снабден с Java API и .NET Framework.ArrayList Class Общият клас List<> снабден с .NET Framework версия 2.0 също е осъществен с динамични масиви. OrderCollection на Smalltalk е динамичен масив с динамичен стартов и краен индекс, правейки премахването на първия елемент също O(1). Осъществяването на дата типа list на Python е динамичен масив. Delphi и D изпълняват динамичния масив на основен език. Общият пакет Ada.Containers.Vectors на Ada дава осъществяването на динамичен масив за даден подтип. Много скриптинг езици като Perl и Ruby предлагат динамични масиви като вградени примитивни типове данни. Няколко многоплатформени структури предоставят изпълнението на динамичен масив за C, включвайки CFArray и CFMutableArray в Core Foundation, и GArray и GPtrArray в GLib.
Източници
Категория:Структури от данни