Топ-100
Back

ⓘ Динамичен масив. В компютърните науки динамичният масив е масив с променлив размер, в който могат да се добавят или премахват елементи. Той се поддържа от станд ..




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

ⓘ Динамичен масив

В компютърните науки динамичният масив е масив с променлив размер, в който могат да се добавят или премахват елементи. Той се поддържа от стандартните библиотеки в много от модерните програмни езици.

Динамичният масив не бива да се бърка с динамично разпределения масив, чийто размер е предварително определен още при неговата декларация, макар че динамичният масив може да използва точно такъв масив с предварително известен брой елементи за своя подложка.

                                     

1. Динамични масиви с ограничен размер и капацитет

Най-елементарният динамичен масив може да се създаде, чрез заделянето на масив с фиксиран размер и разделянето му на две части: първата част съхранява елементите на динамичния масив, а втората част се резервира или въобще не се използва. Така ние можем да добавяме или премахваме елементи в края на динамичния масив, използвайки резервираната памет, докато тя не се изчерпа. Броя на елементите използвани от съдържанието на един динамичен масив са неговия логически размер или просто размер, докато размерът на свободната част от масива се нарича капацитет или физически размер на динамичния масив, който е възможно най-големия размер без да се налага презаделяне на памет.

При апликациите, където логическия размер е ограничен, структурите от данни с фиксиран размер са напълно достатъчни. Въпреки че това не е много добра практика ако по-късно се наложи използването на допълнителна памет, която в конкретния случай няма как да се набави. Един програмист би предпочел да пише код и да прави всеки масив способен да се преоразмерява, след което отново да се връща към масив с фиксиран размер по време на програмната оптимизация. Преоразмеряването може обаче да се окаже доста скъпо струващо удоволствие, което често се изразява с копирането на цялото съдържание на масива.

                                     

2. Геометрична експанзия и амортизирана стойност

Преоразмеряването изисква много висок разход, тъй като включва изграждането на още един масив с увеличен размер следван от копие на елементите от "стария" в "новия" масив. За да се избегне тази процедура всеки път когато се добавя нов елемент, динамичните масиви се уголемяват като удвояват обема си вместо с една единица. По този начин се резервира място за бъдещи елементи. Добавянето на елемент в края може да работи по следния начин:

function insertEnddynarray 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 ← e a.size ← a.size + 1

Като се добавят N елементи, капацитетът образуват геометрична прогресия. Разширяване на масива от всеки постоянен процент гарантира, че поставянето на N елементи отнема O N време като цяло, което означава, че всяка манипулация отнема амортизирано константно време. Стойността на този дял води до компромис пространство-време: средното време за една операция на вмъкване е приблизително а/а-1, докато броя на загубените клетки е допълнително ограничен до а-1n. Изборът на "a" е независим от приложението, но е обща употреба а = 2.

Много динамични масиви също заделят част от основната памет, ако техния размер падне под определен праг например, 30% от капацитета.

Динамичните масиви са често срещан пример, когато преподава амортизиран анализ.

                                     

3. Растежен фактор

Растежният фактор на динамичния масив зависи от няколко фактора, пространство-време и алгоритми, използвани в самия алокатор. За растежния фактор "а", средното време за вмъкване на операцията е аа-1, докато броят пропилените клетки е ограничен до а-1n. Ако разпределителят на паметта използва първия подходящ алгоритъм за разпределение, а след това стойността на растежния фактор както а = 2, може да предизвика динамично разширяване на масива до изчерпване на паметта, въпреки че значително количество на памет все още може да бъде на разположение. Има различни спорове за идеалните стойности на растежния фактор, включително предложения за Златното сечение, както и стойността на 1.5. Много от учебниците, обаче, използват а=2 за опростяване и за аналитични цели.

                                     

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

Динамичният масив има производителност, близка до тази на обикновения масив, но с допълнение на нови операции като добавяне и премахване на елементи:

  • Обхождане на елементите подред линейно време с добра производителност на кеша
  • Взимане или променяне на стойност от даден индекс константно време
  • Добавяне или изтриване на елемент от края на масива амортизирано константно време
  • Добавяне или изтриване на елемент от средата на масива линейно време

Те се възползват от многото предимства на обикновените масиви, включвайки добра референтна локалност и добър процесорен кеш, компактност употреба на малко памет и произволен достъп. Случва се понякога да имат някакво малко фиксирано допълнително натоварване при съхранението на информация за размера и капацитета си. Въпреки това динамичните масиви са много удобни инструменти за създаване на структури от данни, които минимално товарят кеша. В езици като Python или Java обаче, които налагат референтна семантика, динамичният масив не съхранява данните в себе си, а в него се съдържат референциите на данните, намиращи се в други части на паметта. В този случай, в последователното достъпване на елементи в масива се включва и претърсване на множество далечни части в паметта.

В сравнение със свързания списък, динамичните масиви имат по-бърз достъп до индексите и по-бързо обхождане поради подобрената референтна локалност, обаче изискват линейно време да добавят или премахват данните от произволните места в паметта, тъй като всеки следващ елемент трябва да се премести докато свързаният списък това може да го направи в константно време. Този недостатък е смекчен благодарение на празния буфер и вариациите на стъпаловидните вектори. Също така във високо фрагментирана област на паметта, намирането на съседно свободно пространство за голям динамичен масив, може да отнеме повече време или дори да е невъзможно. Докато свързаните списъци не изискват цялата структура от данни да бъде съхранявана последователно.

Балансираното дърво може да съхранява списък докато предоставя всичките операции, които имат динамичните масиви и свързаните списъци. Умее да ги изпълнява сравнително бързо и ефективно, но производителността при добавянето на елементи в края и обхождането на листа е по-малка от тази на динамичния масив. Това се дължи на непоследователното съхранение и натоварването при манипулацията на данни в дървото.



                                     

5. Варианти

Празните буфери са подобни на динамичните масиви, но позволяват ефикасно вмъкване и заличаване на операции близко до същите случайни локации. Някои deque изпълнения използват deque масиви, които позволяват постоянно амортизирано времево вмъкване/премахване и на двата края, вместо само на единия.

Гуудрич представя алгоритъм на динамичен масив, наречен стъпаловидни вектори, който предоставя On1/2 изпълнения за редови запазващите вмъквания или премахвания от средата на масива.

Hashed Array TreeHAT е алгоритъм на динамичен масив публикуван от Ситарски през 1999. Hashed Array Tree губи редовия n1/2 размер от съхранителното пространство, където n е числото на елемента в масива. Когато се добавят серии от обекти към края на Hashed Array Tree, алгоритъмът има O1 амортизирани изпълнения.

През 1999 вестникът, Brodnik et al. описва стъпаловидна дата структури на динамичен масив, които губят само n1/2 пространство за n елементи при всяка точка от времето и доказват, че всеки масив трябва да изгуби толкова пространство ако иска да запази операциите постоянно амортизирано времеви. В допълнение, те представят вариант където разрастването и смаляването на буфера не само амортизира ами и е в най-лошия случай постоянно времеви.

Багуел 2002 представя VList алгоритъма, който може да бъде адаптиран да изпълнява динамичен масив.

                                     

6. Езикова поддръжка

std vector на C++ е изпълнение на динамични масиви, както и класа ArrayList снабден с Java API и.NET Framework. Общият клас List снабден с.NET Framework версия 2.0 също е осъществен с динамични масиви. OrderCollection на Smalltalk е динамичен масив с динамичен стартов и краен индекс, правейки премахването на първия елемент също O1. Осъществяването на дата типа list на Python е динамичен масив. Delphi и D изпълняват динамичния масив на основен език. Общият пакет Ada.Containers.Vectors на Ada дава осъществяването на динамичен масив за даден подтип. Много скриптинг езици като Perl и Ruby предлагат динамични масиви като вградени примитивни типове данни. Няколко многоплатформени структури предоставят изпълнението на динамичен масив за C, включвайки CFArray и CFMutableArray в Core Foundation, и GArray и GPtrArray в GLib.

                                     
  • значения на Масив Масивът в компютърните науки е наредена последователност от елементи от един и същ базов тип. Отделен елемент на масива се указва посредством
  • рети. През ранното средновековие динамичните събития на север изтикват тук нови бегълци, този път германоезични. Масивът ограничава тяхното проникване към
  • В програмирането назъбен масив на английски: Jagged Array познат още като нащърбен масив е масив от масиви чиито елементи могат да бъдат с различна
  • тестване, точни модели, вградено автоматично управление на паметта, динамични масиви анонимни функции. Голяма част от характеристиките на езиците, които
  • масив от масиви Тъй като JavaScript е динамичен език, елементите от масива могат да са от различен тип. Един масив може да съдържа други масиви обекти
  • сортирането чрез броене, bucket сортирането изисква свързани списъци, динамични масиви или голямо количество заделена памет, където да съхранява групите от
  • елементи и в масива няма да могат да бъдат добавяни нови елементи. Това налага копиране на опашката в нов масив с по - голям размер. При динамичната реализация
  • и обработване на грешки, управление на динамичната памет, множество типове данни, съвкупности от данни масиви структури, обединения и комбинации от
  • Динамична памет DRAM на английски: dynamic random access memory динамична памет с произволен достъп е вид енергозависимо запомнящо устройство с
  • наследяват ValueType: класовете class интерфей сите interface масивите и делегатите delegate void Можем да декларираме референтна променлива

Users also searched:

...