Matriz dinámica

En informática , un array dinámico , array expandible , array redimensionable , tabla dinámica , array mutable o lista de arrays es una estructura de datos de lista de tamaño variable y acceso aleatorio que permite añadir o eliminar elementos. Se incluye en las bibliotecas estándar de muchos lenguajes de programación modernos . Los arrays dinámicos superan una limitación de los arrays estáticos , que tienen una capacidad fija que debe especificarse en el momento de la asignación .

Un array dinámico no es lo mismo que un array asignado dinámicamente o un array de longitud variable , ya que ambos son arrays cuyo tamaño es fijo cuando se asignan, aunque un array dinámico puede usar un array de tamaño fijo como base. ^{[ 1 ]}

Se puede construir un arreglo dinámico simple asignando un arreglo de tamaño fijo, generalmente mayor que la cantidad de elementos necesarios. Los elementos del arreglo dinámico se almacenan de forma contigua al inicio del arreglo subyacente, y las posiciones restantes hacia el final de este se reservan. Se pueden agregar elementos al final de un arreglo dinámico en tiempo constante utilizando el espacio reservado hasta que este se agote por completo.

Cuando se agota el espacio disponible y se desea agregar un elemento adicional, es necesario aumentar el tamaño del array subyacente de tamaño fijo. Por lo general, redimensionar un array resulta costoso, ya que implica asignar un nuevo array subyacente y, posiblemente, copiar cada elemento del array original.

Los elementos se pueden eliminar del final de una matriz dinámica en tiempo constante, ya que no se requiere redimensionamiento. El número de elementos utilizados por el contenido de la matriz dinámica es su tamaño lógico o longitud , mientras que el tamaño de la matriz subyacente se denomina tamaño físico o capacidad de la matriz dinámica . La capacidad es el tamaño máximo posible sin reubicar datos. ^{[ 2 ]}

Un array de tamaño fijo será suficiente en aplicaciones donde el tamaño lógico máximo sea fijo (por ejemplo, por especificación) o se pueda calcular antes de asignar el array. Un array dinámico podría ser preferible si:

• El tamaño lógico máximo es desconocido o difícil de calcular antes de que se asigne el array.
• Se considera que es probable que cambie el tamaño lógico máximo especificado.
• El costo amortizado de redimensionar una matriz dinámica no afecta significativamente el rendimiento ni la capacidad de respuesta.

Para evitar incurrir en el costo de redimensionar muchas veces, los arreglos dinámicos se redimensionan en gran medida, por ejemplo, duplicando 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 ) 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 el arreglo en una proporción constante a garantiza que la inserción de n elementos tome un tiempo total de O ( n ) , lo que significa que cada inserción toma un tiempo constante amortizado (siempre que cualquier asignación dada tome un tiempo de O ( 1 )). Muchos arreglos dinámicos también liberan 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 crecimientos y reducciones repetidas) y admitir secuencias mixtas de inserciones y eliminaciones con un costo constante amortizado.

Los arreglos dinámicos son un ejemplo común al enseñar análisis amortizado . ^{[ 3 ] [ 4 ]}

El factor de crecimiento para la matriz dinámica depende de varios factores, incluyendo una compensación espacio-temporal y los algoritmos utilizados en el propio asignador de memoria. Para un factor de crecimiento a , el tiempo promedio por operación de inserción es aproximadamente a / ( a ​​− 1), mientras que el número de celdas desperdiciadas está limitado superiormente por ( a − 1) n . Si el asignador de memoria utiliza un algoritmo de asignación de primer ajuste , entonces valores del factor de crecimiento como a = 2 pueden hacer que la expansión de la matriz dinámica se quede sin memoria, incluso si todavía hay una cantidad significativa de memoria disponible. ^{[ 5 ]} Ha habido varias discusiones sobre valores ideales del factor de crecimiento, incluyendo propuestas para la proporción áurea , así como el valor 1,5. ^{[ 6 ]} Sin embargo, muchos libros de texto utilizan a = 2 por simplicidad y para fines de análisis. ^{[ 3 ] [ 4 ]}  

A continuación se muestran los factores de crecimiento utilizados por varias implementaciones populares:

El array dinámico tiene un rendimiento similar al de un array, con la adición de nuevas operaciones para agregar y eliminar elementos:

• Obtener o establecer el valor en un índice determinado (tiempo constante).
• Iterar sobre los elementos en orden (tiempo lineal, buen rendimiento de la caché)
• Insertar o eliminar un elemento en medio del array (tiempo lineal)
• Inserción o eliminación de un elemento al final del array (tiempo amortizado constante)

Los arreglos dinámicos se benefician de muchas de las ventajas de los arreglos, incluyendo una buena localidad de referencia y utilización de la caché de datos , compacidad (bajo consumo de memoria) y acceso aleatorio . Por lo general, solo tienen una pequeña sobrecarga fija adicional para almacenar información sobre el tamaño y la capacidad. Esto convierte a los arreglos dinámicos en una herramienta atractiva para construir estructuras de datos optimizadas para la caché . Sin embargo, en lenguajes como Python o Java, que imponen semántica de referencia, el arreglo dinámico generalmente no almacena los datos reales, sino referencias a los datos que residen en otras áreas de la memoria. En este caso, acceder a los elementos del arreglo de forma secuencial implica acceder a múltiples áreas de memoria no contiguas, por lo que se pierden muchas de las ventajas de la optimización para la caché de esta estructura de datos.

En comparación con las listas enlazadas , los arreglos dinámicos 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 mejor localidad de referencia; sin embargo, los arreglos dinámicos requieren 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 hacerlo en tiempo constante. Esta desventaja se mitiga con el búfer de espacio vacío y las variantes de vector por niveles que se describen en la sección Variantes más adelante. Además, en una región de memoria muy fragmentada , puede ser costoso o imposible encontrar espacio contiguo para un arreglo dinámico 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 a la vez que proporciona todas las operaciones de los arreglos dinámicos y las listas enlazadas de forma razonablemente eficiente, pero tanto la inserción al final como la iteración sobre la lista son más lentas que para un arreglo dinámico, en teoría y en la práctica, debido al almacenamiento no contiguo y a la sobrecarga del recorrido/manipulación del árbol.

Los búferes de huecos son similares a los arreglos dinámicos, pero permiten operaciones eficientes de inserción y eliminación agrupadas cerca de la misma ubicación arbitraria. Algunas implementaciones de deque utilizan deques de arreglos , que permiten la inserción/eliminación amortizada en tiempo constante en ambos extremos, en lugar de solo en uno.

Goodrich ^{[ 17 ]} presentó un algoritmo de matriz dinámica llamado vectores escalonados que proporciona un rendimiento O ( n ^{1/ k} ) para inserciones y eliminaciones desde cualquier lugar de la matriz, y O ( k ) obtener y establecer, 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. ^{[ 18 ]} El árbol de matriz hash desperdicia una cantidad de espacio de almacenamiento del orden de 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, ^{[ 19 ]} Brodnik et al. describen una estructura de datos de matriz dinámica por niveles, que desperdicia solo n ^1/2 espacio para n elementos en cualquier momento, y demuestran una cota 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 donde el crecimiento y la reducción del búfer no solo se amortizan, sino que también presentan un tiempo constante en el peor de los casos.

Bagwell (2002) ^{[ 20 ]} presentó el algoritmo VList, que puede adaptarse para implementar una matriz dinámica.

Los arreglos redimensionables ingenuos —también llamados "la peor implementación" de arreglos redimensionables— mantienen el tamaño asignado del arreglo exactamente lo suficientemente grande para todos los datos que contiene, tal vez llamando a realloc para cada elemento agregado al arreglo. Los arreglos redimensionables ingenuos son la forma más simple de implementar un arreglo redimensionable en C. No desperdician memoria, pero agregar al final del arreglo siempre toma Θ( n ) tiempo. ^{[ 18 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ]} Los arreglos de crecimiento lineal preasignan ("desperdician") Θ(1) espacio cada vez que redimensionan el arreglo, lo que los hace muchas veces más rápidos que los arreglos redimensionables ingenuos: agregar al final del arreglo todavía toma Θ( n ) tiempo pero con una constante mucho menor. Los arreglos redimensionables ingenuos y los arreglos de crecimiento lineal pueden ser útiles cuando una aplicación con restricciones de espacio necesita muchos arreglos redimensionables pequeños; También se utilizan comúnmente como ejemplo educativo que conduce a matrices dinámicas de crecimiento exponencial. ^{[ 25 ]}

Las implementaciones de C++ y std::vectorRust sonstd::vec::Vec de matrices dinámicas, al igual que java.util.ArrayList^{[ 26 ]} en Java ^{[ 27 ] : 236} y System.Collections.ArrayListen el .NET Framework . ^{[ 28 ] [ 29 ] : 22}

La clase genérica System.Collections.Generic.List<T>en la versión 2.0 de .NET Framework también se implementa con arreglos dinámicos. El de SmalltalkOrderedCollection es un arreglo dinámico con índice de inicio y fin 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 un array dinámico, cuyo patrón de crecimiento es: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... ^{[ 7 ]}

Delphi y D implementan matrices dinámicas en el núcleo del lenguaje.

El paquete genérico de AdaAda.Containers.Vectors proporciona una implementación de matrices dinámicas para un subtipo dado.

Muchos lenguajes de scripting, como Perl y Ruby, ofrecen matrices dinámicas como un tipo de dato primitivo incorporado .

Varios marcos multiplataforma proporcionan implementaciones de matrices dinámicas para C , incluyendo CFArrayy CFMutableArrayen Core Foundation , y GArrayy GPtrArrayen GLib .

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 .

• Pila (tipo de dato abstracto)
• Cola (tipo de dato abstracto)

• Diccionario de algoritmos y estructuras de datos del NIST: Matriz dinámica
• VPOOL - Implementación en lenguaje C de un array dinámico.
• CollectionSpy : un analizador de rendimiento de Java con soporte explícito para depurar problemas relacionados con ArrayList y Vector.
• Estructuras de datos abiertas - Capítulo 2 - Listas basadas en arreglos , Pat Morin