Matriz (estructura de datos)

En informática , un array es una estructura de datos que consiste en una colección de elementos ( valores o variables ) del mismo tamaño de memoria, cada uno identificado por al menos un índice o clave del array , cuya colección puede ser una tupla , conocida como tupla de índices. En general, un array es una colección mutable y lineal de elementos del mismo tipo de datos. Un array se almacena de tal manera que la posición (dirección de memoria) de cada elemento se puede calcular a partir de su tupla de índices mediante una fórmula matemática. ^{[ 1 ] [ 2 ] [ 3 ]} El tipo más simple de estructura de datos es un array lineal, también llamado array 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) de modo 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 de fundación.

Dado que el concepto matemático de matriz puede representarse como una cuadrícula bidimensional, las matrices bidimensionales también se denominan a veces «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 las tablas de búsqueda ; la palabra «tabla» se utiliza a veces como sinónimo de matriz.

Los arreglos son una de las estructuras de datos más antiguas e importantes, y se utilizan en casi todos los programas. También se emplean para implementar muchas otras estructuras de datos, como listas y cadenas . Aprovechan eficazmente la lógica de direccionamiento de las computadoras. En la mayoría de las computadoras modernas y en muchos dispositivos de almacenamiento externo , la memoria es un arreglo unidimensional de palabras, cuyos índices son sus direcciones. Los procesadores , especialmente los procesadores vectoriales , suelen estar optimizados para operaciones con arreglos.

Los arreglos 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 instrucción iterativa procese una cantidad arbitraria de elementos de un arreglo. Por esa razón, los elementos de una estructura de datos de arreglo deben tener el mismo tamaño y usar la misma representación de datos. El conjunto de tuplas de índices válidas y las direcciones de los elementos (y por lo tanto la fórmula de direccionamiento de elementos) suelen ser, ^{[ 3 ] [ 5 ]} pero no siempre, ^{[ 2 ]} fijos mientras el arreglo está en uso.

El término "array" también puede referirse a un tipo de dato array , un tipo de dato que ofrecen la mayoría de los lenguajes de programación de alto nivel y que consiste en una colección de valores o variables que se pueden seleccionar mediante uno o más índices calculados en tiempo de ejecución. Los tipos array suelen implementarse mediante estructuras array; 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 una matriz asociativa o "matriz abstracta", un modelo teórico de la informática (un tipo de dato abstracto o TDA) destinado a capturar las propiedades esenciales de las matrices.

Las primeras computadoras digitales utilizaban programación en lenguaje 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 ordenación de matrices ( ordenación por fusión ) en 1945, durante la construcción de la primera computadora de programa almacenado . ^{[ 6 ]} La indexación de matrices se realizaba originalmente mediante código automodificable , y posteriormente mediante registros de índice y direccionamiento indirecto . Algunas computadoras centrales diseñadas en la década de 1960, como la Burroughs B5000 y sus sucesoras, utilizaban segmentación de memoria para realizar comprobaciones de límites de índice en hardware. ^{[ 7 ]}

Los lenguajes ensambladores generalmente no tienen soporte especial para arreglos, más allá 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), tenían soporte para arreglos multidimensionales, al igual que C (1972). En C++ (1983), existen plantillas de clase para arreglos multidimensionales cuya dimensión es fija en tiempo de ejecución ^{[ 3 ] [ 5 ]} , así como para arreglos flexibles en tiempo de ejecución. ^{[ 2 ]}

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

Los arreglos se utilizan para implementar otras estructuras de datos, como listas, montículos , tablas hash , deques , colas , pilas , cadenas y listas virtuales. Las implementaciones basadas en arreglos de otras estructuras de datos suelen ser simples y eficientes en cuanto a espacio ( estructuras de datos implícitas ), requiriendo poco espacio adicional , pero pueden tener una complejidad espacial deficiente, especialmente al modificarlas, en comparación con las estructuras de datos basadas en árboles (compárese un arreglo ordenado con un árbol de búsqueda ).

En ocasiones, se utilizan uno o más arreglos grandes para emular la asignación dinámica de memoria dentro del programa , en particular la asignación de memoria compartida . Históricamente, esta ha sido a veces la única forma de asignar "memoria dinámica" de manera portable.

Los arreglos se pueden usar para determinar el flujo de control parcial o completo en los programas, como una alternativa compacta a IFlas instrucciones múltiples (que de otro modo serían repetitivas). En este contexto, se conocen como tablas de control y se usan junto con un intérprete diseñado específicamente para ello, cuyo flujo de control se modifica según los valores que contiene el arreglo. El arreglo puede contener punteros a subrutinas (o números de subrutinas relativas sobre las que se pueden actuar mediante instrucciones SWITCH ) que dirigen la ruta de ejecución del programa.

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

Existen tres formas de indexar los elementos de un array:

0 ( indexación basada en cero )

El primer elemento del array se indexa mediante el subíndice 0. ^{[ 8 ]}

1 ( indexación basada en uno )

El primer elemento del array se indexa mediante el subíndice 1.

n ( indexación basada en n )

El índice base de un array se puede elegir libremente. Por lo general, los lenguajes de programación que permiten la indexación basada en n también permiten valores de índice negativos y otros tipos de datos escalares , como enumeraciones o caracteres, que pueden usarse como índice de un array.

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 simplifica la implementación, ya que el subíndice se refiere a un desplazamiento desde la posición inicial de un array, de modo que el primer elemento tiene un desplazamiento de cero.

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

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

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

Matrices unidimensionales

Una matriz unidimensional (o matriz de una sola dimensión) es un tipo de matriz lineal. Para acceder a sus elementos se utiliza un único subíndice que puede representar un índice de fila o de columna.

Como ejemplo, consideremos la declaración en C que declara un arreglo unidimensional llamado de diez enteros. Aquí, el arreglo puede almacenar diez elementos de tipo . Este arreglo tiene índices que van desde cero hasta nueve. Por ejemplo, las expresiones y son el primer y último elemento, respectivamente.inta[10];ainta[0]a[9]

Para un vector con direccionamiento lineal, el elemento con índice i se encuentra 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 paso .

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

Sin embargo, se puede elegir el índice del primer elemento seleccionando adecuadamente la dirección base B. Por ejemplo, si el arreglo 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.

matrices 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 incrementos de dirección de fila y columna , respectivamente.

De forma más general, en una matriz k- dimensional, la dirección de un elemento con índices i ₁ , i ₂ , ..., i _k es

B + c ₁ · i ₁ + c ₂ · i ₂ + … + c _k · i _k .

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

Esto significa que el array a tiene 2 filas y 3 columnas, y es de tipo entero. Aquí podemos almacenar 6 elementos que se almacenarán linealmente, comenzando por la primera fila y continuando con la segunda. El array anterior se almacenará como a ₁₁ , a ₁₂ , a ₁₃ , a ₂₁ , a ₂₂ , a ₂₃ .

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 reemplazar por un desplazamiento de bits .

Los coeficientes c _k deben elegirse de manera que cada tupla de índice válida se corresponda con 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. Al igual que en el caso unidimensional, los índices de los elementos pueden cambiarse modificando 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 reemplazar B por B + c ₁ − 3 c ₂ 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 la 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.

Diseños compactos

A menudo, los coeficientes se eligen de forma que los elementos ocupen un área contigua de memoria. Sin embargo, esto no es necesario. Aunque los arreglos siempre se crean con elementos contiguos, algunas operaciones de segmentación de arreglos pueden generar subarreglos no contiguos a partir de ellos.

Existen dos disposiciones compactas sistemáticas para una matriz bidimensional. Por ejemplo, consideremos la matriz

${\displaystyle A={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}$

En la disposición de orden por filas (adoptada por C para arreglos declarados estáticamente), los elementos de cada fila se almacenan en posiciones consecutivas y todos los elementos de una fila tienen una dirección menor que cualquiera de los elementos de una fila consecutiva:

En el orden por columnas (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 inferior a la de cualquiera de los elementos de una columna consecutiva:

Para matrices con tres o más índices, el orden "por filas" coloca en posiciones consecutivas cualquier par de elementos cuyas tuplas de índices solo difieren en uno en el último índice. El orden "por columnas" es análogo con respecto al primer índice.

En sistemas que utilizan memoria caché del procesador o memoria virtual , el escaneo de una matriz es mucho más rápido si los elementos sucesivos se almacenan en posiciones consecutivas en la memoria, en lugar de estar dispersos. Esto se conoce como localidad espacial, que es un tipo de localidad de referencia . Muchos algoritmos que utilizan matrices multidimensionales las escanean en un orden predecible. Un programador (o un compilador avanzado) puede usar esta información para elegir entre una disposición por filas o por columnas para cada matriz. Por ejemplo, al calcular el producto A · B de dos matrices, sería mejor tener A almacenada en orden de filas y B en orden de columnas.

Tanto almacenar como seleccionar toman un tiempo constante (en el peor de los casos determinista) . Los arreglos toman un espacio lineal ( O ( n )) en función del número de elementos n que contienen.

En un array 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 un array de n elementos requiere un mínimo de ceiling( nk /B) fallos de caché, porque sus elementos ocupan ubicaciones de memoria contiguas. Esto es aproximadamente un factor de B/ k mejor que el número de fallos de caché necesarios para acceder a n elementos en ubicaciones de memoria aleatorias. Como consecuencia, la iteración secuencial sobre un array 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 del mismo array (local) no sea aún más rápido, y alcanzable en 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 del array significativamente más rápido que 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 de los elementos del array, la arquitectura y la implementación.

En términos de memoria, los arreglos son estructuras de datos compactas sin sobrecarga por elemento . Puede haber una sobrecarga por arreglo (por ejemplo, para almacenar los límites de los índices), pero esto depende del lenguaje. También puede ocurrir que los elementos almacenados en un arreglo requieran menos memoria que los mismos elementos almacenados en variables individuales, ya que varios elementos de un arreglo pueden almacenarse en una sola palabra ; estos arreglos se denominan a menudo arreglos empaquetados . Un caso extremo (pero de uso común) es el arreglo de bits , donde cada bit representa un único elemento. Un solo octeto puede, por lo tanto, contener hasta 256 combinaciones diferentes de hasta 8 condiciones distintas, en su 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 de tamaño variable son similares a los arreglos, pero permiten insertar y eliminar elementos; agregar y eliminar al final resulta especialmente eficiente. Sin embargo, reservan un espacio de almacenamiento adicional lineal ( Θ ( n )), mientras que los arreglos no lo hacen.

Los arreglos asociativos proporcionan un mecanismo para lograr una funcionalidad similar a la de los arreglos tradicionales sin la gran sobrecarga de almacenamiento cuando los valores de los índices son dispersos. Por ejemplo, un arreglo que contiene valores solo en los índices 1 y 2 mil millones puede beneficiarse del uso de dicha estructura. Entre los arreglos asociativos especializados con claves enteras se incluyen los árboles de Patricia , los arreglos de Judy y los árboles de van Emde-Boas .

Los árboles equilibrados requieren un tiempo de O(log n ) para el acceso indexado, pero también permiten insertar o eliminar elementos en un tiempo de O(log n ), ^{[ 11 ]} mientras que los arreglos de crecimiento requieren un tiempo lineal (Θ( n )) para insertar o eliminar elementos en una posición arbitraria.

Las listas enlazadas permiten la eliminación e inserción de elementos en tiempo constante, pero el acceso indexado requiere tiempo lineal. Su consumo de memoria suele ser mayor que el de los arreglos, aunque 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 por cada fila (puntero en C o C++). Así, 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 la 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 precedentes. También ahorra una multiplicación (por el incremento de la dirección de columna) al reemplazarla por un desplazamiento de bits (para indexar el vector de punteros de fila) y un acceso a memoria adicional (obtener la dirección de fila), lo que puede ser útil 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 como una función de 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, ^{[ 12 ]} una matriz 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 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 puede representarse mediante una matriz unidimensional de tamaño tres.

• Estructuras/matrices de datos en Wikilibros