Estructura de datos de matriz - Array data structure

En informática , una estructura de datos de matriz , o simplemente una matriz , es una estructura de datos que consta de una colección de elementos ( valores o variables ), 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. El tipo más simple de estructura de datos es una matriz lineal, también llamada matriz unidimensional.

Por ejemplo, una matriz de 10 de 32 bits variables enteras (4 bytes), con índices de 0 a 9, se puede almacenar como 10 palabras en 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).

La dirección de memoria del primer elemento de una matriz se denomina primera dirección, dirección básica 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 utiliza en computación para referirse a una matriz, aunque las tuplas en lugar de los vectores son el equivalente matemáticamente correcto. Las tablas a menudo se implementan 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 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 una matriz unidimensional de palabras, cuyos índices son sus direcciones. Los procesadores , especialmente los procesadores vectoriales , a menudo se optimizan para operaciones de arreglos.

Las matrices son útiles principalmente porque los índices de 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, 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, pero no siempre, son fijas mientras se usa la matriz.

El término matriz se usa a menudo para referirse al 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 significar matriz asociativa o "matriz abstracta", un modelo teórico de la ciencia de la computación (un tipo de datos abstracto o ADT) destinado a capturar las propiedades esenciales de las matrices.

Historia

Las primeras computadoras digitales usaban programación en lenguaje de máquina para configurar y acceder a estructuras de matriz 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 (clasificación por fusión ) en 1945, durante la construcción de la primera computadora con programa almacenado . ^{pag. 159 La} indexación de matrices se realizaba originalmente mediante código de modificación automática y , posteriormente, 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 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 matrices multidimensionales cuya dimensión se fija en tiempo de ejecución, así como para matrices flexibles en tiempo de ejecución.

Aplicaciones

Las matrices 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 de (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 el espacio ( estructuras de datos implícitas ), requiriendo poca sobrecarga de espacio , pero pueden tener poca complejidad de espacio, particularmente cuando se modifican, en comparación con estructuras de datos basadas en árboles (compare 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 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" de forma portátil.

Las matrices se pueden utilizar para determinar el flujo de control parcial o completo en los programas, como una alternativa compacta a las IFsentencias múltiples (de otra manera 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 de acuerdo con 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 generalmente es un 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 de indexar los elementos de una matriz:

0 ( indexación de base cero )

El primer elemento de la matriz está indexado por un subíndice de 0.

1 ( indexación basada en uno )

El primer elemento de la matriz está indexado por un subíndice de 1.

n ( indexación basada en n )

El índice base de una matriz se puede elegir libremente. Por lo general, los idiomas de programación que permite la indexación basada en N también permiten los valores negativos del índice y otros escalares tipos de datos como enumeraciones , o caracteres se pueden usar como un índice de matriz.

El uso de la 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 yn para una matriz n- dimensional.

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

En 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.

Matrices unidimensionales

Una matriz unidimensional (o matriz de una sola dimensión) 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 enteros. Aquí, la matriz puede almacenar diez elementos de tipo int. Esta matriz tiene índices 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 el índice i se encuentra en la dirección de B + c × i , donde B es un fijo dirección de base y c una constante fija, a veces llamado el incremento de dirección o la 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, uno puede elegir el índice del primer elemento por una elección apropiada de la dirección base B . Por ejemplo, si la matriz tiene cinco elementos, indexados de 1 a 5, y la dirección base B se reemplaza por B + 30 c , entonces los índices de esos mismos elementos serán de 31 a 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 los índices i , j tendría dirección B + c · i + d · j , donde los coeficientes c y d son las filas y incrementos de dirección de columna , respectivamente.

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

B + do ₁ · yo ₁ + do ₂ · yo ₂ +… + do _k · yo _k .

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 que se almacenarán linealmente pero comenzando desde la primera fila lineal y luego continuando con la segunda fila. La matriz anterior se almacenará como ₁₁ , ₁₂ , ₁₃ , ₂₁ , ₂₂ , ₂₃ .

Esta fórmula requiere solo k multiplicaciones y k sumas, para cualquier matriz que pueda caber en la memoria. Además, si cualquier coeficiente es una potencia fija de 2, la multiplicación se puede reemplazar por desplazamiento de bits .

Los coeficientes c _k deben elegirse de modo que cada tupla de índice válida se corresponda con 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 pueden ser cambiados por el cambio de la dirección de base B . Así, si una matriz de dos dimensiones tiene filas y columnas indexadas de 1 a 10 y 1 a 20, respectivamente, entonces la sustitución de B por B + C ₁ - 3 c ₂ hará que se numerarán de 0 a 9 y 4 a través de 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.

Vectores de dope

La fórmula de direccionamiento está completamente definida por la dimensión d , la dirección base B y los incrementos c ₁ , c ₂ , ..., c _k . A menudo es útil empaquetar estos parámetros en un registro llamado descriptor de la matriz o vector de zancada o vector de droga . El tamaño de cada elemento y los valores mínimos y máximos permitidos para cada índice también pueden incluirse en el vector de droga. El vector dope es un identificador completo para la matriz y es una forma conveniente de pasar matrices como argumentos a 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.

Diseños compactos

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

Ilustración del orden principal de filas y columnas

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

${\ displaystyle A = {\ begin {bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \ end {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:

1

2

3

4

5

6

7

8

9

En 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 matrices con tres o más índices, el "orden mayor de fila" coloca en posiciones consecutivas dos elementos cualesquiera cuyas tuplas de índice difieran sólo en uno en el último índice. El "orden principal de la columna" es análogo con respecto al primer índice.

En los sistemas que utilizan la memoria caché del procesador o la memoria virtual , la exploración de una matriz es mucho más rápida si los elementos sucesivos se almacenan en posiciones consecutivas en la memoria, en lugar de estar dispersos. Muchos algoritmos que utilizan matrices 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 fila o columna para cada matriz. Por ejemplo, al calcular el producto A · B de dos matrices, sería mejor tener A almacenado en orden de fila mayor y B en orden de columna mayor.

Cambiar el tamaño

Las matrices estáticas tienen un tamaño que se fija cuando se crean y, en consecuencia, no permiten insertar o eliminar 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áximos fijos; 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 el almacenamiento como la selección toman (en el peor de los casos deterministas) un tiempo constante . Las matrices ocupan espacio lineal ( O ( n )) en el número de elementos n que contienen.

En una matriz con tamaño de elemento ky 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 fallas de caché de techo ( nk / B), 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 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 trivial dentro de la misma matriz (local) , no será aún más rápido y alcanzable en un tiempo constante ). Las bibliotecas proporcionan instalaciones 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 tales rutinas optimizadas varía según el tamaño del elemento de la matriz, la arquitectura y la implementación.

En cuanto a la memoria, las matrices son estructuras de datos compactas sin sobrecarga por elemento . Puede haber una sobrecarga por arreglo (por ejemplo, para almacenar límites de índice) pero esto depende del idioma. También puede suceder que los elementos almacenados en una matriz requieran menos memoria que los mismos elementos almacenados en variables individuales, porque varios elementos de la matriz se pueden almacenar 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 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 predecibles estáticamente son una fuente importante de paralelismo de datos .

Comparación con otras estructuras de datos

Las matrices dinámicas o las matrices que se pueden crecer 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 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 intentos de Patricia , matrices de Judy y á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 ), mientras que las matrices que pueden crecer requieren tiempo lineal (Θ ( n )) para insertar o eliminar elementos en una posición arbitraria.

Las listas enlazadas permiten la eliminación e inserción de tiempo constante en el medio, 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 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 una indexación doble ( A [ i ] [ j ] en notación típica). Esta estructura alternativa permite matrices dentadas , 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 guarda 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 punteros de fila) y un acceso a memoria adicional (obteniendo la dirección de la fila), lo que puede ser útil en algunas arquitecturas.

Dimensión

La dimensión de una matriz es el número de índices necesarios para seleccionar un elemento. Por lo tanto, si la matriz se ve como una función en un conjunto de posibles combinaciones de índices, es la dimensión del espacio del cual su dominio es un subconjunto discreto. Así, una matriz unidimensional es una lista de datos, una matriz bidimensional es un rectángulo de datos, 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 dado, es decir, el número de elementos de la matriz. Por ejemplo, una matriz con 5 filas y 4 columnas es bidimensional, pero tales matrices forman un espacio de 20 dimensiones. De manera similar, un vector tridimensional se puede representar mediante una matriz unidimensional de tamaño tres.

Ver también

Referencias