Matriz dinámica

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 31 de marzo de 2015; la verificación requiere 51 ediciones .

Una matriz se llama dinámica , cuyo tamaño puede cambiar durante la ejecución del programa. La capacidad de cambiar el tamaño distingue una matriz dinámica de una estática, cuyo tamaño se establece en el momento en que se compila el programa. Para cambiar el tamaño de una matriz dinámica , un lenguaje de programación que admita tales matrices debe proporcionar una función u operador integrado. Los arreglos dinámicos permiten un trabajo más flexible con los datos, ya que no permiten predecir los volúmenes de datos almacenados, sino ajustar el tamaño del arreglo de acuerdo con los volúmenes realmente requeridos.

Además, a veces las matrices dinámicas son matrices de longitud variable , cuyo tamaño no se fija durante la compilación, sino que se establece cuando se crea o inicializa la matriz durante la ejecución del programa. Se diferencian de las matrices dinámicas "reales" en que no proporcionan un cambio de tamaño automático con conservación del contenido, por lo que el programador debe implementar dicha función si es necesario.

Soporte en lenguajes de programación

Las matrices dinámicas se pueden admitir en el nivel de sintaxis del propio lenguaje de programación o en el nivel de las bibliotecas del sistema. La descripción de una matriz dinámica puede ser sintácticamente diferente de la descripción de una estática, pero puede ser la misma. En el segundo caso, por regla general, todos los arreglos en el lenguaje son potencialmente dinámicos, y queda a criterio del programador si usar esta propiedad en cada caso particular. Cuando son compatibles con matrices dinámicas a través de bibliotecas del sistema, generalmente se implementan como clases (en el sentido de programación orientada a objetos ) o tipos genéricos (las llamadas "plantillas" o "genéricos"); la declaración de matriz en este caso es una instanciación de una clase o una instanciación de un tipo genérico. Según el idioma, las matrices dinámicas solo pueden ser matrices unidimensionales o tener dos o más dimensiones.

La compatibilidad con matrices dinámicas implica la presencia obligatoria de una operación integrada para determinar el tamaño actual de una matriz. El tamaño inicial de una matriz dinámica es igual a cero o se establece durante la descripción o la inicialización. El cambio de tamaño adicional se realiza mediante una operación integrada especial (procedimiento). En algunos lenguajes (por ejemplo , JavaScript , Lua ), la expansión de la matriz se produce automáticamente cuando se intenta escribir en una celda inexistente.

Implementación

Para que las matrices puedan cambiar de tamaño dinámicamente, la implementación debe encontrar un "medio dorado" entre varios requisitos en conflicto.

Memoria eficiente : la implementación no debería generar una sobrecarga de memoria significativa.
Rendimiento Eficiencia , que incluye:
- sobrecarga mínima para cambiar el tamaño de la matriz;
- ahorrando, si es posible, un tiempo de acceso de lectura/escritura constante a los elementos del arreglo.
Compatibilidad de bajo nivel con arreglos estáticos regulares . Por ejemplo, un requisito previo para usar una matriz dinámica en las llamadas a las funciones de la API del sistema operativo puede ser que los elementos de la matriz se coloquen en un bloque contiguo de RAM física en el orden correspondiente a la indexación de la matriz. Si no se cumple este requisito, las matrices dinámicas no se pueden usar junto con código de bajo nivel.

Dependiendo de la prioridad de ciertos requisitos, se selecciona el método de implementación que los cumple.

Matrices de longitud variable

La implementación de arreglos de longitud variable difiere poco de la implementación de arreglos estáticos ordinarios. Una matriz de elementos de tipo T de longitud variable generalmente se almacena en un bloque de RAM contiguo de tamaño , donde N es el número de elementos especificado al describir (crear) la matriz. Es decir, la declaración de una matriz de longitud variable, de hecho, simplemente enmascara la asignación dinámica de memoria. La diferencia puede ser que (por ejemplo, como en C99 y versiones posteriores) se asigna memoria en la pila a una matriz de longitud variable, como otras variables automáticas, mientras que la forma típica de asignación de memoria dinámica (en la función C ) asigna memoria en la pila. montón _ Además, para una matriz de longitud variable, el compilador generalmente genera automáticamente un código de desasignación de memoria cuando la matriz declarada queda fuera del alcance. $sizeof(T)\cdot N$ malloc

Mover una matriz en la memoria

Lo más común para los típicos lenguajes compilados de procedimientos es implementar el cambio de tamaño de una matriz moviéndola en la memoria del montón.

Se asigna un fragmento de RAM para la matriz, cuyo tamaño es mayor que el llamado requerido. tamaño lógico (tamaño o longitud). La cantidad de elementos que realmente se pueden colocar en esta memoria se denomina capacidad de la matriz dinámica. La longitud actual de la matriz se almacena en un contador separado. Se puede usar para determinar el tamaño actual, así como para controlar el desbordamiento de la matriz, si el idioma admite dicho control. Así, en realidad, un array dinámico es un array de tamaño fijo, en el que sólo se ocupa una parte de las celdas.
El comando para aumentar el tamaño de la matriz, si el nuevo tamaño no supera la capacidad, simplemente cambia el contador de longitud de la matriz al tamaño deseado. No hay cambios en la matriz en sí.
Una instrucción de aumento en la que el nuevo tamaño supera la capacidad hace que la matriz se reubique en la memoria:

se asigna un nuevo fragmento de RAM, cuyo tamaño excede el tamaño de la matriz;
el contenido de la matriz se copia en la memoria recién asignada;
el tamaño y la capacidad de la matriz se actualizan;
en la estructura de servicio que almacena los parámetros de la matriz, el valor del puntero de datos se cambia a uno nuevo;
se lanza el comando para liberar el fragmento de RAM previamente asignado para el arreglo; si el idioma admite la administración automática de memoria , la liberación de memoria previamente asignada para la matriz permanece en el recolector de elementos no utilizados.

El comando para reducir el tamaño de una matriz puede provocar su movimiento en la memoria si, como resultado de su ejecución, el porcentaje de celdas ocupadas en la matriz cae por debajo de un valor determinado. El movimiento en este caso se lleva a cabo de acuerdo con el mismo esquema que en el caso del comando para aumentar la matriz.

Esta implementación es la más eficiente en términos de velocidad de acceso a celdas de matriz ya asignadas. Además, proporciona un tiempo de acceso constante a cualquier elemento, independientemente de su índice. Sin embargo, la sobrecarga adicional de las operaciones de cambio de tamaño puede ser significativa. El valor de estos costos depende de los parámetros del algoritmo de movimiento de matriz.

La capacidad inicial y el incremento de capacidad a medida que aumenta el tamaño. Se puede especificar como un valor relativo (una cierta fracción de la longitud lógica de la matriz) o como un incremento absoluto sobre la longitud de la matriz requerida. Cuanto más grandes sean estos parámetros, más tarde, con el mismo modo de relleno de matriz, se requerirá el siguiente movimiento, pero más memoria quedará potencialmente sin usar. Expandir la matriz por cualquier factor constante garantiza que la inserción de n elementos tomará O (n) tiempo, lo que significa que cada inserción toma una cantidad de tiempo específica y definida. El valor numérico de este coeficiente da lugar a diferentes indicadores: el tiempo medio de inserción de una operación es a/(a-1), mientras que el número de celdas desperdiciadas es (a-1)n. El valor de esta constante en diferentes aplicaciones y bibliotecas puede ser diferente: muchos libros de texto usan el valor 2, pero la implementación del lenguaje Java de ArrayList usa un factor de 3/2, en algunos otros casos usan a=9/8.
Capacidad mínima. Por lo general, se establece por razones de eficiencia, para no perder rendimiento cuando se cambia el tamaño de los arreglos pequeños con frecuencia. En la práctica, configurarlo significa que todas las matrices dinámicas más pequeñas que la capacidad mínima desperdiciarán memoria.
El porcentaje de relleno mínimo de la matriz. Especifica cuándo se producirá la reubicación después de que se haya reducido el tamaño de la matriz. Cuanto mayor sea este valor, más a menudo se producirá el movimiento cuando el tamaño de la matriz disminuya. Cuanto más pequeña sea, más memoria permanecerá ocupada pero no utilizada cuando se reduzca el tamaño de la matriz.

Existen varias estimaciones de los valores óptimos para los parámetros del algoritmo de movimiento, pero a partir de consideraciones generales, está claro que ninguno de los métodos para determinarlos garantiza la máxima eficiencia en todos los casos, y para cualquiera es posible elegir un algoritmo. para trabajar con una matriz, en la que el movimiento será ineficiente. Para compensar los efectos negativos, muchos lenguajes que admiten arreglos dinámicos tienen parámetros adicionales en los comandos de aumento/disminución del arreglo que le permiten controlar directamente la capacidad del arreglo. Si el programador sabe con certeza hasta qué tamaño aumentará/disminuirá la matriz como resultado de esta o aquella operación, y cómo se procesará la matriz en el futuro, puede especificar directamente la capacidad final requerida en el comando de cambio de tamaño, evitando así un gran número de movimientos sin sentido.

Otros algoritmos de asignación dinámica

Hay muchos algoritmos para implementar arreglos dinámicos, además de los anteriores. Por lo tanto, es posible implementar otras diversas estructuras de datos con la ayuda de celdas de memoria dinámica conectadas por enlaces. La mayoría de estos métodos brindan una ventaja en algunas condiciones específicas, pero no brindan un tiempo de acceso constante o son incompatibles con matrices estáticas y, por lo tanto, no pueden funcionar con código de bajo nivel.

Uso

Las matrices dinámicas se utilizan para procesar conjuntos de datos homogéneos cuyo tamaño no se conoce exactamente en el momento de escribir el programa, pero que potencialmente pueden caber en la memoria disponible. Sin el uso de arreglos dinámicos, la solución de tales problemas se reduce a una de las siguientes estrategias:

asignación de una matriz estática de gran tamaño, obviamente suficiente para la colocación completa de datos;
usar una matriz estática como un búfer en el que se cargan los datos en partes;
uso de otras estructuras de datos dinámicas (por ejemplo, listas).

La primera opción es aplicable solo cuando el tamaño del conjunto de datos cambia dentro de un rango pequeño y limitado (por ejemplo, en el procesamiento de textos, un límite de 1000 caracteres por línea es bastante aceptable). De lo contrario, la elección de una matriz pequeña limitará la funcionalidad del programa, y una grande (para que sea suficiente para cualquier dato de entrada) conducirá a un uso ineficiente de la memoria. El almacenamiento en búfer de procesamiento complica el algoritmo, y otras estructuras dinámicas en tareas de procesamiento de grandes secuencias de datos simples no se pueden comparar con una matriz en términos de eficiencia.

El uso de matrices dinámicas le permite asignar exactamente tanta memoria como sea realmente necesaria (inmediatamente, si la tarea le permite determinar la cantidad antes de cargar los datos, o durante la carga, expandiendo la matriz según sea necesario), cargue todos los datos en uno ordenarlos y procesarlos uniformemente. Sin embargo, esta estrategia también tiene desventajas:

disminución de la velocidad debido a los costos generales por cambiar el tamaño de una matriz dinámica;
disminución potencial de la confiabilidad: con una cantidad extremadamente grande de datos de entrada, un intento de aumentar la matriz al tamaño adecuado puede provocar una ralentización significativa repentina o incluso la falla del programa debido a la falta de memoria libre.

En general, se puede ver que el soporte de arreglos dinámicos aumenta la conveniencia del desarrollo, pero no releva al programador de la necesidad de evaluar las necesidades de memoria del programa; también requiere comprender las características de una implementación específica de matrices dinámicas y hacer coincidir los algoritmos de procesamiento de datos con estas características.

Ejemplos

Pascual

Las matrices dinámicas son compatibles con Delphi , FreePascal , pero no con Turbo Pascal .

var byteArray : matriz de bytes ; // Array unidimensional multiArray : Array of Array of string ; // Matriz multidimensional ... empieza ... // Establece el tamaño de una matriz unidimensional en n elementos SetLength ( byteArray , n ) ; // El acceso a una matriz dinámica es similar al acceso a una normal. // La indexación siempre comienza desde cero, los índices siempre son números enteros. matriz de bytes [ 0 ] := 10 ; // Redimensionar a m elementos. EstablecerLongitud ( matriz de bytes , m ) ; ... // Establecer el tamaño de una matriz bidimensional en elementos X*Y SetLength ( multiArray , X , Y ) ; multiArray [ 7 , 35 ] := 'ru.wikipedia.org' ; ... final .

xi

No hay matrices dinámicas en el lenguaje C en sí, pero las funciones mallocde biblioteca estándar freele reallocpermiten implementar una matriz de tamaño variable:

int * mas = ( int * ) malloc ( tamaño de ( int ) * n ); // Crea una matriz de n elementos de tipo int ... mas = ( int * ) realloc ( mas , tamaño de ( int ) * m ); // Cambiar el tamaño de la matriz de n a m, manteniendo el contenido ... libre ( más ); // Liberando memoria después de usar la matriz

La desventaja de este enfoque es la necesidad de calcular el tamaño de la memoria asignada, aplicar una conversión de tipo explícita y monitorear cuidadosamente la vida útil de la matriz (como siempre ocurre con la memoria asignada dinámicamente en C).

Una matriz dinámica multidimensional se puede crear como una matriz de punteros a matrices:

int ** A = ( int ** ) malloc ( N * tamaño de ( int * )); para ( int yo = 0 ; yo < norte ; yo ++ ) { A [ i ] = ( int * ) malloc ( M * sizeof ( int )); }

Sin embargo, el aumento de la dimensión complica significativamente los procedimientos para crear una matriz y liberar memoria una vez que se completa su uso. La tarea de cambiar el tamaño de una matriz a lo largo de una o más coordenadas se vuelve aún más complicada.

Algunos compiladores de C proporcionan una función de biblioteca no estándar void *alloca(size_t size)que facilita un poco el trabajo con matrices dinámicas. Esta función asigna memoria no en el montón, como malloc, sino en la pila, y esta memoria se libera automáticamente cuando se alcanza el operador return. Es decir, cuando esta función asigna una matriz dinámica, no es necesario eliminarla manualmente, pero dicha matriz no puede devolverse desde la función al punto de llamada.

Desde la versión del estándar C99 , se han introducido en el lenguaje arreglos de longitud variable. En la sintaxis habitual para declarar una matriz C, en lugar del tamaño de la matriz, no solo se puede indicar una constante, sino también una variable de tipo entero:

void func ( int arraySize ) { intmas [ tamaño de la matriz ] ; // Descripción de una matriz de longitud variable para ( int i = 0 ; i < arraySize ; ++ i ) { mas [ i ] = otraFunc ( i ); // Haciendo referencia a los elementos de la matriz } ... }

Una matriz de longitud variable se puede establecer en cualquier tamaño deseado en el momento de la creación. La memoria para ello se asigna en la pila. Una matriz de longitud variable existe hasta que abandona el ámbito en el que se declaró, después de lo cual su memoria se libera automáticamente. Como en el caso anterior, una matriz de longitud variable no se puede devolver desde una función a la persona que llama.

C++

La biblioteca estándar proporciona una clase de plantilla std::vector[1] que implementa la funcionalidad de una matriz dinámica:

// Declarar una matriz mas, que inicialmente contiene los números 1 - 5: std :: vector < int > mas = { 1 , 2 , 3 , 4 , 5 }; más _ reserva ( 100 ); // Reserve espacio de almacenamiento para al menos 100 artículos sin cambiar el tamaño real. El contenido sigue siendo el mismo. más _ cambiar el tamaño ( 50 ); // Establecer el tamaño explícito en exactamente 50 elementos. Los elementos faltantes obtendrán el valor "predeterminado", los elementos adicionales se eliminarán. mas [ yo ] = yo ; // Asignar i'th elemento el valor i mas . retroceder ( 100 ); // Agrega un elemento al final de la matriz int x = mas . atrás (); // Accede al último elemento, en este ejemplo x == 100 mas . pop_back (); // Elimina el último elemento std :: cout << mas . tamaño () << " " << mas . capacidad () << " \n " ; // Capacidad de visualización y tamaño real automático mas2 = mas ; // La variable mas2 contiene una copia completa de mas

std::vectortiene muchos métodos y operadores, algunos de los cuales se muestran en el ejemplo anterior. Le permiten acceder por índice, cambiar el tamaño de la matriz en cualquier dirección, usarla como una pila, escribir un nuevo valor en una posición arbitraria de la matriz (con un cambio de los elementos restantes) y, en general, admiten la semántica. del tipo de valor : copiar, intercambiar, mover, transferir en una función y devolver, comparación de elementos con otro objeto del mismo tipo. No solo se gestiona el tamaño real, sino también la capacidad, lo que permite optimizar el proceso de asignación de memoria.

std::vectorimplementa el principio RAII : posee sus subobjetos, asigna y libera memoria y llama correctamente a los constructores/destructores.

El estándar C++ requiere una implementación para cumplir con las siguientes condiciones:

todos los elementos de la matriz deben almacenarse en una fila en orden creciente de índice en un bloque integral de RAM;
se debe garantizar un tiempo de acceso constante a un elemento arbitrario.

El trabajo de bajo nivel con memoria dinámica se puede implementar por medios heredados del lenguaje ancestral , pero para garantizar la seguridad de tipo y cumplir con los requisitos del modelo de objeto, se recomienda asignar memoria para matrices utilizando operadores específicos del lenguaje new []y delete []:

// Asignar memoria para una matriz int de longitud n int * mas = new int [ n ]; ... // Liberando la memoria del arreglo delete [] mas ;

Entre otras cosas, esto le permite redefinir operadores para tipos definidos por el usuario new []y delete [], por lo tanto, implementar sus propios esquemas de asignación de memoria.

En C++ moderno, la administración manual de la memoria es una base esencial para implementar contenedores de plantillas, pero presenta dificultades significativas incluso para programadores experimentados y no se recomienda su uso en el código de la aplicación. [2] [3]

Notas

↑ std::vector-cppreference.com . Consultado el 16 de octubre de 2021. Archivado desde el original el 28 de junio de 2011. (indefinido)
↑ Directrices básicas de C++: R.1: Administre los recursos automáticamente mediante identificadores de recursos y RAII (Adquisición de recursos es inicialización) . Consultado el 16 de octubre de 2021. Archivado desde el original el 8 de febrero de 2020. (indefinido)
↑ Directrices básicas de C++: R.11: Evite llamar a new y eliminar explícitamente . Consultado el 16 de octubre de 2021. Archivado desde el original el 8 de febrero de 2020. (indefinido)

Estructuras de datos
Liza	formación lista enlazada simple lista doblemente enlazada lista de pases
Árboles	árbol B Árbol de búsqueda binario árbol AVL árbol rojo-negro montón
cuenta	Gráfico dirigido Gráfico Acíclico Dirigido Diagrama de decisión binaria Hipergrafo
Otro	Tabla de picadillo Pila