Programare matrice - Array programming
În informatică , programarea matricială se referă la soluții care permit aplicarea operațiilor la un set întreg de valori simultan. Astfel de soluții sunt utilizate în mod obișnuit în setările științifice și inginerești .
Limbajele de programare moderne care acceptă programarea matricei (cunoscute și sub numele de limbaje vectoriale sau multidimensionale ) au fost concepute special pentru a generaliza operațiunile pe scalare pentru a se aplica în mod transparent vectorilor , matricilor și matricilor cu dimensiuni superioare. Acestea includ APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (ca liste), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) și extensia NumPy la Python . În aceste limbaje, o operație care operează pe tablouri întregi poate fi numită operație vectorizată , indiferent dacă este executată pe un procesor vector , care implementează instrucțiuni vectoriale. Primitivele de programare a matricilor exprimă concis idei largi despre manipularea datelor. Nivelul de concizie poate fi dramatic în anumite cazuri: nu este neobișnuit să găsești un liner de limbaj de programare matrice care necesită mai multe pagini de cod orientat obiect.
Concepte de matrice
Ideea fundamentală din spatele programării matrice este că operațiile se aplică simultan unui întreg set de valori. Acest lucru îl face un model de programare la nivel înalt , deoarece permite programatorului să gândească și să opereze pe agregate întregi de date, fără a fi nevoie să recurgă la bucle explicite ale operațiilor scalare individuale.
Kenneth E. Iverson a descris rațiunea din spatele programării matrice (referindu-se de fapt la APL) după cum urmează:
majoritatea limbajelor de programare sunt cu siguranță inferioare notației matematice și sunt puțin utilizate ca instrumente de gândire în moduri care ar fi considerate semnificative de, să zicem, un matematician aplicat.
Teza este că avantajele executabilității și universalității găsite în limbajele de programare pot fi combinate în mod eficient, într-un singur limbaj coerent, cu avantajele oferite de notația matematică. este important să distingem dificultatea de a descrie și de a învăța o bucată de notație de dificultatea de a-și însuși implicațiile. De exemplu, învățarea regulilor pentru calculul unui produs matricial este ușoară, dar o stăpânire a implicațiilor sale (cum ar fi asociativitatea, distributivitatea față de adiție și capacitatea sa de a reprezenta funcții liniare și operații geometrice) este o chestiune diferită și mult mai dificilă .
Într-adevăr, chiar sugestivitatea unei notații poate face să pară mai greu de învățat din cauza numeroaselor proprietăți pe care le sugerează pentru explorări.
[...]
Utilizatorii de computere și limbaje de programare sunt deseori preocupați în primul rând de eficiența executării algoritmilor și, prin urmare, ar putea respinge sumar mulți dintre algoritmii prezentați aici. O astfel de concediere ar fi miopă, deoarece o declarație clară a unui algoritm poate fi utilizată de obicei ca bază din care se poate obține cu ușurință un algoritm mai eficient.
Baza din spatele programării și gândirii matrice este găsirea și exploatarea proprietăților datelor în care elementele individuale sunt similare sau adiacente. Spre deosebire de orientarea obiectului, care implicit descompune datele în părțile sale componente (sau cantități scalare ), orientarea matricei arată gruparea datelor și aplicarea unei manipulări uniforme.
Rangul funcțional este un concept important pentru matricea limbajelor de programare în general, prin analogie cu rangul tensorial din matematică: funcțiile care operează pe date pot fi clasificate după numărul de dimensiuni pe care acționează. Înmulțirea obișnuită, de exemplu, este o funcție clasificată scalar, deoarece operează pe date cu dimensiuni zero (numere individuale). Operația de produs încrucișat este un exemplu de funcție de rang vector, deoarece operează pe vectori, nu pe scalari. Înmulțirea matricei este un exemplu de funcție cu 2 ranguri, deoarece operează pe obiecte bidimensionale (matrice). Operatorii de colaps reduc dimensionalitatea unei matrice de date de intrare cu una sau mai multe dimensiuni. De exemplu, însumarea peste elemente restrânge matricea de intrare cu 1 dimensiune.
Utilizări
Programarea matricei este foarte potrivită pentru paralelizarea implicită ; un subiect de multe cercetări în zilele noastre. Mai mult, procesoarele Intel și compatibile dezvoltate și produse după 1997 conțineau diverse extensii de seturi de instrucțiuni, începând de la MMX și continuând prin SSSE3 și 3DNow! , care includ capabilități de matrice SIMD rudimentare . Procesarea matricii este distinctă de procesarea paralelă, deoarece un procesor fizic efectuează operațiuni simultan pe un grup de articole, în timp ce procesarea paralelă urmărește să împartă o problemă mai mare în altele mai mici ( MIMD ) pentru a fi rezolvate în bucăți de numeroase procesoare. Procesoarele cu două sau mai multe nuclee sunt din ce în ce mai frecvente astăzi.
Limbi
Exemplele canonice de limbaje de programare matrice sunt Fortran , APL și J . Altele includ: A + , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL și TI-BASIC .
Limbi scalare
În limbaje scalare, cum ar fi C și Pascal , operațiile se aplică numai valorilor unice, astfel încât a + b exprimă adunarea a două numere. În astfel de limbi, adăugarea unei matrice la alta necesită indexare și buclare, a căror codificare este plictisitoare.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
În limbile bazate pe matrice, de exemplu în Fortran, bucla cuplată de mai sus poate fi scrisă în format matrice într-o singură linie,
a = a + b
sau, alternativ, pentru a sublinia natura matricei obiectelor,
a(:,:) = a(:,:) + b(:,:)
În timp ce limbajele scalare, cum ar fi C, nu au elemente native de programare a matricei ca parte a limbajului propriu-zis, acest lucru nu înseamnă că programele scrise în aceste limbi nu profită niciodată de tehnicile subiacente de vectorizare (adică, folosind instrucțiunile bazate pe vector ale unui CPU, dacă are sau folosind mai multe nuclee CPU). Unele compilatoare C, cum ar fi GCC la unele niveluri de optimizare, detectează și vectorizează secțiuni de cod pe care euristicele sale le-ar determina să beneficieze de acesta. O altă abordare este dată de API-ul OpenMP , care permite paralelizarea secțiunilor de cod aplicabile, profitând de mai multe nuclee CPU.
Limbi matrice
În limbile de matrice, operațiile sunt generalizate pentru a se aplica atât scalarilor, cât și matricelor. Astfel, a + b exprimă suma a două scalare dacă a și b sunt scalare, sau suma a două tablouri dacă sunt tablouri.
Un limbaj matricial simplifică programarea, dar posibil la un cost cunoscut sub numele de penalizare de abstractizare . Deoarece adăugirile sunt efectuate izolat de restul codării, este posibil să nu producă codul optim cel mai eficient . (De exemplu, adăugările altor elemente ale aceluiași tablou pot fi întâlnite ulterior în timpul aceleiași execuții, provocând căutări repetate inutile.) Chiar și cel mai sofisticat compilator de optimizare ar avea dificultăți extrem de mari în amalgamarea a două sau mai multe funcții aparent disparate care ar putea apărea în diferite secțiuni de program sau subrutine, chiar dacă un programator ar putea face acest lucru cu ușurință, agregând sume pe aceeași trecere peste matrice pentru a minimiza cheltuielile generale ).
Ada
Codul C anterior ar deveni următorul în limbajul Ada , care acceptă sintaxa programării matrice.
A := A + B;
APL
APL utilizează simboluri Unicode cu un singur caracter, fără zahăr sintactic.
A ← A + B
Această operație funcționează pe tablouri de orice rang (inclusiv rangul 0), și pe un scalar și un tablou. Dyalog APL extinde limba originală cu sarcini augmentate :
A +← B
Analytica
Analytica oferă aceeași economie de exprimare ca și Ada.
A := A + B;
DE BAZĂ
Dartmouth BASIC a avut declarații MAT pentru manipularea matricei și matricei în cea de-a treia ediție (1966).
DIM A(4),B(4),C(4)
MAT A = 1
MAT B = 2 * A
MAT C = A + B
MAT PRINT A,B,C
Mata
Limbajul de programare matricial al Stata Mata acceptă programarea matricei. Mai jos, ilustrăm adunarea, înmulțirea, adunarea unei matrice și a unui scalar, înmulțire element cu element, subscriptare și una dintre numeroasele funcții ale matricei inverse.
. mata:
: A = (1,2,3) \(4,5,6)
: A
1 2 3
+-------------+
1 | 1 2 3 |
2 | 4 5 6 |
+-------------+
: B = (2..4) \(1..3)
: B
1 2 3
+-------------+
1 | 2 3 4 |
2 | 1 2 3 |
+-------------+
: C = J(3,2,1) // A 3 by 2 matrix of ones
: C
1 2
+---------+
1 | 1 1 |
2 | 1 1 |
3 | 1 1 |
+---------+
: D = A + B
: D
1 2 3
+-------------+
1 | 3 5 7 |
2 | 5 7 9 |
+-------------+
: E = A*C
: E
1 2
+-----------+
1 | 6 6 |
2 | 15 15 |
+-----------+
: F = A:*B
: F
1 2 3
+----------------+
1 | 2 6 12 |
2 | 4 10 18 |
+----------------+
: G = E :+ 3
: G
1 2
+-----------+
1 | 9 9 |
2 | 18 18 |
+-----------+
: H = F[(2\1), (1, 2)] // Subscripting to get a submatrix of F and
: // switch row 1 and 2
: H
1 2
+-----------+
1 | 4 10 |
2 | 2 6 |
+-----------+
: I = invsym(F'*F) // Generalized inverse (F*F^(-1)F=F) of a
: // symmetric positive semi-definite matrix
: I
[symmetric]
1 2 3
+-------------------------------------------+
1 | 0 |
2 | 0 3.25 |
3 | 0 -1.75 .9444444444 |
+-------------------------------------------+
: end
MATLAB
Implementarea în MATLAB permite aceeași economie permisă prin utilizarea limbajului Fortran.
A = A + B;
O variantă a limbajului MATLAB este limbajul GNU Octave , care extinde limba originală cu atribuții augmentate:
A += B;
Atât MATLAB, cât și GNU Octave suportă în mod nativ operații de algebră liniară , cum ar fi multiplicarea matricei, inversarea matricei și soluția numerică a sistemului de ecuații liniare , chiar folosind pseudoinversa Moore-Penrose .
Exemplul Nial al produsului interior a două matrice poate fi implementat folosind operatorul de multiplicare a matricei native. Dacă aeste un vector rând de mărime [1 n] și beste un vector de coloană corespunzător de dimensiune [n 1].
a * b;
Produsul interior dintre două matrice având același număr de elemente poate fi implementat cu operatorul auxiliar (:), care remodelează o matrice dată într-un vector de coloană și operatorul de transpunere' :
A(:)' * B(:);
rasql
Limba de interogare rasdaman este un limbaj de programare-matrice orientate spre baze de date. De exemplu, ar putea fi adăugate două tablouri cu următoarea interogare:
SELECT A + B
FROM A, B
R
Limbajul R acceptă implicit paradigma matricei . Următorul exemplu ilustrează un proces de multiplicare a două matrice urmat de o adăugare a unui scalar (care este, de fapt, un vector cu un singur element) și un vector:
> A <- matrix(1:6, nrow=2) !!this has nrow=2 ... and A has 2 rows
> A
[,1] [,2] [,3]
[1,] 1 3 5
[2,] 2 4 6
> B <- t( matrix(6:1, nrow=2) ) # t() is a transpose operator !!this has nrow=2 ... and B has 3 rows --- a clear contradiction to the definition of A
> B
[,1] [,2]
[1,] 6 5
[2,] 4 3
[3,] 2 1
> C <- A %*% B
> C
[,1] [,2]
[1,] 28 19
[2,] 40 28
> D <- C + 1
> D
[,1] [,2]
[1,] 29 20
[2,] 41 29
> D + c(1, 1) # c() creates a vector
[,1] [,2]
[1,] 30 21
[2,] 42 30
Raționamentul matematic și notația limbajului
Operatorul de divizare la stânga al matricei exprimă concis unele proprietăți semantice ale matricilor. Ca și în echivalentul scalar, în cazul în care ( determinant al) Coeficientul (matricea) Anu este nul , atunci este posibil pentru a rezolva (vectoriala) ecuația A * x = bprin stânga înmulțirea ambele părți cu inversul a A: (în ambele limbi MATLAB și GNU Octave : ). Următoarele afirmații matematice sunt valabile atunci când este o matrice pătrată cu rang complet :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b( asociativitate matrice-multiplicare ) x = A^-1 * b
unde ==este operatorul relațional de echivalență . Afirmațiile anterioare sunt, de asemenea, expresii MATLAB valabile dacă a treia este executată înainte de celelalte (comparațiile numerice pot fi false din cauza erorilor de rotunjire).
Dacă sistemul este supradeterminat - deci Aare mai multe rânduri decât coloane - pseudoinversul (în limbile MATLAB și GNU Octave:) poate înlocui inversul , după cum urmează:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(asociativitate matrice-multiplicare) x = pinv(A) * b
Cu toate acestea, aceste soluții nu sunt nici cele mai concise (de exemplu, rămâne încă nevoia de a diferenția din punct de vedere notațional sistemele nedeterminate) și nici cele mai eficiente din punct de vedere al calculului. Ultimul punct este ușor de înțeles atunci când se ia în considerare din nou echivalentul scalar a * x = b, pentru care soluția x = a^-1 * bar necesita două operații în locul celei mai eficiente x = b / a. Problema este că în general multiplicările matricei nu sunt comutative, deoarece extinderea soluției scalare la cazul matricei ar necesita:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(comutativitatea nu este valabilă pentru matrice!) -
x * (a / a)==b / a(asociativitatea este valabilă și pentru matrice) x = b / a
Limbajul MATLAB introduce operatorul de divizare stânga \pentru a menține partea esențială a analogiei cu cazul scalar, simplificând astfel raționamentul matematic și păstrând concizia:
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(asociativitatea este valabilă și pentru matrice, nu mai este necesară comutativitatea) x = A \ b
Acesta nu este doar un exemplu de programare a matricei din punct de vedere al codificării, ci și din perspectiva eficienței computaționale, care în mai multe limbaje de programare a matricei beneficiază de biblioteci de algebră liniară destul de eficiente, cum ar fi ATLAS sau LAPACK .
Revenind la citatul anterior al lui Iverson, rațiunea din spatele acestuia ar trebui să fie acum evidentă:
este important să distingem dificultatea de a descrie și de a învăța o bucată de notație de dificultatea de a-și însuși implicațiile. De exemplu, învățarea regulilor pentru calculul unui produs matricial este ușoară, dar o stăpânire a implicațiilor sale (cum ar fi asociativitatea, distributivitatea față de adiție și capacitatea sa de a reprezenta funcții liniare și operații geometrice) este o chestiune diferită și mult mai dificilă . Într-adevăr, chiar sugestivitatea unei notații poate face să pară mai greu de învățat din cauza numeroaselor proprietăți pe care le sugerează pentru explorări.
Biblioteci terțe
Utilizarea bibliotecilor specializate și eficiente pentru a oferi abstracții mai concise este, de asemenea, obișnuită în alte limbaje de programare. În C ++, mai multe biblioteci liniare de algebră exploatează capacitatea limbajului de a supraîncărca operatorii . În unele cazuri, o abstracție foarte concisă în aceste limbaje este influențată în mod explicit de paradigma de programare a matricei, așa cum fac bibliotecile Armadillo și Blitz ++ .
