En informática , una matriz dinámica , matriz ampliable , matriz redimensionable , tabla dinámica , matriz mutable o lista de matrices es una estructura de datos de lista de tamaño variable y acceso aleatorio que permite agregar o quitar elementos. Se suministra con bibliotecas estándar en muchos lenguajes de programación modernos . Las matrices dinámicas superan un límite de matrices estáticas , que tienen una capacidad fija que debe especificarse en 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 es fijo cuando se asigna la matriz, aunque una matriz dinámica puede usar una matriz de tamaño fijo como back-end. [1]
Una matriz dinámica simple puede construirse asignando una matriz de tamaño fijo, normalmente mayor que el número de elementos requeridos inmediatamente. Los elementos de la matriz dinámica se almacenan de forma contigua al comienzo de la matriz subyacente, y las posiciones restantes hacia el final de la matriz subyacente se reservan o no se utilizan. 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 debe agregar un elemento adicional, entonces se debe aumentar el tamaño de la matriz de tamaño fijo subyacente. Normalmente, el cambio de 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 se requiere ningún cambio de 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 denomina capacidad de la matriz dinámica o tamaño físico , que es el tamaño máximo posible sin reubicar los datos. [2]
Una matriz de tamaño fijo será suficiente en aplicaciones en las que el tamaño lógico máximo sea fijo (por ejemplo, por especificación) o se pueda calcular antes de asignar la matriz. Una matriz dinámica podría ser preferible si:
Para evitar incurrir en el costo de cambiar el tamaño muchas veces, las matrices dinámicas cambian de tamaño en una gran cantidad, por ejemplo, duplicando su tamaño, y utilizan el espacio reservado para futuras ampliaciones. La operación de agregar un elemento al final podría funcionar de la siguiente manera:
función insertEnd ( dynarray a , elemento e ) si ( a . tamaño == a . capacidad ) // redimensiona a al doble de su capacidad actual: a . capacidad ← a . capacidad * 2 // (copia el contenido a la nueva ubicación de memoria aquí) a [ a . tamaño ] ← e a . tamaño ← a . tamaño + 1 A medida que se insertan n elementos, las capacidades forman una progresión geométrica . Expandir la matriz en cualquier proporción constante a garantiza que la inserción de n elementos tome O ( n ) tiempo en 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 el crecimiento y la contracción repetidos) 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 el análisis amortizado . [3] [4]
El factor de crecimiento de la matriz dinámica depende de varios factores, entre ellos un equilibrio espacio-tiempo y algoritmos utilizados en el propio asignador de memoria. Para el factor de crecimiento a , el tiempo medio por operación de inserción es de aproximadamente a /( a −1), mientras que el número de celdas desperdiciadas está limitado por encima por ( a −1) n [ cita requerida ] . Si el asignador de memoria utiliza un algoritmo de asignación de primer ajuste , los valores del factor de crecimiento como a = 2 pueden hacer que la expansión de la matriz dinámica se quede sin memoria aunque todavía pueda haber una cantidad significativa de memoria disponible. [5] Ha habido varias discusiones sobre los valores ideales del factor de crecimiento, incluidas las propuestas para la proporción áurea , así como el valor 1,5. [6] Sin embargo, muchos libros de texto utilizan a = 2 para simplificar y con fines de análisis. [3] [4]
A continuación se presentan 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:
Las matrices dinámicas se benefician de muchas de las ventajas de las matrices, 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, solo tienen una pequeña sobrecarga adicional fija para almacenar información sobre el tamaño y la capacidad. Esto hace que las matrices dinámicas sean una herramienta atractiva para crear estructuras de datos compatibles con la memoria 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 a los elementos de la matriz de forma secuencial en realidad implicará acceder a múltiples áreas no contiguas de la memoria, por lo que se pierden las muchas ventajas de la compatibilidad con la memoria caché de esta estructura de datos.
En comparación con las listas enlazadas , las matrices dinámicas tienen una indexación más rápida (tiempo constante frente a 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 enlazadas pueden hacer esto en tiempo constante. Esta desventaja se mitiga con el búfer de espacio y las variantes de vector escalonado que se analizan en Variantes a continuación. Además, en una región de memoria altamente fragmentada , puede ser 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 de matrices dinámicas y 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 al almacenamiento no contiguo y a la sobrecarga de manipulación/recorrido del árbol.
Los buffers de espacio son similares a las matrices dinámicas, pero permiten operaciones de inserción y eliminación eficientes agrupadas cerca de la misma ubicación arbitraria. Algunas implementaciones de deque utilizan deques de matriz , que permiten la inserción/eliminación de tiempo constante amortizado en ambos extremos, en lugar de solo en uno.
Goodrich [18] presentó un algoritmo de matriz dinámica llamado vectores escalonados que proporciona un rendimiento O ( n 1/ k ) para inserciones y eliminaciones desde cualquier parte de la matriz, y obtención y configuración O ( k ), 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 una cantidad de espacio de almacenamiento de orden n 1/2 , donde n es el número de elementos en la matriz. El algoritmo tiene un rendimiento amortizado de 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 punto del tiempo, y prueban un límite inferior que muestra que cualquier matriz dinámica debe desperdiciar esta cantidad de espacio para que las operaciones permanezcan amortizadas en tiempo constante. Además, presentan una variante en la que el aumento y la disminución del búfer no solo ha amortizado, sino que también ha mantenido el tiempo constante en el peor de los casos.
Bagwell (2002) [21] presentó el algoritmo VList, que puede adaptarse para implementar una matriz dinámica.
Las matrices redimensionables ingenuas, también llamadas "la peor implementación" de matrices redimensionables, mantienen el tamaño asignado de la matriz exactamente lo suficientemente grande para todos los datos que contiene, quizás llamando a realloc para todos y cada uno de los elementos agregados a la matriz. Las matrices redimensionables ingenuas son la forma más simple de implementar una matriz redimensionable en C. No desperdician memoria, pero agregar al final de la matriz siempre toma Θ( n ) tiempo. [19] [22] [23] [24] [25] Las matrices de crecimiento lineal preasignan ("desperdician") Θ(1) espacio cada vez que redimensionan la matriz, lo que las hace mucho más rápidas que las matrices redimensionables ingenuas: agregar al final de la matriz aún toma Θ( n ) tiempo pero con una constante mucho más pequeña. Las matrices redimensionables ingenuas y las matrices de crecimiento lineal pueden ser útiles cuando una aplicación con restricciones de espacio necesita muchas matrices redimensionables pequeñas; También se utilizan comúnmente como un ejemplo educativo que conduce a matrices dinámicas de crecimiento exponencial. [26]
Las clases de C++std::vector y Ruststd::vec::Vec son implementaciones de matrices dinámicas, al igual que las ArrayList[27] clases suministradas 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. La de SmalltalkOrderedCollection es una matriz dinámica con índice inicial 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 incorporado .
Varios marcos multiplataforma proporcionan implementaciones de matrices dinámicas para C , incluidos CFArrayy CFMutableArrayen Core Foundation , y GArrayy GPtrArrayen GLib .
Common Lisparray proporciona un soporte rudimentario para vectores redimensionables al permitir configurar el tipo incorporado como ajustable y la ubicación de inserción mediante el puntero de relleno .
ArrayList