Tipo de datos de matriz - Array data type

En informática , un tipo de matriz es un tipo de datos que representa una colección de elementos ( valores o variables ), cada uno seleccionado por uno o más índices (claves de identificación) que se pueden calcular en tiempo de ejecución durante la ejecución del programa. Colección un Tal generalmente se llama una variable de matriz , valor de la matriz , o simplemente matriz . Por analogía con los conceptos matemáticos vector y matriz , los tipos de matriz con uno y dos índices a menudo se denominan tipo de vector y tipo de matriz , respectivamente. De manera más general, un tipo de matriz multidimensional puede denominarse tipo tensor .

El soporte de lenguaje para tipos de matriz puede incluir ciertos tipos de datos de matriz incorporados , algunas construcciones sintácticas (constructores de tipo de matriz ) que el programador puede usar para definir tales tipos y declarar variables de matriz, y notación especial para indexar elementos de matriz. Por ejemplo, en el lenguaje de programación Pascal , la declaración type MyTable = array [1..4,1..2] of integerdefine un nuevo tipo de datos de matriz llamado MyTable. var A: MyTableLuego, la declaración define una variable Ade ese tipo, que es un agregado de ocho elementos, cada uno de los cuales es una variable entera identificada por dos índices. En el programa Pascal, esos elementos se denotan A[1,1], A[1,2], A[2,1], ..., A[4,2]. Los tipos de matrices especiales a menudo se definen mediante las bibliotecas estándar del lenguaje .

Las listas dinámicas también son más comunes y más fáciles de implementar que las matrices dinámicas . Los tipos de matriz se distinguen de los tipos de registro principalmente porque permiten que los índices de elementos se calculen en tiempo de ejecución , como en la asignación de Pascal A[I,J] := A[N-I,2*J]. Entre otras cosas, esta característica permite que una sola declaración iterativa procese arbitrariamente muchos elementos de una variable de matriz.

En contextos más teóricos, especialmente en la teoría de tipos y en la descripción de algoritmos abstractos , los términos "matriz" y "tipo de matriz" a veces se refieren a un tipo de datos abstracto (ADT) también llamado matriz abstracta o pueden referirse a una matriz asociativa , un modelo matemático con las operaciones básicas y el comportamiento de un tipo de matriz típico en la mayoría de los lenguajes; básicamente, una colección de elementos que se seleccionan mediante índices calculados en tiempo de ejecución.

Dependiendo del idioma, los tipos de arreglos pueden superponerse (o identificarse con) otros tipos de datos que describen agregados de valores, como listas y cadenas . Los tipos de matriz a menudo se implementan mediante estructuras de datos de matriz , pero a veces por otros medios, como tablas hash , listas vinculadas o árboles de búsqueda .

Historia

El lenguaje de programación de Heinz Rutishauser Superplan (1949-1951) incluía matrices multidimensionales. Sin embargo, Rutishauser, aunque describió cómo se debería construir un compilador para su lenguaje, no implementó uno.

Los lenguajes ensambladores y los lenguajes de bajo nivel como BCPL generalmente no tienen soporte sintáctico para arreglos.

Debido a la importancia de las estructuras de arreglos para el cálculo eficiente, los primeros lenguajes de programación de alto nivel, incluidos FORTRAN (1957), COBOL (1960) y Algol 60 (1960), proporcionaron soporte para arreglos multidimensionales.

Matrices abstractas

Una estructura de datos de matriz se puede modelar matemáticamente como una estructura de datos abstracta (una matriz abstracta ) con dos operaciones

obtener ( A , I ): los datos almacenados en el elemento de la matriz A cuyos índices son el número entero tupla I .

conjunto ( A , I , V ): la matriz que los resultados estableciendo el valor de ese elemento a V .

Estas operaciones son necesarias para satisfacer los axiomas

obtener ( establecer ( A , I , V ), I ) = V

obtener ( establecer ( A , I , V ), J ) = obtener ( A , J ) si I ≠ J

para cualquier estado de matriz A , cualquier valor V y cualquier tupla I , J para las que se definen las operaciones.

El primer axioma significa que cada elemento se comporta como una variable. El segundo axioma significa que los elementos con índices distintos se comportan como variables disjuntas , de modo que almacenar un valor en un elemento no afecta el valor de cualquier otro elemento.

Estos axiomas no imponen restricciones al conjunto de tuplas de índice válidas I , por lo que este modelo abstracto se puede utilizar para matrices triangulares y otras matrices de formas extrañas.

Implementaciones

Para implementar de manera efectiva variables de tipos tales como estructuras de matriz (con indexación realizada por aritmética de punteros ), muchos lenguajes restringen los índices a tipos de datos enteros (u otros tipos que pueden interpretarse como enteros, como bytes y tipos enumerados ), y requieren que todos los elementos tengan el mismo tipo de datos y tamaño de almacenamiento. La mayoría de esos lenguajes también restringen cada índice a un intervalo finito de enteros, que permanece fijo durante la vida útil de la variable de matriz. En algunos lenguajes compilados , de hecho, es posible que los rangos de índices deban conocerse en el momento de la compilación .

Por otro lado, algunos lenguajes de programación proporcionan tipos de matrices más liberales, que permiten la indexación por valores arbitrarios, como números de punto flotante , cadenas , objetos , referencias , etc. Dichos valores de índice no pueden restringirse a un intervalo, mucho menos a un intervalo fijo. Por lo tanto, estos lenguajes suelen permitir la creación de nuevos elementos arbitrarios en cualquier momento. Esta elección excluye la implementación de tipos de arreglos como estructuras de datos de arreglos. Es decir, esos lenguajes usan una sintaxis similar a una matriz para implementar una semántica de matriz asociativa más general y, por lo tanto, deben implementarse mediante una tabla hash o alguna otra estructura de datos de búsqueda .

Ayuda de idioma

Matrices multidimensionales

El número de índices necesarios para especificar un elemento se denomina dimensión , dimensionalidad o rango del tipo de matriz. (Esta nomenclatura entra en conflicto con el concepto de dimensión en álgebra lineal, donde es el número de elementos. Por lo tanto, una matriz de números con 5 filas y 4 columnas, por lo tanto 20 elementos, se dice que tiene dimensión 2 en contextos informáticos, pero representa una matriz con dimensión 4 por 5 o 20. Además, el significado de "rango" en ciencias de la computación es similar a su significado en álgebra tensorial, pero no al concepto de rango de una matriz en álgebra lineal ).

Muchos lenguajes solo admiten matrices unidimensionales. En esos lenguajes, una matriz multidimensional se representa típicamente mediante un vector Iliffe , una matriz unidimensional de referencias a matrices de una dimensión menos. Una matriz bidimensional, en particular, se implementaría como un vector de punteros a sus filas. Por lo tanto , se accedería a un elemento en la fila i y la columna j de una matriz A mediante una doble indexación ( A [ i ] [ j ] en notación típica). Esta forma de emular matrices multidimensionales permite la creación de 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.

Esta representación para matrices multidimensionales es bastante frecuente en el software C y C ++. Sin embargo, C y C ++ utilizarán una fórmula de indexación lineal para matrices multidimensionales que se declaran con un tamaño constante de tiempo de compilación, por ejemplo, por int A[10][20]o int A[m][n], en lugar del tradicional int **A.

Notación de indexación

La mayoría de los lenguajes de programación que admiten matrices admiten las operaciones de almacenamiento y selección , y tienen una sintaxis especial para la indexación. Los primeros idiomas usaban paréntesis, por ejemplo A(i,j), como en FORTRAN; otros eligen corchetes, por ejemplo, A[i,j]o A[i][j], como en Algol 60 y Pascal (para distinguir del uso de paréntesis para llamadas a funciones ).

Tipos de índice

Los tipos de datos de matriz se implementan con mayor frecuencia como estructuras de matriz: con los índices restringidos a valores enteros (o totalmente ordenados), los rangos de índice se fijan en el momento de la creación de la matriz y el direccionamiento de elementos multilineales. Este fue el caso en la mayoría de los lenguajes de "tercera generación" , y sigue siendo el caso de la mayoría de los lenguajes de programación de sistemas como Ada , C y C ++ . En algunos lenguajes, sin embargo, los tipos de datos de matriz tienen la semántica de matrices asociativas, con índices de tipo arbitrario y creación de elementos dinámicos. Este es el caso de algunos lenguajes de scripting como Awk y Lua , y de algunos tipos de arreglos proporcionados por las bibliotecas estándar de C ++ .

Comprobación de límites

Algunos lenguajes (como Pascal y Modula) realizan la verificación de límites en cada acceso, generando una excepción o abortando el programa cuando algún índice está fuera de su rango válido. Los compiladores pueden permitir que estos controles se desactiven para intercambiar seguridad por velocidad. Otros lenguajes (como FORTRAN y C) confían en el programador y no realizan comprobaciones. Los buenos compiladores también pueden analizar el programa para determinar el rango de valores posibles que puede tener el índice, y este análisis puede conducir a la eliminación de la verificación de límites .

Origen del índice

Algunos lenguajes, como C, proporcionan sólo tipos de matrices de base cero , para los cuales el valor mínimo válido para cualquier índice es 0. Esta opción es conveniente para la implementación de matrices y cálculos de direcciones. Con un lenguaje como C, se puede definir un puntero al interior de cualquier matriz que actuará simbólicamente como una pseudo-matriz que acomoda índices negativos. Esto funciona solo porque C no compara un índice con los límites cuando se usa.

Otros lenguajes proporcionan solo tipos de matriz basados en uno, donde cada índice comienza en 1; esta es la convención tradicional en matemáticas para matrices y secuencias matemáticas . Algunos lenguajes, como Pascal y Lua, admiten tipos de matrices basados en n , cuyos índices legales mínimos son elegidos por el programador. Los méritos relativos de cada elección han sido objeto de acalorados debates. La indexación basada en cero puede evitar errores de uno por uno o de poste de cerca , específicamente un basado en 0 para (i = 0; i <5; i + = 1) itera (5-0) veces, mientras que en la mitad equivalente basada en 1 -rango abierto para (i = 1; i <6; i + = 1) el 6 es en sí mismo un error potencial de este tipo, que generalmente requiere longitud () + 1, y el rango inclusivo basado en 1 para (i = 1; i <= 5; i + = 1) itera (5-1) +1 veces.

Consulte la comparación de lenguajes de programación (matriz) para conocer los índices base utilizados por varios lenguajes.

Índice más alto

La relación entre los números que aparecen en una declaración de matriz y el índice del último elemento de esa matriz también varía según el idioma. En muchos lenguajes (como C), se debe especificar el número de elementos contenidos en la matriz; mientras que en otros (como Pascal y Visual Basic .NET ) se debe especificar el valor numérico del índice del último elemento. No hace falta decir que esta distinción es irrelevante en idiomas donde los índices comienzan en 1, como Lua .

Álgebra de matrices

Algunos lenguajes de programación admiten la programación de matrices , donde las operaciones y funciones definidas para ciertos tipos de datos se extienden implícitamente a matrices de elementos de esos tipos. Así, uno puede escribir A + B a añadir correspondientes elementos de dos matrices A y B . Por lo general, estos lenguajes proporcionan tanto la multiplicación elemento por elemento como el producto matricial estándar del álgebra lineal , y cuál de estos está representado por el operador * varía según el idioma.

Los lenguajes que proporcionan capacidades de programación de matrices han proliferado desde las innovaciones en esta área de APL . Estas son capacidades básicas de lenguajes de dominios específicos como GAUSS , IDL , Matlab y Mathematica . Son una instalación central en lenguajes más nuevos, como Julia y versiones recientes de Fortran . Estas capacidades también se proporcionan a través de bibliotecas de extensión estándar para otros lenguajes de programación de propósito general (como la biblioteca NumPy ampliamente utilizada para Python ).

Tipos de cadenas y matrices

Muchos lenguajes proporcionan un tipo de datos de cadena incorporado , con notación especializada (" literales de cadena ") para generar valores de ese tipo. En algunos idiomas (como C), una cadena es solo una matriz de caracteres o se maneja de la misma manera. Otros lenguajes, como Pascal , pueden proporcionar operaciones muy diferentes para cadenas y matrices.

Consultas de rango de índice de matriz

Algunos lenguajes de programación proporcionan operaciones que devuelven el tamaño (número de elementos) de un vector o, más generalmente, el rango de cada índice de una matriz. En C y C ++, las matrices no admiten la función de tamaño , por lo que los programadores a menudo tienen que declarar una variable separada para mantener el tamaño y pasarla a los procedimientos como un parámetro separado.

Los elementos de una matriz recién creada pueden tener valores indefinidos (como en C), o pueden definirse para tener un valor "predeterminado" específico como 0 o un puntero nulo (como en Java).

En C ++, un objeto std :: vector admite las operaciones de almacenamiento , selección y anexión con las características de rendimiento descritas anteriormente. Los vectores se pueden consultar por su tamaño y se pueden cambiar de tamaño. También se admiten operaciones más lentas, como insertar un elemento en el medio.

Rebanar

Una operación de corte de matriz toma un subconjunto de los elementos de una entidad de tipo matriz (valor o variable) y luego los ensambla como otra entidad de tipo matriz, posiblemente con otros índices. Si los tipos de matriz se implementan como estructuras de matriz, muchas operaciones útiles de corte (como seleccionar una submatriz, intercambiar índices o invertir la dirección de los índices) se pueden realizar de manera muy eficiente manipulando el vector de droga de la estructura. Los posibles cortes dependen de los detalles de implementación: por ejemplo, FORTRAN permite cortar una columna de una variable de matriz, pero no una fila, y tratarla como un vector; mientras que C permite cortar una fila de una matriz, pero no una columna.

Por otro lado, son posibles otras operaciones de corte cuando los tipos de matriz se implementan de otras formas.

Cambiar el tamaño

Algunos lenguajes permiten matrices dinámicas (también llamadas redimensionables , ampliables o extensibles ): variables de matriz cuyos rangos de índice se pueden expandir en cualquier momento después de la creación, sin cambiar los valores de sus elementos actuales.

Para matrices unidimensionales, esta función puede proporcionarse como una operación " append( A , x )" que aumenta el tamaño de la matriz A en uno y luego establece el valor del último elemento ax . Otros tipos de matrices (como las cadenas de Pascal) proporcionan un operador de concatenación, que se puede usar junto con el corte para lograr ese efecto y más. En algunos lenguajes, la asignación de un valor a un elemento de una matriz amplía automáticamente la matriz, si es necesario, para incluir ese elemento. En otros tipos de matrices, una rebanada se puede reemplazar por una matriz de diferente tamaño "y los elementos subsiguientes se vuelven a numerar en consecuencia, como en la asignación de lista de Python" A [5: 5] = [10,20,30] ", que inserta tres nuevos elementos (10,20 y 30) antes del elemento " A [5]". Las matrices redimensionables son conceptualmente similares a las listas , y los dos conceptos son sinónimos en algunos idiomas.

Una matriz extensible se puede implementar como una matriz de tamaño fijo, con un contador que registra cuántos elementos están realmente en uso. La appendoperación simplemente incrementa el contador; hasta que se utilice toda la matriz, cuando appendse puede definir que la operación falle. Se trata de una implementación de un arreglo dinámico con una capacidad fija, como en el stringtipo de Pascal. Alternativamente, la appendoperación puede reasignar la matriz subyacente con un tamaño mayor y copiar los elementos antiguos a la nueva área.

Languages

In other projects