Programmazione array - Array programming
In informatica , la programmazione di array si riferisce a soluzioni che consentono l'applicazione di operazioni a un intero insieme di valori contemporaneamente. Tali soluzioni sono comunemente utilizzate in contesti scientifici e ingegneristici .
I moderni linguaggi di programmazione che supportano la programmazione di array (noti anche come linguaggi vettoriali o multidimensionali ) sono stati progettati specificamente per generalizzare le operazioni su scalari da applicare in modo trasparente a vettori , matrici e array di dimensioni superiori. Questi includono APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (come elenchi), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) e l' estensione NumPy a Python . In questi linguaggi, un'operazione che opera su interi array può essere chiamata operazione vettorizzata , indipendentemente dal fatto che venga eseguita su un processore vettoriale , che implementa istruzioni vettoriali. Le primitive di programmazione di array esprimono in modo conciso idee generali sulla manipolazione dei dati. Il livello di concisione può essere drammatico in alcuni casi: non è raro trovare one-liner in linguaggio di programmazione array che richiedono diverse pagine di codice orientato agli oggetti.
Concetti di array
L'idea fondamentale alla base della programmazione degli array è che le operazioni si applicano contemporaneamente a un intero insieme di valori. Questo lo rende un modello di programmazione di alto livello in quanto consente al programmatore di pensare e operare su interi aggregati di dati, senza dover ricorrere a cicli espliciti di singole operazioni scalari.
Kenneth E. Iverson ha descritto la logica alla base della programmazione degli array (in realtà riferendosi all'APL) come segue:
la maggior parte dei linguaggi di programmazione sono decisamente inferiori alla notazione matematica e sono poco usati come strumenti di pensiero in modi che sarebbero considerati significativi, ad esempio, da un matematico applicato.
La tesi è che i vantaggi di eseguibilità e universalità riscontrabili nei linguaggi di programmazione possano essere efficacemente combinati, in un unico linguaggio coerente, con i vantaggi offerti dalla notazione matematica. è importante distinguere la difficoltà di descrivere e di apprendere un pezzo di notazione dalla difficoltà di padroneggiarne le implicazioni. Ad esempio, imparare le regole per calcolare un prodotto matriciale è facile, ma padroneggiarne le implicazioni (come la sua associatività, la sua distributività sull'addizione e la sua capacità di rappresentare funzioni lineari e operazioni geometriche) è una questione diversa e molto più difficile .
In effetti, la stessa suggestione di una notazione può farla sembrare più difficile da imparare a causa delle molte proprietà che suggerisce per le esplorazioni.
[...]
Gli utenti di computer e linguaggi di programmazione sono spesso interessati principalmente all'efficienza dell'esecuzione degli algoritmi e potrebbero, quindi, ignorare sommariamente molti degli algoritmi qui presentati. Tale licenziamento sarebbe miope poiché una chiara enunciazione di un algoritmo può essere solitamente utilizzata come base da cui si può facilmente derivare un algoritmo più efficiente.
La base dietro la programmazione e il pensiero di array è trovare e sfruttare le proprietà dei dati in cui i singoli elementi sono simili o adiacenti. A differenza dell'orientamento agli oggetti che scompone implicitamente i dati nelle sue parti costituenti (o quantità scalari ), l'orientamento degli array cerca di raggruppare i dati e applicare una gestione uniforme.
Il rango di funzione è un concetto importante per i linguaggi di programmazione degli array in generale, per analogia al rango di tensore in matematica: le funzioni che operano sui dati possono essere classificate in base al numero di dimensioni su cui agiscono. La moltiplicazione ordinaria, ad esempio, è una funzione classificata scalare perché opera su dati a dimensione zero (numeri individuali). L' operazione di prodotto incrociato è un esempio di una funzione di rango vettoriale perché opera su vettori, non su scalari. La moltiplicazione di matrici è un esempio di funzione a 2 ranghi, perché opera su oggetti bidimensionali (matrici). Gli operatori di compressione riducono la dimensionalità di una matrice di dati di input di una o più dimensioni. Ad esempio, la somma degli elementi riduce la matrice di input di 1 dimensione.
Usi
La programmazione di array è molto adatta alla parallelizzazione implicita ; un argomento di molta ricerca al giorno d'oggi. Inoltre, le CPU Intel e compatibili sviluppate e prodotte dopo il 1997 contenevano varie estensioni di set di istruzioni, a partire da MMX e continuando attraverso SSSE3 e 3DNow! , che includono funzionalità di array SIMD rudimentali . L'elaborazione di array è diversa dall'elaborazione parallela in quanto un processore fisico esegue operazioni su un gruppo di elementi contemporaneamente mentre l'elaborazione parallela mira a suddividere un problema più grande in problemi più piccoli ( MIMD ) da risolvere in modo frammentario da numerosi processori. I processori con due o più core sono oggi sempre più comuni.
Le lingue
Gli esempi canonici di linguaggi di programmazione array sono Fortran , APL e J . Altri includono: A+ , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL e TI-BASIC .
linguaggi scalari
Nei linguaggi scalari come C e Pascal , le operazioni si applicano solo ai singoli valori, quindi a + b esprime l'aggiunta di due numeri. In tali linguaggi, l'aggiunta di un array a un altro richiede l'indicizzazione e il ciclo, la cui codifica è noiosa.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
Nei linguaggi basati su array, ad esempio in Fortran, il ciclo for annidato sopra può essere scritto in formato array in una riga,
a = a + b
o in alternativa, per enfatizzare la natura array degli oggetti,
a(:,:) = a(:,:) + b(:,:)
Sebbene i linguaggi scalari come il C non abbiano elementi di programmazione array nativi come parte del linguaggio vero e proprio, ciò non significa che i programmi scritti in questi linguaggi non sfruttino mai le tecniche di vettorizzazione sottostanti (cioè, utilizzando le istruzioni basate su vettori di una CPU se ha loro o utilizzando più core della CPU). Alcuni compilatori C come GCC ad alcuni livelli di ottimizzazione rilevano e vettorializzano sezioni di codice che, secondo la sua euristica, ne trarrebbero beneficio. Un altro approccio è dato dall'API OpenMP , che consente di parallelizzare sezioni di codice applicabili sfruttando più core della CPU.
linguaggi array
Nei linguaggi array, le operazioni sono generalizzate per essere applicate sia agli scalari che agli array. Così, un + b esprime la somma di due scalari se una e b sono scalari, o della somma di due matrici se sono matrici.
Un linguaggio array semplifica la programmazione, ma forse a un costo noto come penalità di astrazione . Poiché le aggiunte vengono eseguite isolatamente dal resto della codifica, potrebbero non produrre il codice più efficiente in modo ottimale . (Ad esempio, aggiunte di altri elementi dello stesso array possono essere incontrate successivamente durante la stessa esecuzione, causando inutili ricerche ripetute.) Anche il compilatore di ottimizzazione più sofisticato avrebbe difficoltà a fondere due o più funzioni apparentemente disparate che potrebbero apparire in diverse sezioni di programma o subroutine, anche se un programmatore potrebbe farlo facilmente, aggregando le somme sullo stesso passaggio sull'array per ridurre al minimo l' overhead ).
Ada
Il precedente codice C diventerebbe il seguente nel linguaggio Ada , che supporta la sintassi di programmazione di array.
A := A + B;
APL
APL utilizza simboli Unicode a carattere singolo senza zucchero sintattico.
A ← A + B
Questa operazione funziona su array di qualsiasi rango (incluso il rango 0) e su uno scalare e un array. Dyalog APL estende la lingua originale con assegnazioni aumentate :
A +← B
Analytica
Analytica offre la stessa economia espressiva di Ada.
A := A + B;
DI BASE
Dartmouth BASIC aveva istruzioni MAT per la manipolazione di matrici e array nella sua terza edizione (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
Il linguaggio di programmazione a matrice di Stata Mata supporta la programmazione di array. Di seguito, illustriamo addizione, moltiplicazione, addizione di una matrice e uno scalare, moltiplicazione elemento per elemento, pedice e una delle tante funzioni di matrice inversa di 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'implementazione in MATLAB consente la stessa economia consentita dall'utilizzo del linguaggio Fortran.
A = A + B;
Una variante del linguaggio MATLAB è il linguaggio GNU Octave , che estende il linguaggio originale con assegnazioni aumentate:
A += B;
Sia MATLAB che GNU Octave supportano nativamente operazioni di algebra lineare come la moltiplicazione di matrici, l' inversione di matrici e la soluzione numerica di sistemi di equazioni lineari , anche utilizzando la pseudoinversa di Moore-Penrose .
L' esempio Nial del prodotto interno di due array può essere implementato utilizzando l'operatore di moltiplicazione di matrici native. If aè un vettore riga di dimensione [1 n] ed bè un corrispondente vettore colonna di dimensione [n 1].
a * b;
Il prodotto interno tra due matrici aventi lo stesso numero di elementi può essere implementato con l'operatore ausiliario (:), che rimodella una data matrice in un vettore colonna, e l' operatore di trasposizione' :
A(:)' * B(:);
rasql
Il linguaggio di query rasdaman è un linguaggio di programmazione array orientato al database. Ad esempio, è possibile aggiungere due array con la seguente query:
SELECT A + B
FROM A, B
R
Il linguaggio R supporta il paradigma array per impostazione predefinita. L'esempio seguente illustra un processo di moltiplicazione di due matrici seguito dall'aggiunta di uno scalare (che è, infatti, un vettore a un elemento) e un vettore:
> 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
Ragionamento matematico e notazione linguistica
L'operatore di divisione a sinistra della matrice esprime in modo conciso alcune proprietà semantiche delle matrici. Come nell'equivalente scalare, se il ( determinante del) coefficiente (matrice) Anon è nullo allora è possibile risolvere l'equazione (vettoriale) A * x = bmoltiplicando a sinistra entrambi i membri per l' inverso di A: (in entrambi i linguaggi MATLAB e GNU Octave : ). Le seguenti affermazioni matematiche valgono quando è una matrice quadrata di rango completo :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b( associatività matrice-moltiplicazione ) x = A^-1 * b
dove ==è l' operatore relazionale di equivalenza . Le istruzioni precedenti sono anche espressioni MATLAB valide se la terza viene eseguita prima delle altre (i confronti numerici possono essere falsi a causa di errori di arrotondamento).
Se il sistema è sovradeterminato, quindi Aha più righe che colonne, la pseudoinversa (nei linguaggi MATLAB e GNU Octave: ) può sostituire l'inversa , come segue:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(associatività matrice-moltiplicazione) x = pinv(A) * b
Tuttavia, queste soluzioni non sono né le più concise (ad es. rimane ancora la necessità di differenziare in modo notazionale i sistemi sovradeterminati) né le più efficienti dal punto di vista computazionale. Quest'ultimo punto è di facile comprensione considerando nuovamente l'equivalente scalare a * x = b, per il quale la soluzione x = a^-1 * brichiederebbe due operazioni invece della più efficiente x = b / a. Il problema è che generalmente le moltiplicazioni matriciali non sono commutative in quanto l'estensione della soluzione scalare al caso matriciale richiederebbe:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(la commutatività non vale per le matrici!) -
x * (a / a)==b / a(l'associatività vale anche per le matrici) x = b / a
Il linguaggio MATLAB introduce l'operatore di divisione sinistra \per mantenere la parte essenziale dell'analogia con il caso scalare, semplificando quindi il ragionamento matematico e preservandone la concisione:
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(l'associatività vale anche per le matrici, la commutatività non è più richiesta) x = A \ b
Questo non è solo un esempio di programmazione di array concisa dal punto di vista della codifica, ma anche dal punto di vista dell'efficienza computazionale, che in diversi linguaggi di programmazione di array beneficia di librerie di algebra lineare piuttosto efficienti come ATLAS o LAPACK .
Tornando alla precedente citazione di Iverson, la logica alla base dovrebbe ora essere evidente:
è importante distinguere la difficoltà di descrivere e di apprendere un pezzo di notazione dalla difficoltà di padroneggiarne le implicazioni. Ad esempio, imparare le regole per calcolare un prodotto matriciale è facile, ma padroneggiarne le implicazioni (come la sua associatività, la sua distributività sull'addizione e la sua capacità di rappresentare funzioni lineari e operazioni geometriche) è una questione diversa e molto più difficile . In effetti, la stessa suggestione di una notazione può farla sembrare più difficile da imparare a causa delle molte proprietà che suggerisce per le esplorazioni.
Librerie di terze parti
L'uso di librerie specializzate ed efficienti per fornire astrazioni più concise è comune anche in altri linguaggi di programmazione. In C++ diverse librerie di algebra lineare sfruttano la capacità del linguaggio di sovraccaricare gli operatori . In alcuni casi un'astrazione molto concisa in quei linguaggi è esplicitamente influenzata dal paradigma di programmazione degli array, come fanno le librerie Armadillo e Blitz++ .
