En informática , una matriz dinámica , una matriz ampliable , una matriz redimensionable , una tabla dinámica , una matriz mutable o una lista de matrices es una estructura de datos de lista de tamaño variable y acceso aleatorio que permite agregar o eliminar elementos. Se suministra con bibliotecas estándar en muchos lenguajes de programación convencionales modernos . Los arreglos dinámicos superan el límite de los arreglos estáticos , que tienen una capacidad fija que debe especificarse en el momento de la asignación .
Una matriz dinámica no es lo mismo que una matriz asignada dinámicamente o una matriz de longitud variable , cualquiera de las cuales es una matriz cuyo tamaño se fija cuando se asigna la matriz, aunque una matriz dinámica puede usar una matriz de tamaño fijo como respaldo. fin. [1]
Se puede construir una matriz dinámica simple asignando una matriz de tamaño fijo, generalmente mayor que la cantidad de elementos inmediatamente requeridos. Los elementos de la matriz dinámica se almacenan de forma contigua al inicio de la matriz subyacente, y las posiciones restantes hacia el final de la matriz subyacente están reservadas o no utilizadas. Se pueden agregar elementos al final de una matriz dinámica en tiempo constante utilizando el espacio reservado, hasta que este espacio se consuma por completo. Cuando se consume todo el espacio y se va a agregar un elemento adicional, es necesario aumentar el tamaño de la matriz de tamaño fijo subyacente. Normalmente, cambiar el tamaño es costoso porque implica asignar una nueva matriz subyacente y copiar cada elemento de la matriz original. Los elementos se pueden eliminar del final de una matriz dinámica en tiempo constante, ya que no es necesario cambiar el tamaño. La cantidad de elementos utilizados por el contenido de la matriz dinámica es su tamaño lógico o tamaño , mientras que el tamaño de la matriz subyacente se llama capacidad de la matriz dinámica o tamaño físico , que es el tamaño máximo posible sin reubicar datos. [2]
Una matriz de tamaño fijo será suficiente en aplicaciones donde el tamaño lógico máximo es fijo (por ejemplo, por especificación), o se puede calcular antes de asignar la matriz. Podría preferirse una matriz dinámica si:
Para evitar incurrir en el costo de cambiar el tamaño muchas veces, las matrices dinámicas cambian de tamaño en gran medida, como duplicar su tamaño, y utilizan el espacio reservado para futuras expansiones. La operación de agregar un elemento al final podría funcionar de la siguiente manera:
función insertEnd ( dynarray a , elemento e ) if ( a . tamaño == a . capacidad ) // cambia el tamaño de a al doble de su capacidad actual: a . capacidad ← a . capacidad * 2 // (copie el contenido a la nueva ubicación de memoria aquí) a [ a . tamaño ] ← e a . tamaño ← a . tamaño + 1 Al insertar n elementos, las capacidades forman una progresión geométrica . Expandir la matriz en cualquier proporción constante a garantiza que insertar n elementos tome O ( n ) tiempo total, lo que significa que cada inserción toma un tiempo constante amortizado . Muchas matrices dinámicas también desasignan parte del almacenamiento subyacente si su tamaño cae por debajo de un cierto umbral, como el 30 % de la capacidad. Este umbral debe ser estrictamente menor que 1/ a para proporcionar histéresis (proporcionar una banda estable para evitar crecer y contraerse repetidamente) y admitir secuencias mixtas de inserciones y eliminaciones con un costo constante amortizado.
Las matrices dinámicas son un ejemplo común cuando se enseña análisis amortizado . [3] [4]
El factor de crecimiento de la matriz dinámica depende de varios factores, incluido un equilibrio espacio-temporal y algoritmos utilizados en el propio asignador de memoria. Para el factor de crecimiento a , el tiempo promedio por operación de inserción es aproximadamente a /( a −1), mientras que el número de células desperdiciadas está limitado arriba por ( a −1) n [ cita necesaria ] . Si el asignador de memoria utiliza un algoritmo de asignación de primer ajuste , entonces los valores del factor de crecimiento como = 2 pueden provocar que la expansión dinámica de la matriz se quede sin memoria aunque todavía haya una cantidad significativa de memoria disponible. [5] Ha habido varias discusiones sobre los valores ideales de los factores de crecimiento, incluidas propuestas para la proporción áurea y el valor 1,5. [6] Muchos libros de texto, sin embargo, utilizan a = 2 por motivos de simplicidad y análisis. [3] [4]
A continuación se muestran los factores de crecimiento utilizados por varias implementaciones populares:
La matriz dinámica tiene un rendimiento similar a una matriz, con la adición de nuevas operaciones para agregar y eliminar elementos:
Los arreglos dinámicos se benefician de muchas de las ventajas de los arreglos, incluida una buena localidad de referencia y utilización de la caché de datos , compacidad (bajo uso de memoria) y acceso aleatorio . Por lo general, sólo tienen una pequeña sobrecarga adicional fija para almacenar información sobre el tamaño y la capacidad. Esto hace que los arreglos dinámicos sean una herramienta atractiva para construir estructuras de datos amigables con la caché . Sin embargo, en lenguajes como Python o Java que imponen semántica de referencia, la matriz dinámica generalmente no almacenará los datos reales, sino que almacenará referencias a los datos que residen en otras áreas de la memoria. En este caso, acceder secuencialmente a los elementos de la matriz en realidad implicará acceder a múltiples áreas de memoria no contiguas, por lo que se pierden las muchas ventajas de la compatibilidad con caché de esta estructura de datos.
En comparación con las listas vinculadas , las matrices dinámicas tienen una indexación más rápida (tiempo constante versus tiempo lineal) y, por lo general, una iteración más rápida debido a una localidad de referencia mejorada; sin embargo, las matrices dinámicas requieren un tiempo lineal para insertar o eliminar en una ubicación arbitraria, ya que todos los elementos siguientes deben moverse, mientras que las listas vinculadas pueden hacerlo en un tiempo constante. Esta desventaja se ve mitigada por el buffer de brecha y las variantes de vectores escalonados que se analizan en Variantes a continuación. Además, en una región de memoria altamente fragmentada , puede resultar costoso o imposible encontrar espacio contiguo para una matriz dinámica grande, mientras que las listas enlazadas no requieren que toda la estructura de datos se almacene de forma contigua.
Un árbol equilibrado puede almacenar una lista y al mismo tiempo proporcionar todas las operaciones tanto de matrices dinámicas como de listas enlazadas de manera razonablemente eficiente, pero tanto la inserción al final como la iteración sobre la lista son más lentas que para una matriz dinámica, en teoría y en la práctica, debido a la falta de almacenamiento contiguo y recorrido/manipulación de árboles por encima.
Los buffers de espacio son similares a las matrices dinámicas, pero permiten operaciones eficientes de inserción y eliminación agrupadas cerca de la misma ubicación arbitraria. Algunas implementaciones de deque utilizan matrices deques , que permiten la inserción/eliminación de tiempo constante amortizado en ambos extremos, en lugar de solo un extremo.
Goodrich [18] presentó un algoritmo de matriz dinámica llamado vectores escalonados que proporciona rendimiento O ( n 1/ k ) para inserciones y eliminaciones desde cualquier lugar de la matriz, y O ( k ) get y set, donde k ≥ 2 es un parámetro constante.
El árbol de matriz hash (HAT) es un algoritmo de matriz dinámica publicado por Sitarski en 1996. [19] El árbol de matriz hash desperdicia orden n 1/2 cantidad de espacio de almacenamiento, donde n es el número de elementos en la matriz. El algoritmo tiene un rendimiento amortizado O (1) al agregar una serie de objetos al final de un árbol de matriz hash.
En un artículo de 1999, [20] Brodnik et al. describen una estructura de datos de matriz dinámica en niveles, que desperdicia solo n 1/2 espacio para n elementos en cualquier momento, y demuestran un límite inferior que muestra que cualquier matriz dinámica debe desperdiciar esta cantidad de espacio si las operaciones deben permanecer amortizadas en tiempo constante. . Además, presentan una variante en la que aumentar y reducir el buffer no sólo amortiza el tiempo, sino que, en el peor de los casos, es constante.
Bagwell (2002) [21] presentó el algoritmo VList, que puede adaptarse para implementar una matriz dinámica.
Las matrices ingenuas de tamaño variable, también llamadas "la peor implementación" de matrices de tamaño variable, mantienen el tamaño asignado de la matriz exactamente lo suficientemente grande para todos los datos que contiene, tal vez llamando a realloc para todos y cada uno de los elementos agregados a la matriz. Las matrices ingenuas de tamaño variable son la forma más sencilla de implementar una matriz de tamaño variable en C. No desperdician memoria, pero agregarlas al final de la matriz siempre toma Θ( n ) tiempo. [19] [22] [23] [24] [25] Las matrices de crecimiento lineal preasignan ("desperdician") espacio Θ(1) cada vez que cambian el tamaño de la matriz, lo que las hace muchas veces más rápidas que las matrices ingenuas de tamaño variable. - agregar al final de la matriz todavía toma Θ ( n ) tiempo pero con una constante mucho más pequeña. Los arreglos ingenuos de tamaño variable y los arreglos de crecimiento lineal pueden ser útiles cuando una aplicación con espacio limitado necesita muchos arreglos pequeños de tamaño variable; También se utilizan comúnmente como ejemplo educativo que conduce a matrices dinámicas de crecimiento exponencial. [26]
C++ y std::vectorRust son implementaciones std::vec::Vecde matrices dinámicas, al igual que las clases ArrayList[27] proporcionadas con la API de Java [28] : 236 y .NET Framework . [29] [30] : 22
La clase genérica List<>suministrada con la versión 2.0 de .NET Framework también se implementa con matrices dinámicas. Smalltalk es OrderedCollectionuna matriz dinámica con inicio y final dinámicos, lo que hace que la eliminación del primer elemento también sea O(1).
La implementación del tipo de datos de Pythonlist es una matriz dinámica cuyo patrón de crecimiento es: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... [31]
Delphi y D implementan matrices dinámicas en el núcleo del lenguaje.
El paquete genérico Ada.Containers.Vectors de Ada proporciona una implementación de matriz dinámica para un subtipo determinado.
Muchos lenguajes de programación, como Perl y Ruby, ofrecen matrices dinámicas como un tipo de datos primitivo integrado .
Varios marcos multiplataforma proporcionan implementaciones de matrices dinámicas para C , incluidos CFArrayCore Foundation y GLib .CFMutableArrayGArrayGPtrArray
Common Lisp proporciona un soporte rudimentario para vectores redimensionables al permitir configurar el tipo incorporado arraycomo ajustable y la ubicación de inserción mediante el puntero de relleno .
ArrayList