Matriu (tipus de dades)
En informàtica, matriu (en anglès array) és un tipus de dades que representa una col·lecció d'elements (valors o variables), cadascun seleccionat per un o més índexs (claus identificatives) que es poden calcular en temps d'execució durant l'execució del programa. Aquesta col·lecció normalment s'anomena variable de matriu o valor de matriu. Per analogia amb els conceptes matemàtics vector i matriu, els tipus de matriu amb un i dos índexs sovint s'anomenen tipus de vector i tipus de matriu, respectivament. De manera més general, un tipus de matriu multidimensional es pot anomenar tipus tensor, per analogia amb el concepte físic, tensor.[1]
El suport de llenguatge per als tipus de matriu pot incloure certs tipus de dades de matriu integrats, algunes construccions sintàctiques (constructors de tipus de matriu) que el programador pot utilitzar per definir aquests tipus i declarar variables de matriu i una notació especial per indexar elements de matriu. Per exemple, en el llenguatge de programació Pascal, el type MyTable = array [1..4,1..2] of integer, defineix un nou tipus de dades de matriu anomenat MyTable. La declaració var A: MyTable defineix llavors una variable A d'aquest tipus, que és un agregat de vuit elements, cadascun d'ells una variable entera identificada per dos índexs. En el programa Pascal, aquests elements es denoten A[1,1], A[1,2], A[2,1], …, A[4,2]. Els tipus de matrius especials solen ser definits per les biblioteques estàndard de l'idioma.[2]
Les llistes dinàmiques també són més habituals i més fàcils d'implementar que les matrius dinàmiques. Els tipus de matriu es distingeixen dels tipus de registre principalment perquè permeten que els índexs d'element es calculin en temps d'execució, com en l'assignació Pascal A[I,J]:= A[NI,2*J]. Entre altres coses, aquesta característica permet que una sola instrucció iterativa processi arbitràriament molts elements d'una variable de matriu.[3]
En contextos més teòrics, especialment en la teoria de tipus i en la descripció d'algorismes abstractes, els termes "array" i "array type" de vegades es refereixen a un tipus de dades abstractes (ADT) també anomenat matriu abstracta o poden referir-se a una matriu associativa, un model matemàtic amb les operacions bàsiques i el comportament d'un tipus de matriu típic en la majoria d'idiomes – bàsicament, una col·lecció d'elements que són seleccionats mitjançant índexs calculats en temps d'execució.
Depenent de l'idioma, els tipus de matriu es poden solapar (o identificar-se amb) altres tipus de dades que descriuen agregats de valors, com ara llistes i cadenes. Els tipus de matriu solen implementar-se mitjançant estructures de dades de matriu, però de vegades per altres mitjans, com ara taules hash, llistes enllaçades o arbres de recerca.[4]
Història
[modifica]El llenguatge de programació de Heinz Rutishauser Superplan (1949–1951) incloïa matrius multidimensionals. Rutishauser, però, tot i que va descriure com s'havia de construir un compilador per al seu llenguatge, no en va implementar cap.
Els llenguatges assemblador i els llenguatges de baix nivell com BCPL generalment no tenen suport sintàctic per a matrius.
A causa de la importància de les estructures de matriu per a un càlcul eficient, els primers llenguatges de programació d'alt nivell, inclosos FORTRAN (1957), COBOL (1960) i Algol 60 (1960), van proporcionar suport per a matrius multidimensionals.
Implementacions
[modifica]Per tal d'implementar eficaçment variables de tipus com ara estructures de matriu (amb la indexació feta per aritmètica de punters), molts llenguatges restringeixen els índexs a tipus de dades enters [5][6] (o altres tipus que es poden interpretar com a nombres enters, com ara bytes). i tipus enumerats), i requereixen que tots els elements tinguin el mateix tipus de dades i mida d'emmagatzematge. La majoria d'aquests llenguatges també restringeixen cada índex a un interval finit de nombres enters, que roman fix durant tota la vida útil de la variable matriu. En alguns llenguatges compilats, de fet, és possible que els intervals d'índex s'hagin de conèixer en temps de compilació.
D'altra banda, alguns llenguatges de programació ofereixen tipus de matriu més liberals, que permeten la indexació per valors arbitraris, com ara nombres de coma flotant, cadenes, objectes, referències, etc. Aquests valors d'índex no es poden restringir a un interval, i molt menys a un interval fix. Per tant, aquests llenguatges solen permetre crear nous elements arbitraris en qualsevol moment. Aquesta elecció impedeix la implementació de tipus de matriu com a estructures de dades de matriu. És a dir, aquests llenguatges utilitzen una sintaxi semblant a una matriu per implementar una semàntica de matriu associativa més general i, per tant, s'han d'implementar mitjançant una taula hash o alguna altra estructura de dades de cerca.
Suport lingüístic
[modifica]Matrius multidimensionals
[modifica]
El nombre d'índexs necessaris per especificar un element s'anomena dimensió, dimensionalitat o rang del tipus de matriu. (Aquesta nomenclatura entra en conflicte amb el concepte de dimensió en àlgebra lineal, que expressa la forma d'una matriu. Així, es diu que una matriu de nombres amb 5 files i 4 columnes, per tant 20 elements, té la dimensió 2 en contextos informàtics, però representa una matriu que es diu que és de 4 × 5 dimensions. A més, el significat informàtic de "rang" entra en conflicte amb la noció de rang tensor, que és una generalització del concepte d'àlgebra lineal de rang d'una matriu).
Molts idiomes només admeten matrius unidimensionals. En aquests idiomes, una matriu multidimensional normalment es representa amb un vector Iliffe, una matriu unidimensional de referències a matrius d'una dimensió menys. Una matriu bidimensional, en particular, s'implementaria com a vector de punters a les seves files. Així, s'accediria a un element de la fila i i de la columna j d'una matriu A mitjançant una indexació doble ( A [ i ][ j ] en notació típica). Aquesta manera d'emular matrius multidimensionals permet la creació de matrius irregulars, on cada fila pot tenir una mida diferent. – o, en general, on el rang vàlid de cada índex depèn dels valors de tots els índexs precedents.
Aquesta representació per a matrius multidimensionals és força freqüent al programari C i C++. Tanmateix, C i C++ utilitzaran una fórmula d'indexació lineal per a matrius multidimensionals que es declaren amb una mida constant de temps de compilació, per exemple, per int A[10][20] o int A[m][n], en lloc de la tradicional int **A.
Notació d'indexació
[modifica]La majoria dels llenguatges de programació que admeten matrius admeten les operacions d'emmagatzematge i selecció, i tenen una sintaxi especial per a la indexació. Les primeres llengües utilitzaven parèntesis, per exemple A(i,j), com en FORTRAN; d'altres trien claudàtors, per exemple A[i,j] o A[i][j], com en Algol 60 i Pascal (per distingir-se de l'ús de parèntesis per a les trucades de funcions).
Tipus d'índex
[modifica]Els tipus de dades de matriu s'implementen més sovint com a estructures de matriu: amb els índexs restringits a valors enters (o totalment ordenats), intervals d'índex fixats en el moment de la creació de matrius i adreçament d'elements multilineals. Aquest va ser el cas de la majoria de llenguatges de "tercera generació", i encara és el cas de la majoria de llenguatges de programació de sistemes com Ada, C i C++. En alguns idiomes, però, els tipus de dades de matriu tenen la semàntica de matrius associatives, amb índexs de tipus arbitrari i creació d'elements dinàmics. Aquest és el cas d'alguns llenguatges de script com ara Awk i Lua, i d'alguns tipus de matrius proporcionats per les biblioteques C++ estàndard.
Àlgebra de matrius
[modifica]Alguns llenguatges de programació admeten la programació de matrius, on les operacions i funcions definides per a determinats tipus de dades s'estenen implícitament a matrius d'elements d'aquests tipus. Així, es pot escriure A + B per afegir els elements corresponents de dues matrius A i B. Normalment aquests llenguatges proporcionen tant la multiplicació element per element com el producte matricial estàndard de l'àlgebra lineal, i quin d'aquests està representat per l'operador * varia segons el llenguatge.
Els llenguatges que proporcionen capacitats de programació de matrius han proliferat des de les innovacions en aquesta àrea de l'APL. Aquestes són les capacitats bàsiques dels llenguatges específics del domini com ara GAUSS, IDL, Matlab i Mathematica. Són una instal·lació bàsica en idiomes més nous, com ara Julia i versions recents de Fortran. Aquestes capacitats també es proporcionen mitjançant biblioteques d'extensió estàndard per a altres llenguatges de programació de propòsit general (com ara la biblioteca NumPy àmpliament utilitzada per a Python).
Tipus de cadenes i matrius
[modifica]Molts idiomes proporcionen un tipus de dades de cadena integrat, amb una notació especialitzada ("literals de cadena") per crear valors d'aquest tipus. En alguns idiomes (com ara C), una cadena és només una matriu de caràcters o es gestiona de la mateixa manera. Altres idiomes, com Pascal, poden proporcionar operacions molt diferents per a cadenes i matrius.
Referències
[modifica]- ↑ «Introduction to Tensors | TensorFlow Core» (en anglès). TensorFlow.
- ↑ «Array Data Structure Guide» (en anglès americà), 22-05-2024. [Consulta: 18 agost 2024].
- ↑ «Complete Guide to Arrays Data Structure» (en anglès americà). [Consulta: 18 agost 2024].
- ↑ «Data Structures 101: Arrays — A Visual Introduction for Beginners» (en anglès), 12-02-2019. [Consulta: 18 agost 2024].
- ↑ Deitel, Harvey M. C# for Programmers (en anglès). Prentice Hall Professional, 2005, p. 303. ISBN 978-0-13-246591-5.
- ↑ Friesen, Jeff. Learn Java for Android Development: Java 8 and Android 5 Edition (en anglès). Apress, 5 March 2014, p. 56. ISBN 978-1-4302-6455-2.