En informática , una matriz es una estructura de datos que consta de una colección de elementos ( valores o variables ), del mismo tamaño de memoria, cada uno identificado por al menos un índice o clave de matriz . Una matriz se almacena de manera que la posición de cada elemento se pueda calcular a partir de su tupla de índice mediante una fórmula matemática. [1] [2] [3] 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, se puede almacenar 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 tenga la dirección 2000 + ( i × 4). [4]
La dirección de memoria del primer elemento de una matriz se llama primera dirección, dirección base o dirección base.
Debido a que el concepto matemático de matriz se puede representar como una cuadrícula bidimensional, las matrices bidimensionales a veces también se denominan "matrices". En algunos casos, el término "vector" se utiliza en informática para referirse a una matriz, aunque las tuplas en lugar de los vectores son el equivalente matemáticamente más correcto. Las tablas suelen implementarse en forma de matrices, especialmente tablas de búsqueda ; La palabra "tabla" se utiliza a veces como sinónimo de matriz.
Las matrices se encuentran entre las estructuras de datos más antiguas e importantes y son utilizadas por casi todos los programas. 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 en muchos dispositivos de almacenamiento externos , la memoria es una matriz unidimensional de palabras, cuyos índices son sus direcciones. Los procesadores , especialmente los procesadores vectoriales , suelen estar optimizados 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 muchos elementos arbitrarios de una matriz. Por esa razón, se requiere que los elementos de una estructura de datos de matriz tengan el mismo tamaño y utilicen 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, [3] [5] pero no siempre, [2] son fijas mientras la matriz está en uso.
El término "matriz" también puede referirse a un tipo de datos de matriz , un 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 lenguajes pueden implementarse mediante tablas hash , listas enlazadas , árboles de búsqueda u otras estructuras de datos.
El término también se utiliza, especialmente en la descripción de algoritmos , para referirse a 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 las matrices.
Las primeras computadoras digitales utilizaron programación en lenguaje de máquina para configurar y acceder a estructuras de matrices para tablas de datos, cálculos vectoriales y matriciales, y para muchos otros propósitos. John von Neumann escribió el primer programa de clasificación de matrices ( merge sort ) en 1945, durante la construcción de la primera computadora con programas almacenados . [6] La indexación de matrices se realizaba originalmente mediante código automodificado y luego utilizando registros de índice y direccionamiento indirecto . Algunos mainframes diseñados en la década de 1960, como el Burroughs B5000 y sus sucesores, utilizaban segmentación de memoria para realizar comprobaciones de límites de índice en el hardware. [7]
Los lenguajes ensambladores generalmente no tienen soporte especial para matrices, aparte del 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), admitían matrices multidimensionales, al igual que C (1972). En C++ (1983), existen plantillas de clases para matrices multidimensionales cuya dimensión se fija en tiempo de ejecución [3] [5] así como para matrices flexibles en tiempo de ejecución. [2]
Los arrays se utilizan para implementar vectores y matrices matemáticos , así como otros tipos de tablas rectangulares. Muchas bases de datos , pequeñas y grandes, constan (o incluyen) matrices 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 matrices de otras estructuras de datos son frecuentemente simples y eficientes en cuanto a espacio ( estructuras de datos implícitas ), requiriendo poca sobrecarga de espacio , pero pueden tener poca complejidad espacial, particularmente cuando se modifican, en comparación con las estructuras de datos basadas en árboles (compárese una matriz ordenada 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 dentro del programa , particularmente la asignación de grupo de memoria . Históricamente, esta ha sido a veces la única forma de asignar "memoria dinámica" de forma portátil.
Las matrices se pueden utilizar para determinar el flujo de control parcial o completo en programas, como una alternativa compacta a IFdeclaraciones múltiples (de otro modo repetitivas). 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 sentencias SWITCH ) que dirigen la ruta de ejecución.
Cuando los objetos de datos se almacenan en una matriz, los objetos individuales se seleccionan mediante un índice que suele ser un número entero escalar no negativo . Los índices también se denominan subíndices. Un índice asigna el valor de la matriz a un objeto almacenado.
Hay tres formas en que se pueden indexar los elementos de una matriz:
El uso de indexación de base cero es la elecció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.
Las matrices pueden tener múltiples dimensiones, por lo que no es raro acceder a una matriz utilizando múltiples índices. Por ejemplo, una matriz bidimensional Acon 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 tanto, se utilizan dos índices para una matriz bidimensional, tres para una matriz tridimensional y n para una matriz de n dimensiones.
El número 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 una fórmula "lineal" en los índices.
Una matriz unidimensional (o matriz unidimensional) es un tipo de matriz lineal. El acceso a sus elementos implica un único 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 números enteros. Aquí, la matriz puede almacenar diez elementos de tipo int. Esta matriz tiene índices que van del cero al 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 llamada 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 matriz siempre comienzan en 0; y muchos programadores llamarán a ese elemento " cero " 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 + 30 c , 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.
Para una matriz multidimensional, el elemento con índices i , j tendría dirección B + c · i + d · j , donde los coeficientes cyd son los incrementos de dirección de fila y columna , respectivamente.
De manera más general, en una matriz k -dimensional, la dirección de un elemento con índices i 1 , i 2 , ..., i k es
Por ejemplo: int a[2][3];
Esto significa que la matriz a tiene 2 filas y 3 columnas, y la matriz es de tipo entero. Aquí podemos almacenar 6 elementos. Se almacenarán linealmente, pero comenzando desde la primera fila de forma lineal y luego continuando con la segunda fila. La matriz anterior se almacenará como 11 , a 12 , a 13 , a 21 , a 22 , a 23 .
Esta fórmula requiere solo k multiplicaciones y k sumas, para cualquier matriz que quepa en la memoria. Además, si algún coeficiente es una potencia fija de 2, la multiplicación se puede sustituir por un desplazamiento de bits .
Los coeficientes c k deben elegirse de modo que cada tupla de índice válida se asigne a la dirección de un elemento distinto.
Si el valor mínimo legal 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, reemplazar B por B + c 1 − 3 c 2 hará que se renumeren del 0 al 9 y del 4 al 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 al usuario elegir el valor mínimo para cada índice.
La fórmula de direccionamiento está completamente definida por la dimensión d , la dirección base B y los incrementos c 1 , c 2 , ..., c k . A menudo resulta útil empaquetar estos parámetros en un registro llamado descriptor de la matriz o vector de zancada o vector de dope . [2] [3] 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 dope. El vector dope es un identificador 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 seleccionar una submatriz, intercambiar índices o invertir la dirección de los índices) se pueden realizar de manera muy eficiente manipulando el vector dope. [2]
A menudo los coeficientes se eligen de modo que los elementos ocupen un área contigua de la memoria. Sin embargo, eso no es necesario. Incluso si las matrices siempre se crean con elementos contiguos, algunas operaciones de división de matrices pueden crear submatrices no contiguas a partir de ellos.
Hay dos diseños compactos sistemáticos para una matriz bidimensional. Por ejemplo, considere la matriz
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:
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:
Para matrices con tres o más índices, el "orden principal de filas" coloca en posiciones consecutivas dos elementos cualesquiera cuyas tuplas de índice difieren sólo en uno en el último índice. El "orden principal de columnas" es análogo con respecto al primer índice.
En sistemas que utilizan caché de procesador o 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. A esto se le conoce como localidad espacial, que es un tipo de localidad de referencia . Muchos algoritmos que utilizan matrices multidimensionales las escanearán en un orden predecible. Un programador (o un compilador sofisticado) puede usar esta información para elegir entre el diseño de fila o columna principal para cada matriz. Por ejemplo, al calcular el producto A · B de dos matrices, sería mejor tener A almacenado en el orden principal de las filas y B en el orden principal de las columnas.
Los arreglos estáticos tienen un tamaño que se fija cuando se crean y en consecuencia no permiten insertar ni quitar elementos. Sin embargo, al asignar una nueva matriz y copiarle el contenido de la matriz anterior, es posible implementar de manera efectiva 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 solo requieren un tiempo constante amortizado.
Algunas estructuras de datos de matriz no reasignan el almacenamiento, pero almacenan un recuento del número de elementos de la matriz en uso, llamado recuento o tamaño. Esto efectivamente convierte a la matriz en una matriz dinámica con un tamaño o capacidad máximo fijo; Las cadenas Pascal son ejemplos de esto.
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.
Tanto el almacenamiento como la selección toman (peor caso determinista) un tiempo constante . Las matrices toman un espacio lineal ( O ( n )) en el número de elementos n que contienen.
En una matriz con un tamaño de elemento k y en una máquina con un tamaño de línea de caché de B bytes, la iteración a través de una matriz de n elementos requiere el mínimo de errores máximos de caché ( nk /B), porque sus elementos ocupan ubicaciones de memoria contiguas. Esto es aproximadamente un factor de B/ k mejor que el número 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 (esto no significa, sin embargo, 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 un tiempo constante ). Las bibliotecas proporcionan 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 mediante el 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 de la matriz.
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 límites de índice), pero esto depende del idioma. También puede suceder que los elementos almacenados en un array requieran menos memoria que los mismos elementos almacenados en variables individuales, debido a que se pueden almacenar varios elementos del array en una sola palabra ; Estas matrices a menudo se denominan matrices empaquetadas . Un caso extremo (pero comúnmente utilizado) es la matriz de bits , donde cada bit representa un único 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 .
Las matrices dinámicas o las matrices ampliables son similares a las matrices, 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 los arreglos no reservan almacenamiento adicional.
Las matrices asociativas proporcionan un mecanismo para una funcionalidad similar a una matriz sin grandes gastos de almacenamiento cuando los valores del índice son escasos. Por ejemplo, una matriz que contiene valores sólo en los índices 1 y 2 mil millones puede beneficiarse del uso de dicha estructura. Los arreglos asociativos especializados con claves enteras incluyen los intentos de Patricia , los arreglos de Judy y los árboles de van Emde Boas .
Los árboles equilibrados requieren tiempo O(log n ) para el acceso indexado, pero también permiten insertar o eliminar elementos en tiempo O(log n ), [13] mientras que los arreglos cultivables requieren tiempo lineal (Θ( n )) para insertar o eliminar elementos en un tiempo posición arbitraria.
Las listas enlazadas permiten una eliminación e inserción en el medio en un tiempo constante, pero requieren un tiempo lineal para el acceso indexado. Su uso de 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 indexación doble ( 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 desplazamiento de bits (para indexar el vector de los punteros de fila) y un acceso a memoria adicional (obteniendo la dirección de la fila), lo que puede valer la pena en algunas arquitecturas.
La dimensión de una matriz es el número de índices necesarios para seleccionar un elemento. Por lo tanto, si la matriz se considera una función sobre un conjunto de posibles combinaciones de índices, es la dimensión del espacio cuyo dominio es un subconjunto discreto. Así, una matriz unidimensional es una lista de datos, una matriz bidimensional es un rectángulo de datos, [14] una matriz tridimensional es un bloque de datos, etc.
Esto no debe confundirse con la dimensión del conjunto de todas las matrices con un dominio determinado, es decir, el número de elementos de la matriz. 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.
{{cite conference}}: Mantenimiento CS1: estado de la URL ( enlace )En la mayoría de los lenguajes informáticos, el índice de matriz (conteo) comienza desde 0, no desde 1. El índice del primer elemento de la matriz es 0, el índice del segundo elemento de la matriz es 1, y así sucesivamente.
En la serie de nombres a continuación puede ver índices y valores.
Estructuras/matrices de datos en Wikilibros