Уикипедия

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

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

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

Няколко стойности се добавят в края на динамичен масив с геометрична експанзия. Сивите клетки показват запазено място за експанзия. Повечето вмъквания са бързи (константно време), а някои са бавни, поради необходимостта от преразпределение (Θ (п) път, белязан с костенурки). Логическият размер и качеството на крайния масив са показани.

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

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

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

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

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

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% от капацитета).

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

Растежен фактор редактиране

Растежният фактор на динамичния масив зависи от няколко фактора, пространство-време и алгоритми, използвани в самия алокатор. За растежния фактор „а“, средното време за вмъкване на операцията е а(а-1), докато броят пропилените клетки е ограничен до (а-1)n. Ако разпределителят на паметта използва първия подходящ алгоритъм за разпределение, а след това стойността на растежния фактор (както а = 2), може да предизвика динамично разширяване на масива до изчерпване на паметта, въпреки че значително количество на памет все още може да бъде на разположение.[5] Има различни спорове за идеалните стойности на растежния фактор, включително предложения за Златното сечение, както и стойността на 1.5.[6] Много от учебниците, обаче, използват а=2 за опростяване и за аналитични цели.[7][8]

Приложение Растежен фактор (а)
Java ArrayList[1] 1,5 (3/2)
Python PyListObject[9] 1,125 (9/8)
Microsoft Visual C++ 2013[10] 1,5 (3/2)
G++ 5.2.0 [5] 2
Clang 3.6 [5] 2
Facebook folly/FBVector [11] 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 масиви, които позволяват постоянно амортизирано времево вмъкване/премахване и на двата края, вместо само на единия.

Гуудрич[12] представя алгоритъм на динамичен масив, наречен стъпаловидни вектори, който предоставя O(n1/2) изпълнения за редови запазващите вмъквания или премахвания от средата на масива.

Hashed Array Tree(HAT) е алгоритъм на динамичен масив публикуван от Ситарски през 1999.[13] Hashed Array Tree губи редовия n1/2 размер от съхранителното пространство, където n е числото на елемента в масива. Когато се добавят серии от обекти към края на Hashed Array Tree, алгоритъмът има O(1) амортизирани изпълнения.

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

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

Езикова поддръжка редактиране

std::vector на C++ е изпълнение на динамични масиви, както и класа ArrayList[16] снабден с Java API и .NET Framework.[17] Общият клас 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.

Източници редактиране

  1. ↑ а б See, for example, the source code of java.util.ArrayList class from OpenJDK 6
  2. ↑ Lambert, Kenneth Alfred (2009), "Physical size and logical size", Fundamentals of Python: From First Programs Through Data Structures (Cengage Learning), p. 510
  3. ↑ 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.
  4. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „17.4 Dynamic tables“. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416 – 424
  5. ↑ а б в "C++ STL vector: definition, growth factor, member functions Архив на оригинала от 2015-08-06 в Wayback Machine.". Посетен на 5 август 2015.
  6. ↑ "vector growth factor of 1.5". comp.lang.c++.moderated. Google Groups.
  7. ↑ 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.
  8. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „17.4 Dynamic tables“. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416 – 424
  9. ↑ List object implementation from python.org, Посетен на 27 септември 2011.
  10. ↑ Brais, Hadi. "Dissecting the C++ STL Vector: Part 3 – Capacity & Size". Micromysteries. Посетен на 5 август 2015.
  11. ↑ "facebook/folly". GitHub. Посетен на 5 август 2015.
  12. ↑ 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
  13. ↑ Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal 21
  14. ↑ 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
  15. ↑ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays
  16. ↑ Javadoc on ArrayList
  17. ↑ ArrayList Class
    Тази страница частично или изцяло представлява превод на страницата Dynamic array в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​

Взето от „https://bg.wikipedia.org/w/index.php?title=Динамичен_масив&oldid=10947724“.