Programmation de tableaux - Array programming
En informatique , la programmation matricielle fait référence à des solutions qui permettent l'application d'opérations à un ensemble complet de valeurs à la fois. De telles solutions sont couramment utilisées dans les milieux scientifiques et techniques .
Les langages de programmation modernes qui prennent en charge la programmation matricielle (également appelés langages vectoriels ou multidimensionnels ) ont été spécialement conçus pour généraliser les opérations sur les scalaires afin de s'appliquer de manière transparente aux vecteurs , matrices et tableaux de dimensions supérieures. Ceux-ci incluent APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (sous forme de listes), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) et l' extension NumPy à Python . Dans ces langages, une opération qui opère sur des tableaux entiers peut être appelée une opération vectorisée , qu'elle soit exécutée ou non sur un processeur vectoriel , qui implémente des instructions vectorielles. Les primitives de programmation matricielle expriment de manière concise des idées générales sur la manipulation de données. Le niveau de concision peut être dramatique dans certains cas : il n'est pas rare de trouver des one-liners en langage de programmation matriciel qui nécessitent plusieurs pages de code orienté objet.
Concepts de tableau
L'idée fondamentale derrière la programmation matricielle est que les opérations s'appliquent à la fois à un ensemble complet de valeurs. Cela en fait un modèle de programmation de haut niveau car il permet au programmeur de penser et d'opérer sur des agrégats entiers de données, sans avoir à recourir à des boucles explicites d'opérations scalaires individuelles.
Kenneth E. Iverson a décrit la logique derrière la programmation de tableaux (en fait, se référant à APL) comme suit :
la plupart des langages de programmation sont nettement inférieurs à la notation mathématique et sont peu utilisés comme outils de pensée d'une manière qui serait considérée comme significative par, disons, un mathématicien appliqué.
La thèse est que les avantages d'exécutabilité et d'universalité trouvés dans les langages de programmation peuvent être efficacement combinés, dans un seul langage cohérent, avec les avantages offerts par la notation mathématique. il est important de distinguer la difficulté de décrire et d'apprendre une notation de la difficulté d'en maîtriser les implications. Par exemple, apprendre les règles de calcul d'un produit matriciel est facile, mais la maîtrise de ses implications (telles que son associativité, sa distributivité sur l'addition et sa capacité à représenter des fonctions linéaires et des opérations géométriques) est une question différente et beaucoup plus difficile. .
En effet, le caractère même suggestif d'une notation peut la rendre plus difficile à apprendre en raison des nombreuses propriétés qu'elle suggère pour les explorations.
[...]
Les utilisateurs d'ordinateurs et de langages de programmation sont souvent principalement concernés par l'efficacité de l'exécution des algorithmes et pourraient donc rejeter sommairement bon nombre des algorithmes présentés ici. Un tel rejet serait à courte vue puisqu'un énoncé clair d'un algorithme peut généralement être utilisé comme base à partir de laquelle on peut facilement dériver un algorithme plus efficace.
La base de la programmation et de la réflexion sur les tableaux est de trouver et d'exploiter les propriétés des données où les éléments individuels sont similaires ou adjacents. Contrairement à l'orientation objet qui décompose implicitement les données en leurs éléments constitutifs (ou quantités scalaires ), l'orientation en tableau cherche à regrouper les données et à appliquer une gestion uniforme.
Le rang de fonction est un concept important pour les langages de programmation matricielle en général, par analogie au rang de tenseur en mathématiques : les fonctions qui opèrent sur des données peuvent être classées selon le nombre de dimensions sur lesquelles elles agissent. La multiplication ordinaire, par exemple, est une fonction classée scalaire car elle opère sur des données de dimension zéro (nombres individuels). L' opération de produit croisé est un exemple de fonction de rang vectoriel car elle opère sur des vecteurs et non sur des scalaires. La multiplication matricielle est un exemple de fonction à 2 rangs, car elle opère sur des objets à 2 dimensions (matrices). Les opérateurs de réduction réduisent la dimensionnalité d'un tableau de données d'entrée d'une ou plusieurs dimensions. Par exemple, la somme des éléments réduit le tableau d'entrée d'une dimension.
Les usages
La programmation en tableaux est très bien adaptée à la parallélisation implicite ; un sujet de beaucoup de recherches de nos jours. De plus, les processeurs Intel et compatibles développés et produits après 1997 contenaient diverses extensions de jeux d'instructions, à partir de MMX et continuant jusqu'à SSSE3 et 3DNow ! , qui incluent des capacités de baie SIMD rudimentaires . Le traitement matriciel est distinct du traitement parallèle en ce qu'un processeur physique effectue des opérations sur un groupe d'éléments simultanément, tandis que le traitement parallèle vise à diviser un problème plus vaste en problèmes plus petits ( MIMD ) à résoudre au coup par coup par de nombreux processeurs. Les processeurs à deux cœurs ou plus sont de plus en plus courants aujourd'hui.
Langues
Les exemples canoniques de langages de programmation de tableaux sont Fortran , APL et J . D'autres incluent : A+ , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL et TI-BASIC .
Langages scalaires
Dans les langages scalaires tels que C et Pascal , les opérations ne s'appliquent qu'à des valeurs uniques, donc a + b exprime l'addition de deux nombres. Dans de tels langages, l'ajout d'un tableau à un autre nécessite une indexation et un bouclage, dont le codage est fastidieux.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
Dans les langages basés sur des tableaux, par exemple en Fortran, la boucle for imbriquée ci-dessus peut être écrite au format tableau sur une seule ligne,
a = a + b
ou bien, pour souligner la nature matricielle des objets,
a(:,:) = a(:,:) + b(:,:)
Bien que les langages scalaires comme le C n'aient pas d'éléments de programmation de tableau natifs dans le langage proprement dit, cela ne signifie pas que les programmes écrits dans ces langages ne tirent jamais parti des techniques sous-jacentes de vectorisation (c'est-à-dire, utiliser les instructions vectorielles d' un processeur s'il a eux ou en utilisant plusieurs cœurs de processeur). Certains compilateurs C comme GCC à certains niveaux d'optimisation détectent et vectorisent les sections de code qui, selon ses heuristiques, pourraient en bénéficier. Une autre approche est proposée par l' API OpenMP , qui permet de paralléliser les sections de code applicables en tirant parti de plusieurs cœurs de processeur.
Langues du tableau
Dans les langages de tableaux, les opérations sont généralisées pour s'appliquer à la fois aux scalaires et aux tableaux. Ainsi, a + b exprime la somme de deux scalaires si a et b sont des scalaires, ou la somme de deux tableaux s'ils sont des tableaux.
Un langage matriciel simplifie la programmation mais peut-être à un coût connu sous le nom de pénalité d'abstraction . Étant donné que les ajouts sont effectués indépendamment du reste du codage, ils peuvent ne pas produire le code le plus efficace de manière optimale . (Par exemple, des ajouts d'autres éléments du même tableau peuvent être rencontrés par la suite au cours de la même exécution, provoquant des recherches répétées inutiles.) Même le compilateur d'optimisation le plus sophistiqué aurait beaucoup de mal à fusionner deux ou plusieurs fonctions apparemment disparates qui pourraient apparaître dans différentes sections de programme ou sous-routines, même si un programmeur pourrait le faire facilement, en agrégeant des sommes sur le même passage sur le tableau pour minimiser les frais généraux ).
Ada
Le code C précédent deviendrait le suivant dans le langage Ada , qui prend en charge la syntaxe de programmation de tableaux.
A := A + B;
APL
APL utilise des symboles Unicode à un seul caractère sans sucre syntaxique.
A ← A + B
Cette opération fonctionne sur des tableaux de n'importe quel rang (y compris le rang 0) et sur un scalaire et un tableau. Dyalog APL étend le langage d'origine avec des affectations augmentées :
A +← B
Analytica
Analytica offre la même économie d'expression qu'Ada.
A := A + B;
DE BASE
Dartmouth BASIC avait des instructions MAT pour la manipulation de matrices et de tableaux dans sa troisième édition (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
Le langage de programmation matriciel de Stata Mata prend en charge la programmation de tableaux. Ci-dessous, nous illustrons l'addition, la multiplication, l'addition d'une matrice et d'un scalaire, la multiplication élément par élément, l'indice et l'une des nombreuses fonctions matricielles inverses de Mata.
. 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
L'implémentation dans MATLAB permet la même économie permise en utilisant le langage Fortran.
A = A + B;
Une variante du langage MATLAB est le langage GNU Octave , qui étend le langage d'origine avec des affectations augmentées :
A += B;
MATLAB et GNU Octave prennent en charge nativement les opérations d' algèbre linéaire telles que la multiplication matricielle, l'inversion matricielle et la solution numérique du système d'équations linéaires , même en utilisant le pseudo-inverse de Moore-Penrose .
L' exemple Nial du produit interne de deux tableaux peut être implémenté à l'aide de l'opérateur de multiplication matriciel natif. Si aest un vecteur ligne de taille [1 n] et best un vecteur colonne correspondant de taille [n 1].
a * b;
Le produit scalaire entre deux matrices ayant le même nombre d'éléments peut être implémenté avec l'opérateur auxiliaire (:), qui remodèle une matrice donnée en un vecteur colonne, et l' opérateur de transposition' :
A(:)' * B(:);
rasql
Le langage de requête rasdaman est un langage de programmation de tableaux orienté base de données. Par exemple, deux tableaux peuvent être ajoutés avec la requête suivante :
SELECT A + B
FROM A, B
R
Le langage R prend en charge le paradigme de tableau par défaut. L'exemple suivant illustre un processus de multiplication de deux matrices suivi d'une addition d'un scalaire (qui est en fait un vecteur à un élément) et d'un vecteur :
> 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
Raisonnement mathématique et notation linguistique
L'opérateur de division gauche de la matrice exprime de manière concise certaines propriétés sémantiques des matrices. Comme dans l'équivalent scalaire, si le ( déterminant du) coefficient (matrice) An'est pas nul alors il est possible de résoudre l'équation (vectorielle) A * x = ben multipliant à gauche les deux côtés par l' inverse de A: (dans les deux langages MATLAB et GNU Octave : ). Les déclarations mathématiques suivantes sont valables quand est une matrice carrée de rang complet :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b(matrice de multiplication associativité ) x = A^-1 * b
où ==est l' opérateur relationnel d' équivalence . Les instructions précédentes sont également des expressions MATLAB valides si la troisième est exécutée avant les autres (les comparaisons numériques peuvent être fausses en raison d'erreurs d'arrondi).
Si le système est surdéterminé – donc qui Aa plus de lignes que de colonnes – le pseudoinverse (dans les langages MATLAB et GNU Octave : ) peut remplacer l'inverse , comme suit :
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(associativité matrice-multiplication) x = pinv(A) * b
Cependant, ces solutions ne sont ni les plus concises (il reste par exemple le besoin de différencier notationnellement les systèmes surdéterminés) ni les plus efficaces en calcul. Ce dernier point est facile à comprendre en considérant à nouveau l'équivalent scalaire a * x = b, pour lequel la solution x = a^-1 * bnécessiterait deux opérations au lieu de la plus efficace x = b / a. Le problème est que généralement les multiplications matricielles ne sont pas commutatives car l'extension de la solution scalaire au cas matriciel nécessiterait :
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(la commutativité n'est pas valable pour les matrices !) -
x * (a / a)==b / a(l'associativité est également valable pour les matrices) x = b / a
Le langage MATLAB introduit l'opérateur de division gauche \pour maintenir l'essentiel de l'analogie avec le cas scalaire, simplifiant ainsi le raisonnement mathématique et préservant la concision :
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(l'associativité est également valable pour les matrices, la commutativité n'est plus requise) x = A \ b
Ce n'est pas seulement un exemple de programmation matricielle laconique du point de vue du codage mais aussi du point de vue de l'efficacité de calcul, qui dans plusieurs langages de programmation matricielle bénéficie de bibliothèques d'algèbre linéaire assez efficaces telles que ATLAS ou LAPACK .
Pour en revenir à la citation précédente d'Iverson, la raison qui la sous-tend devrait maintenant être évidente :
il est important de distinguer la difficulté de décrire et d'apprendre une notation de la difficulté d'en maîtriser les implications. Par exemple, apprendre les règles de calcul d'un produit matriciel est facile, mais la maîtrise de ses implications (telles que son associativité, sa distributivité sur l'addition et sa capacité à représenter des fonctions linéaires et des opérations géométriques) est une question différente et beaucoup plus difficile. . En effet, le caractère même suggestif d'une notation peut la rendre plus difficile à apprendre en raison des nombreuses propriétés qu'elle suggère pour les explorations.
Bibliothèques tierces
L'utilisation de bibliothèques spécialisées et efficaces pour fournir des abstractions plus concises est également courante dans d'autres langages de programmation. En C++, plusieurs bibliothèques d'algèbre linéaire exploitent la capacité du langage à surcharger les opérateurs . Dans certains cas, une abstraction très succincte dans ces langages est explicitement influencée par le paradigme de la programmation en tableau, comme le font les bibliothèques Armadillo et Blitz++ .
