Matriz (estructura de datos)

En informática, una matriz es una estructura de datos que consiste en una colección de elementos (valores o variables), cada uno identificado por al menos un índice de matriz o clave. Una matriz se almacena de tal manera que la posición de cada elemento se puede calcular a partir de su tupla de índice mediante una fórmula matemática. El tipo más simple de estructura de datos es una matriz lineal, también llamada matriz unidimensional.

Por ejemplo, una matriz de diez variables enteras de 32 bits (4 bytes), con índices del 0 al 9, puede almacenarse como diez palabras en las direcciones de memoria 2000, 2004, 2008,..., 2036, (en hexadecimal: 0x7D0, 0x7D4, 0x7D8,..., 0x7F4) para que el elemento con índice i tiene la dirección 2000 + (i × 4). La dirección de memoria del primer elemento de una matriz se denomina primera dirección, dirección base o dirección base.

Debido a que el concepto matemático de una matriz se puede representar como una cuadrícula bidimensional, las matrices bidimensionales también se denominan a veces "matrices". En algunos casos, el término "vector" se usa en computación para referirse a una matriz, aunque las tuplas en lugar de los vectores son el equivalente matemáticamente más correcto. Las tablas a menudo se implementan en forma de matrices, especialmente tablas de búsqueda; la palabra "mesa" a veces se usa como sinónimo de matriz.

Las matrices se encuentran entre las estructuras de datos más antiguas e importantes, y casi todos los programas las utilizan. También se utilizan para implementar muchas otras estructuras de datos, como listas y cadenas. Explotan efectivamente la lógica de direccionamiento de las computadoras. En la mayoría de las computadoras modernas y muchos dispositivos de almacenamiento externo, la memoria es una matriz unidimensional de palabras, cuyos índices son sus direcciones. Los procesadores, especialmente los procesadores vectoriales, a menudo se optimizan para operaciones de matriz.

Las matrices son útiles principalmente porque los índices de los elementos se pueden calcular en tiempo de ejecución. Entre otras cosas, esta característica permite que una sola declaración iterativa procese arbitrariamente muchos elementos de una matriz. Por esa razón, los elementos de una estructura de datos de matriz deben tener el mismo tamaño y deben usar la misma representación de datos. El conjunto de tuplas de índice válidas y las direcciones de los elementos (y, por lo tanto, la fórmula de direccionamiento de elementos) generalmente, pero no siempre, se fijan mientras la matriz está en uso.

El término "matriz" también puede referirse a un tipo de datos de matriz, un tipo de tipo de datos proporcionado por la mayoría de los lenguajes de programación de alto nivel que consiste en una colección de valores o variables que pueden seleccionarse mediante uno o más índices calculados en tiempo de ejecución. Los tipos de matriz a menudo se implementan mediante estructuras de matriz; sin embargo, en algunos idiomas pueden implementarse mediante tablas hash, listas vinculadas, árboles de búsqueda u otras estructuras de datos.

El término también se usa, especialmente en la descripción de algoritmos, para referirse a una matriz asociativa o "matriz abstracta", un modelo informático teórico (un tipo de datos abstracto o ADT) destinado a capturar las propiedades esenciales de matrices.

Historia

Las primeras computadoras digitales usaban programación en lenguaje de máquina para configurar y acceder a estructuras de matrices para tablas de datos, cálculos de vectores y matrices, y para muchos otros fines. John von Neumann escribió el primer programa de clasificación de matrices (clasificación por fusión) en 1945, durante la construcción de la primera computadora con programa almacenado.^{p. 159} La indexación de matrices se realizó originalmente mediante código automodificable y, más tarde, mediante registros de índice y direccionamiento indirecto. Algunos mainframes diseñados en la década de 1960, como el Burroughs B5000 y sus sucesores, utilizaron la segmentación de la memoria para realizar la verificación de límites de índice en el hardware.

Los lenguajes ensambladores generalmente no tienen soporte especial para matrices, aparte de lo que proporciona la propia máquina. Los primeros lenguajes de programación de alto nivel, incluidos FORTRAN (1957), Lisp (1958), COBOL (1960) y ALGOL 60 (1960), tenían soporte para matrices multidimensionales, al igual que C (1972). En C++ (1983), existen plantillas de clase para arreglos multidimensionales cuya dimensión se fija en tiempo de ejecución, así como para arreglos flexibles en tiempo de ejecución.

Aplicaciones

Los arreglos se utilizan para implementar matrices y vectores matemáticos, así como otros tipos de tablas rectangulares. Muchas bases de datos, pequeñas y grandes, consisten en (o incluyen) arreglos unidimensionales cuyos elementos son registros.

Las matrices se utilizan para implementar otras estructuras de datos, como listas, montones, tablas hash, deques, colas, pilas, cadenas y VLists. Las implementaciones basadas en arreglos de otras estructuras de datos son con frecuencia simples y eficientes en cuanto al espacio (estructuras de datos implícitas), requieren poca sobrecarga de espacio, pero pueden tener poca complejidad de espacio, particularmente cuando se modifican, en comparación con las estructuras de datos basadas en árboles (compare un arreglo ordenado con un árbol de búsqueda).

A veces se utilizan una o más matrices grandes para emular la asignación de memoria dinámica en el programa, en particular la asignación de grupos de memoria. Históricamente, esta ha sido a veces la única forma de asignar "memoria dinámica" portátil.

Las matrices se pueden usar para determinar el flujo de control parcial o completo en los programas, como una alternativa compacta a (de otro modo repetitivo) múltiples declaraciones IF. Se conocen en este contexto como tablas de control y se utilizan junto con un intérprete especialmente diseñado cuyo flujo de control se modifica según los valores contenidos en la matriz. La matriz puede contener punteros de subrutina (o números de subrutina relativos sobre los que pueden actuar las sentencias SWITCH) que dirigen la ruta de la ejecución.

Identificador de elementos y fórmulas de direccionamiento

Cuando los objetos de datos se almacenan en una matriz, los objetos individuales se seleccionan mediante un índice que suele ser un entero escalar no negativo. Los índices también se denominan subíndices. Un índice mapea el valor de la matriz a un objeto almacenado.

Hay tres formas de indexar los elementos de una matriz:

0Indización basada en cero)

El primer elemento de la matriz se indexa por subscripto de 0.

1 (indexación basada en una sola base)

El primer elemento de la matriz se indexa por subscripto de 1.

No.indexación basada en n)

El índice base de un array se puede elegir libremente. Generalmente los idiomas de programación indexación basada en n También permite valores índice negativos y otros tipos de datos de escalar como enumeraciones, o los caracteres pueden ser utilizados como índice de matriz.

El uso de la indexación basada en cero es la opción de diseño de muchos lenguajes de programación influyentes, incluidos C, Java y Lisp. Esto conduce a una implementación más simple donde el subíndice se refiere a un desplazamiento desde la posición inicial de una matriz, por lo que el primer elemento tiene un desplazamiento de cero.

Los arreglos pueden tener múltiples dimensiones, por lo que no es raro acceder a un arreglo usando múltiples índices. Por ejemplo, una matriz bidimensional A con tres filas y cuatro columnas podría proporcionar acceso al elemento en la segunda fila y la cuarta columna mediante la expresión A[1][3] en el caso de un sistema de indexación de base cero. Por lo tanto, se utilizan dos índices para una matriz bidimensional, tres para una matriz tridimensional y n para una matriz n-dimensional.

La cantidad de índices necesarios para especificar un elemento se denomina dimensión, dimensionalidad o rango de la matriz.

En las matrices estándar, cada índice está restringido a un cierto rango de números enteros consecutivos (o valores consecutivos de algún tipo enumerado), y la dirección de un elemento se calcula mediante un "lineal" fórmula en los índices.

Arreglos unidimensionales

Una matriz unidimensional (o matriz de una sola dimensión) es un tipo de matriz lineal. El acceso a sus elementos implica un solo subíndice que puede representar un índice de fila o columna.

Como ejemplo, considere la declaración C int anArrayName[10]; que declara una matriz unidimensional de diez enteros. Aquí, la matriz puede almacenar diez elementos de tipo int. Esta matriz tiene índices que van desde cero hasta nueve. Por ejemplo, las expresiones anArrayName[0] y anArrayName[9] son el primer y último elemento respectivamente.

Para un vector con direccionamiento lineal, el elemento con índice i se ubica en la dirección B + c × i, donde B es una dirección base fija y c una constante fija, a veces llamado incremento de dirección o zancada.

Si los índices de elementos válidos comienzan en 0, la constante B es simplemente la dirección del primer elemento de la matriz. Por esta razón, el lenguaje de programación C especifica que los índices de los arreglos siempre comienzan en 0; y muchos programadores llamarán a ese elemento "ceroth" en lugar de "primero".

Sin embargo, se puede elegir el índice del primer elemento mediante una elección adecuada de la dirección base B. Por ejemplo, si la matriz tiene cinco elementos, indexados del 1 al 5, y la dirección base B se reemplaza por B + 30c, entonces los índices de esos mismos elementos serán del 31 al 35. Si la numeración no comienza en 0, la constante B puede no ser la dirección de ningún elemento.

Arreglos multidimensionales

Para una matriz multidimensional, el elemento con índices i,j tendría la dirección B + c · i + d · j, donde los coeficientes c y d son los < i>fila y incrementos de dirección de columna, respectivamente.

Más generalmente, en una matriz k-dimensional, la dirección de un elemento con índices i1, i2,..., ik es

B + c1 · i1 + c2 · i2 +... + ck · ik.

Por ejemplo: int a[2][3];

Esto significa que el arreglo a tiene 2 filas y 3 columnas, y el arreglo es de tipo entero. Aquí podemos almacenar 6 elementos, se almacenarán linealmente pero comenzando desde la primera fila lineal y luego continuando con la segunda fila. La matriz anterior se almacenará como 11, a12, a13, a21, a22, un23.

Esta fórmula requiere solo k multiplicaciones y k adiciones, para cualquier matriz que quepa en la memoria. Además, si cualquier coeficiente es una potencia fija de 2, la multiplicación puede reemplazarse por un cambio de bits.

Los coeficientes ck deben elegirse de modo que cada tupla índice válida se asigne a la dirección de un elemento distinto.

Si el valor legal mínimo para cada índice es 0, entonces B es la dirección del elemento cuyos índices son todos cero. Como en el caso unidimensional, los índices de los elementos se pueden cambiar cambiando la dirección base B. Por lo tanto, si una matriz bidimensional tiene filas y columnas indexadas del 1 al 10 y del 1 al 20, respectivamente, entonces se reemplaza B por B + c1 − 3c2 hará que se vuelvan a numerar del 0 al 9 y 4 a 23, respectivamente. Aprovechando esta característica, algunos lenguajes (como FORTRAN 77) especifican que los índices de matriz comienzan en 1, como en la tradición matemática, mientras que otros lenguajes (como Fortran 90, Pascal y Algol) permiten que el usuario elija el valor mínimo para cada índice.

Vectores de drogas

La fórmula de direccionamiento está completamente definida por la dimensión d, la dirección base B y los incrementos c1, c2,..., ck. A menudo es útil empaquetar estos parámetros en un registro llamado descriptor o vector de zancada o vector de droga de la matriz. El tamaño de cada elemento y los valores mínimo y máximo permitidos para cada índice también pueden incluirse en el vector de dopaje. El vector dope es un controlador completo para la matriz y es una forma conveniente de pasar matrices como argumentos a los procedimientos. Muchas operaciones útiles de corte de matrices (como la selección de una submatriz, el intercambio de índices o la inversión de la dirección de los índices) se pueden realizar de manera muy eficiente mediante la manipulación del vector dope.

Diseños compactos

A menudo, los coeficientes se eligen de modo que los elementos ocupen un área de memoria contigua. Sin embargo, eso no es necesario. Incluso si los arreglos siempre se crean con elementos contiguos, algunas operaciones de división de arreglos pueden crear subarreglos no contiguos a partir de ellos.

Ilustración del orden de fila y columna-major

Hay dos diseños compactos sistemáticos para una matriz bidimensional. Por ejemplo, considere la matriz

${displaystyle A={begin{bmatrix}1 tendría2 ventaja34 coincidiendo67 afectados8 coincide9end{bmatrix}}$

En el diseño de orden de fila principal (adoptado por C para matrices declaradas estáticamente), los elementos de cada fila se almacenan en posiciones consecutivas y todos los elementos de una fila tienen una dirección más baja que cualquiera de los elementos de una fila consecutiva. fila:

1

2

3

4

5

6

7

8

9

En el orden de columna principal (tradicionalmente utilizado por Fortran), los elementos de cada columna son consecutivos en la memoria y todos los elementos de una columna tienen una dirección más baja que cualquiera de los elementos de una columna consecutiva:

1

4

7

2

5

8

3

6

9

Para arreglos con tres o más índices, "orden principal de fila" coloca en posiciones consecutivas dos elementos cualquiera cuyas tuplas de índice difieran solo en uno en el índice último. "Orden principal de columna" es análoga con respecto al índice primer.

En los sistemas que utilizan la memoria caché del procesador o la memoria virtual, escanear una matriz es mucho más rápido si los elementos sucesivos se almacenan en posiciones consecutivas en la memoria, en lugar de dispersarse escasamente. Muchos algoritmos que usan arreglos multidimensionales los escanearán en un orden predecible. Un programador (o un compilador sofisticado) puede usar esta información para elegir entre el diseño principal de filas o columnas para cada matriz. Por ejemplo, al calcular el producto A·B de dos matrices, sería mejor tener A almacenado en orden de fila principal, y B en orden de columna principal.

Redimensionamiento

Las matrices estáticas tienen un tamaño que se fija cuando se crean y, en consecuencia, no permiten que se inserten o eliminen elementos. Sin embargo, al asignar una nueva matriz y copiar en ella el contenido de la matriz anterior, es posible implementar efectivamente una versión dinámica de una matriz; ver matriz dinámica. Si esta operación se realiza con poca frecuencia, las inserciones al final de la matriz requieren solo un tiempo constante amortizado.

Algunas estructuras de datos de matriz no reasignan el almacenamiento, pero almacenan un recuento de la cantidad de elementos de la matriz en uso, denominado recuento o tamaño. Esto convierte efectivamente al arreglo en un arreglo dinámico con un tamaño o capacidad máxima fija; Las cadenas de Pascal son ejemplos de esto.

Fórmulas no lineales

Ocasionalmente se utilizan fórmulas más complicadas (no lineales). Para una matriz triangular bidimensional compacta, por ejemplo, la fórmula de direccionamiento es un polinomio de grado 2.

Eficiencia

Tanto almacenar como seleccionar toman (el peor caso determinista) un tiempo constante. Las matrices ocupan un espacio lineal (O(n)) en el número de elementos n que contienen.

En una matriz con tamaño de elemento k y en una máquina con un tamaño de línea de caché de B bytes, iterar a través de una matriz de n elementos requiere el mínimo de techo(La memoria caché nk/B) falla porque sus elementos ocupan ubicaciones de memoria contiguas. Esto es aproximadamente un factor de B/k mejor que la cantidad de errores de caché necesarios para acceder a n elementos en ubicaciones de memoria aleatorias. Como consecuencia, la iteración secuencial sobre una matriz es notablemente más rápida en la práctica que la iteración sobre muchas otras estructuras de datos, una propiedad llamada localidad de referencia (sin embargo, esto no significa que usar un hash perfecto o un hash trivial dentro de la misma matriz (local), no será aún más rápido, y se podrá lograr en tiempo constante). Las bibliotecas brindan funciones optimizadas de bajo nivel para copiar rangos de memoria (como memcpy) que se pueden usar para mover bloques contiguos de elementos de matriz significativamente más rápido de lo que se puede lograr a través del acceso a elementos individuales. La aceleración de dichas rutinas optimizadas varía según el tamaño, la arquitectura y la implementación del elemento del arreglo.

En cuanto a la memoria, las matrices son estructuras de datos compactas sin sobrecarga por elemento. Puede haber una sobrecarga por matriz (por ejemplo, para almacenar los límites del índice), pero esto depende del idioma. También puede suceder que los elementos almacenados en un arreglo requieran menos memoria que los mismos elementos almacenados en variables individuales, porque varios elementos del arreglo pueden almacenarse en una sola palabra; tales matrices a menudo se denominan matrices empaquetadas. Un caso extremo (pero de uso común) es la matriz de bits, donde cada bit representa un solo elemento. Por lo tanto, un solo octeto puede contener hasta 256 combinaciones diferentes de hasta 8 condiciones diferentes, en la forma más compacta.

Los accesos a matrices con patrones de acceso estáticamente predecibles son una fuente importante de paralelismo de datos.

Comparación con otras estructuras de datos

Los arreglos dinámicos o arreglos ampliables son similares a los arreglos, pero agregan la capacidad de insertar y eliminar elementos; agregar y eliminar al final es particularmente eficiente. Sin embargo, reservan almacenamiento adicional lineal (Θ(n)), mientras que las matrices no reservan almacenamiento adicional.

Los arreglos asociativos brindan un mecanismo para una funcionalidad similar a un arreglo sin grandes gastos generales de almacenamiento cuando los valores de índice son escasos. Por ejemplo, una matriz que contiene valores solo en los índices 1 y 2 mil millones puede beneficiarse del uso de dicha estructura. Las matrices asociativas especializadas con claves enteras incluyen los intentos de Patricia, las matrices de Judy y los árboles de van Emde Boas.

Los árboles equilibrados requieren un tiempo O(log n) para el acceso indexado, pero también permiten insertar o eliminar elementos en un tiempo O(log n), mientras que las matrices ampliables requieren un tiempo lineal. (Θ(n)) tiempo para insertar o eliminar elementos en una posición arbitraria.

Las listas vinculadas permiten la eliminación e inserción de tiempo constante en el medio, pero toman un tiempo lineal para el acceso indexado. Su uso de la memoria suele ser peor que el de las matrices, pero sigue siendo lineal.

Un vector de Iliffe es una alternativa a una estructura de matriz multidimensional. Utiliza una matriz unidimensional de referencias a matrices de una dimensión menos. Para dos dimensiones, en particular, esta estructura alternativa sería un vector de punteros a vectores, uno para cada fila (puntero en c o c++). Por lo tanto, se accedería a un elemento en la fila i y la columna j de una matriz A mediante doble indexación (A[ i][j] en notación típica). Esta estructura alternativa permite matrices irregulares, donde cada fila puede tener un tamaño diferente o, en general, donde el rango válido de cada índice depende de los valores de todos los índices anteriores. También ahorra una multiplicación (por el incremento de la dirección de la columna) reemplazándola por un cambio de bit (para indexar el vector de punteros de fila) y un acceso de memoria adicional (obteniendo la dirección de la fila), que puede valer la pena en algunas arquitecturas.

Dimensión

La dimensión de una matriz es el número de índices necesarios para seleccionar un elemento. Así, si el arreglo se ve como una función sobre un conjunto de posibles combinaciones de índices, es la dimensión del espacio del cual su dominio es un subconjunto discreto. Así, un arreglo unidimensional es una lista de datos, un arreglo bidimensional es un rectángulo de datos, un arreglo tridimensional un bloque de datos, etc.

Esto no debe confundirse con la dimensión del conjunto de todas las matrices con un dominio dado, es decir, el número de elementos en el arreglo. Por ejemplo, una matriz con 5 filas y 4 columnas es bidimensional, pero dichas matrices forman un espacio de 20 dimensiones. De manera similar, un vector tridimensional se puede representar mediante una matriz unidimensional de tamaño tres.