Array dinámico

En programación, un arreglo dinámico o array dinámico,^{[nota 1]}​ también llamado inapropiadamente matriz dinámica o tabla dinámica, es un array de elementos que crece o mengua dinámicamente conforme los elementos se agregan o se eliminan. Se suministra como librerías estándar en muchos lenguajes modernos de programación.

Un array dinámico no es lo mismo que un array asignado dinámicamente, que es un array de tamaño fijo, pero cuyo tamaño se fija cuando se asigna por primera vez.^[1]​

Arrays de tamaño predefinido y capacidad limitada

La forma más sencilla de construir un array dinámico es la asignación de espacio de tamaño fijo dividido en dos partes: la primera es la parte ocupada de del array y la segunda está libre para su crecimiento. Es sencillo así añadir o eliminar elementos en el extremo del array en tiempo constante usando el espacio reservado, hasta que este espacio se consume completamente. El número de elementos usados por el contenido del array dinámico es su tamaño lógico o simplemente tamaño, mientras que el tamaño del array subyacente se denomina la capacidad dinámica, que es el tamaño máximo posible sin reubicación de datos.array

En aplicaciones donde el tamaño lógico es conocido, las estructuras de tamaño fijo son las más eficientes, como es evidente, por lo que es mejor usar en estos casos arrays asignados dinámicamente, cuyo tamaño sea un parámetro de la ejecución, que pueda aumentarse cuando se detecta que se alcanzan los límites, optimizando el espacio ocupado.

El acceso a un elemento de un arreglo estático es de O(1), pues se accede siempre directamente al elemento, por tanto la implementación usando arreglos de tamaño fijo predefinido es de O(1). La inserción de un elemento es de O(1) siempre que quepa dentro del arreglo, si no cabe es imposible insertar, debiendo ampliarlo.

Expansión y coste

Cambiar el tamaño del array subyacente es una tarea costosa, implicando típicamente copiar el contenido del array a una nueva zona más grande de memoria, y liberar el espacio del array anterior, lo que puede generar muchos espacios libres en memoria, que pueden ser o no reutilizados, en función de si es el programa o el recolector de basura el encargado de hacerlo.

Para evitar incurrir en el costo del tiempo de cambio de tamaño, muchos arrays dinámicos cambian el tamaño en una cantidad mayor a la necesaria, por ejemplo duplica su tamaño, dejando así espacio reservado para futuras ampliaciones. La operación de añadir un elemento al final podría funcionar de la siguiente manera:

function insertarAlFinal(dynamicarray a, elemento e) // Si es necesario, duplicar el tamaño del array if (a.tamaño = a.capacidad) a.capacidad ← a.capacidad * 2 // Copiar el elemento a la ubicación de memoria  a[a.tamaño] ← e a.tamaño ← a.tamaño + 1 

Cuando se insertan n elementos, la capacidad lo hace en progresión geométrica. La expansión del array en cualquier proporción constante asegura que la inserción de elementos de n toma O(n) de tiempo total, lo que significa que cada inserción se amortiza en un tiempo constante. El valor de esta proporción a conduce a una solución del compromiso espacio-tiempo: el tiempo medio por operación de inserción es aproximadamente a/(a−1), mientras que la memoria desaprovechada está limitada superiormente por (a−1)n. La elección de a depende de la librería de funciones usada: algunos libros de texto utilizar a = 2,^[2]​^[3]​ pero la implementación en Java de un ArrayList utiliza a = 3/2,^[1]​ y la implementación en C de la estructura de datos para las listas en Python utiliza a = 9/8.^[4]​

Muchos arrays dinámicos también desasignan parte de su almacenamiento subyacente si su tamaño disminuye por debajo de un cierto umbral, tal como el 30% de la capacidad. Este umbral debe ser estrictamente menor que 1/a con el fin de que las secuencias mixtas de inserciones y eliminaciones tengan un coste constante.

Los arrays dinámicos son un ejemplo común en la enseñanza del coste y la amortización.^[2]​^[3]​

Rendimiento y comparación con otras estructuras

Los arrays dinámicos tienen un rendimiento similar a una array estático, con la adición de nuevas operaciones para añadir y eliminar elementos al final:

• Al obtener o establecer el valor de un índice en particular: Θ(1) (tiempo constante)
• Recorrer sus elementos en orden: Θ(n) (tiempo lineal, buen uso del caché de lectura)
• Insertar o eliminar un elemento no al final del array: Θ(n) (tiempo lineal)
• Insertar o eliminar un elemento al final del array: Θ(1) (tiempo constante amortizado)
• Espacio desperdiciado: Θ(n)^[5]​

Los arrays dinámicos se benefician de muchas de las ventajas de los arrays estáticos, incluido buena localización por referencia y uso de caché de datos, tamaño reducido (bajo uso de memoria) y capacidad de acceso aleatorio. Por lo general tienen solo una pequeña sobrecarga fija adicional para almacenar información sobre tamaño y capacidad. Esto hace de los arreglos dinámicos una herramienta atractiva para la construcción de estructuras de datos amigables y sencillas de usar.

En comparación con las listas enlazadas, los arreglos dinámicos tienen indexación más rápida (tiempo constante frente a tiempo lineal) y la iteración es típicamente más rápida debido a la localización por referencia, sin embargo, los arreglos estáticos y los dinámicos requieren de un tiempo lineal para insertar o eliminar en una ubicación arbitraria, ya que todos los elementos siguientes deben ser movidos, mientras que las listas enlazadas se puede hacer esto en tiempo constante. Esta desventaja se ve mitigado usando un gap buffer (buffer de huecos), y variantes escalonadas vectoriales. También, en una región de memoria muy fragmentada, puede ser costoso o imposible encontrar espacio contiguo para ampliar un array dinámico grande, mientras que las listas enlazadas no requieren que la estructura de datos completa se almacene de forma contigua.

Un árbol equilibrado puede almacenar una lista, además de proporcionar las operaciones posibles en arrays dinámicos y en listas enlazadas, de forma razonablemente eficiente, pero tanto la inserción al final como la iteración sobre la lista son más lentos que para los arrays dinámicos, tanto en la teoría como en la práctica, debido a la falta de almacenamiento contiguo y las manipulaciones transversales en el recorrido del árbol.

Implementación con listas enlazadas o árboles

Otra posibilidad de implementar un arreglo dinámico es usar listas enlazadas, simples para arreglos de una dimensión, dobles para arreglos de dos dimensiones, etc. Las listas deben mantener contadores de elementos manuales, y disponer de punteros a la cabeza y a la cola para poder insertar rápidamente elementos.

Estas estructuras tienen la ventaja de que no penalizan el crecimiento del tamaño ya que solo es necesario reservar espacio para un nuevo elemento y añadirlo a la lista manteniendo Θ(1), pero a cambio las operaciones de lectura y escritura necesitan recorrer las listas para alcanzar el elemento a leer o cambiar, pasando a Θ(n/2).

Las listas enlazadas se usan mucho para almacenar arreglos de muchos elementos casi vacíos, ya que pueden ahorrar mucho espacio de almacenamiento. En este caso un elemento debe disponer no solo del indicador de su posición en el arreglo sino también de la posición del siguiente elemento, así el recorrido es más rápido al no deber leer el siguiente elemento para conocer el dato de su posición en el arreglo.

Otra estructura usada para implementar los arreglos dinámicos son los árboles binarios, que se recorren muy rápido y pueden crecer muy bien, proporcionan Θ(log n) en lectura y modificación, y Θ(n) para insertar un nuevo elemento al final del arreglo.

Variantes

Los Buffers Gap o buffer de huecos, usados sobre todo en procesadores de texto, son similares a los arrays dinámicos, pero permiten la inserción y eliminación más eficiente en cualquier ubicación arbitraria Algunas implementaciones de la cola doblemente terminada (en inglés conocidas como DEQUE) utilizan arrays, lo que permiten un tiempo constante amortizado de inserción/borrado en ambos extremos, en lugar de solo uno de los extremos.

Goodrich^[6]​ presentó un algoritmo para arrays dinámicos al que llamó Vectores por niveles (Tiered Vectors), que proveían una O(n^1/2) en el rendimiento de las inserciones o borrados al preservar el orden de mitad del array.

El árbol hash de arrays (en inglés Hashed Array Tree o HAT) es un algoritmo de array dinámico publicado por Sitarski en 1996.^[7]​ El HAT provee una O(n^1/2) en la cantidad de espacio de almacenamiento, donde n es el número de elementos en el array. El algoritmo tiene O(1) de rendimiento amortizado se añaden una serie de objetos al final de un HAT.

Brodnik y otros, en su documento de 1999^[5]​, describen un array dinámico escalonado como estructura de datos que gasta solo O(n^1/2) de espacio para n elementos en cualquier momento, y demuestran un límite inferior que demuestra que cualquier array dinámico debemos desperdiciar mucho espacio si las operaciones han de permanecer en un tiempo constante amortizado. Además, presentan una variante donde crece y encoge el buffer tiene no solo tiempo amortizado, sino tiempo constante en el peor de los casos.

Bagwell^[8]​ presenta en 2002 el algoritmo VList, que puede ser adaptado para implementar un array dinámico.

Implementación en varios lenguajes

• En C++ se usa std::vector, que contiene una implementación de los arrays dinámicos.
• En Java se usa la clase ArrayList.^[9]​
• En .NET Framework se usa la clase ArrayList, la clase genérica List<> suministra con la versión 2.0 del .NET Framework se ejecuta también con arrays dinámicos.
• En Smalltalk OrderedCollection es un array dinámico, con comienzo y final con índice dinámico, haciendo la eliminación del primer elemento también del O(1).
• En Python el tipo de datos list usa una implementación de datos con un array dinámico.
• En Delphi y D se implementan los arrays dinámicos en el núcleo del lenguaje.
• En Ada el paquete Ada.Containers.Vectors proporciona una implementación genérica de un array dinámico para un subtipo determinado.
• Muchos lenguajes de script como Perl y Rubí ofrece arrays dinámicos como tipo de datos primitivo incorporado.
• Varios framework de plataformas cruzadas proporcionar implementaciones de arrays dinámicos en C, como CFArray y CFMutableArray en Core Fundación para Mac OS X e iOS, o GArray y GPtrArray en GLib para GTK+.

Ejemplos en Java

Para este tipo datos que crecen y decrecen se podría utilizar la clase Vector, pero es más apropiado utilizar la clase Arraylist implementada en el paquete java.util. ArrayList es una de las muchas clases del Collection Framework, que proporciona un conjunto de interfaces y clases bien-diseñados para almacenar y manipular grupos de datos como una sola unidad, una colección.

Existen varios constructores para los Arraylist, que podemos usar dependiendo de como queramos utilizarlo, aunque básicamente se emplean dos:

• ArrayList() construye un ArrayList con capacidad cero por defecto, pero crecerá según le vayamos añadiendo:

ArrayList al = new ArrayList();

• ArrayList(int CapacidadInicial) construye un ArrayList vacío con una capacidad inicial especificada:

ArrayList al2 = new ArrayList(5);

Para insertar un objeto al ArrayList debemos llamar a sus métodos con el operador punto:

 al.add("El manual de Java"); // Añade una cadena al.add(new Double(40.00)); // Añade un dato de tipo double de una clase envoltorio (wrapper class) System.out.println(al.size()); // Presenta el tamaño del array 

Para navegar por los elementos del ArrayList se utiliza la clase Iterator y sus métodos hasNext y next:

 Iterator alIt = al.iterator(); while (alIt.hasNext()) { System.out.println(alIt.next() + " "); } 

Notas

1. En español debe usarse la palabra Arreglo en lugar del muy extendido anglicismo Array.

Referencias

1. Ver por ejemplo source code of java.util.ArrayList class from OpenJDK 6.
2. Michael T., Goodrich; Tamassia, Roberto (2002). Algorithm Design: Foundations, Analysis and Internet Examples. Capítulo 1.5.2 Analyzing an Extendable Array Implementation: Wiley. pp. 39-41. 
3. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001 [1990]). Introduction to Algorithms (2nd ed.). Capítulo 17.4 "Dynamic tables": MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7. 
4. python.org. «List object implementation». Consultado el 3 de febrero de 2013. 
5. Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (Technical Report CS-99-09). «Resizable Arrays in Optimal Time and Space». Department of Computer Science (University of Waterloo). Consultado el 3 de febrero de 2013. 
6. Goodrich, Michael T.; Kloss II, John G. (1999). «Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences». actas de la Workshop on Algorithms and Data Structures; Lecture Notes in Computer Science 1663. Lecture Notes in Computer Science 1663: 205–216. ISBN 978-3-540-66279-2. doi:10.1007/3-540-48447-7_21. Consultado el 3 de febrero de 2013. 
7. Sitarski, Edward (septiembre de 1996). «HATs: Hashed array trees». Dr. Dobb's Journal 21 (11). 
8. Bagwell, Phil (2002). «Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays». EPFL. 
9. Javadoc on ArrayList

•   Datos: Q128555