Matriu dinàmica

S'insereixen diversos valors al final d'una matriu dinàmica mitjançant l'expansió geomètrica. Les cel·les grises indiquen espai reservat per a l'expansió. La majoria de les insercions són ràpides (temps constant), mentre que algunes són lentes a causa de la necessitat de reassignació (temps Θ(n), etiquetat amb tortugues). Es mostra la mida lògica i la capacitat de la matriu final.

En informàtica, una matriu dinàmica, una matriu creixent, una matriu redimensionable, una taula dinàmica, una matriu mutable o una llista de matrius és una estructura de dades de llista d'accés aleatori i de mida variable que permet afegir o eliminar elements. Es subministra amb biblioteques estàndard en molts llenguatges de programació moderns. Les matrius dinàmiques superen un límit de matrius estàtiques, que tenen una capacitat fixa que cal especificar en l'assignació.

Una matriu dinàmica no és el mateix que una matriu assignada dinàmicament o una matriu de longitud variable, qualsevol dels quals és una matriu la mida de la qual es fixa quan s'assigna la matriu, tot i que una matriu dinàmica pot utilitzar una matriu de mida fixa com a posterior. final.

Matrius dinàmiques i capacitat de mida limitada

Es pot construir una matriu dinàmica senzilla assignant una matriu de mida fixa, normalment més gran que el nombre d'elements necessaris immediatament. Els elements de la matriu dinàmica s'emmagatzemen de manera contigu a l'inici de la matriu subjacent, i les posicions restants cap al final de la matriu subjacent es reserven o no s'utilitzen. Els elements es poden afegir al final d'una matriu dinàmica en temps constant utilitzant l'espai reservat, fins que aquest espai es consumeixi completament. Quan es consumeix tot l'espai i s'ha d'afegir un element addicional, cal augmentar la mida de la matriu de mida fixa subjacent. Normalment, canviar la mida és car perquè implica assignar una nova matriu subjacent i copiar cada element de la matriu original. Els elements es poden eliminar del final d'una matriu dinàmica en temps constant, ja que no cal canviar la mida. El nombre d'elements utilitzats pel contingut de la matriu dinàmica és la seva mida o mida lògica, mentre que la mida de la matriu subjacent s'anomena capacitat o mida física de la matriu dinàmica, que és la mida màxima possible sense reubicar les dades.

Una matriu de mida fixa serà suficient en aplicacions on la mida lògica màxima estigui fixada (per exemple, per especificació), o es pot calcular abans d'assignar la matriu. Pot ser preferible una matriu dinàmica si:

• la mida lògica màxima és desconeguda, o és difícil de calcular, abans d'assignar la matriu
• es considera que una mida lògica màxima donada per una especificació és probable que canviï
• el cost amortitzat de canviar la mida d'una matriu dinàmica no afecta significativament el rendiment o la capacitat de resposta

Expansió geomètrica i cost amortitzat

Per evitar incórrer en el cost de canviar la mida moltes vegades, les matrius dinàmiques canvien la mida en una gran quantitat, com ara duplicar-ne la mida, i utilitzen l'espai reservat per a una futura expansió. L'operació d'afegir un element al final pot funcionar de la següent manera:

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

A mesura que s'insereixen n elements, les capacitats formen una progressió geomètrica. L'ampliació de la matriu en qualsevol proporció constant a garanteix que la inserció de n elements triga O(n) temps global, el que significa que cada inserció triga un temps constant amortitzat. Moltes matrius dinàmiques també desassignen part de l'emmagatzematge subjacent si la seva mida cau per sota d'un determinat llindar, com ara el 30% de la capacitat. Aquest llindar ha de ser estrictament inferior a 1/a per tal de proporcionar histèresi (proporcionar una banda estable per evitar el creixement i la reducció repetida) i suportar seqüències mixtes d'insercions i extraccions amb un cost constant amortitzat.

Les matrius dinàmiques són un exemple comú quan s'ensenya l'anàlisi amortitzada.

LLenguatges de suport

std::vector de C++ i std::vec::Vec Rust són implementacions de matrius dinàmiques, igual que les classes ArrayList subministrades amb l'API de Java i el. NET Framework.

La classe genèrica List<> subministrada amb la versió 2.0 del.NET Framework també s'implementa amb matrius dinàmiques. OrderedCollection de Smalltalk és una matriu dinàmica amb un índex inicial i final dinàmics, fent que l'eliminació del primer element també sigui O(1).

La implementació del tipus de dades de list de Python és una matriu dinàmica el patró de creixement de la qual és: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76,...

Delphi i D implementen matrius dinàmiques al nucli del llenguatge.

Ada 's Ada. Containers. Vectors El paquet genèric proporciona una implementació de matriu dinàmica per a un subtipus determinat.

Molts llenguatges de programació com Perl i Ruby ofereixen matrius dinàmiques com a tipus de dades primitius integrats.

Diversos marcs multiplataforma ofereixen implementacions de matrius dinàmiques per a C, com CFArray i CFMutableArray a Core Foundation i GArray i GPtrArray a GLib.

Diversos marcs multiplataforma ofereixen implementacions de matrius dinàmiques per a C, com CFArray i CFMutableArray a Core Foundation i GArray i GPtrArray a GLib.