Programação de matriz - Array programming
Na ciência da computação , a programação de array se refere a soluções que permitem a aplicação de operações a um conjunto completo de valores de uma só vez. Essas soluções são comumente usadas em ambientes científicos e de engenharia .
Linguagens de programação modernas que oferecem suporte à programação de array (também conhecidas como linguagens vetoriais ou multidimensionais ) foram projetadas especificamente para generalizar operações em escalares para aplicação transparente a vetores , matrizes e arrays de dimensões superiores. Estes incluem APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (como listas), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) e a extensão NumPy para Python . Nessas linguagens, uma operação que opera em matrizes inteiras pode ser chamada de operação vetorial , independentemente de ser executada em um processador vetorial , que implementa instruções vetoriais. As primitivas de programação de array expressam concisamente ideias amplas sobre a manipulação de dados. O nível de concisão pode ser dramático em certos casos: não é incomum encontrar uma linha de linguagem de programação de array que requer várias páginas de código orientado a objetos.
Conceitos de matriz
A ideia fundamental por trás da programação de array é que as operações se aplicam de uma vez a um conjunto inteiro de valores. Isso o torna um modelo de programação de alto nível , pois permite ao programador pensar e operar em agregados inteiros de dados, sem ter que recorrer a loops explícitos de operações escalares individuais.
Kenneth E. Iverson descreveu a lógica por trás da programação de array (na verdade, referindo-se ao APL) da seguinte maneira:
a maioria das linguagens de programação é decididamente inferior à notação matemática e é pouco usada como ferramentas de pensamento de maneiras que seriam consideradas significativas por, digamos, um matemático aplicado.
A tese é que as vantagens de executabilidade e universalidade encontradas nas linguagens de programação podem ser efetivamente combinadas, em uma única linguagem coerente, com as vantagens oferecidas pela notação matemática. é importante distinguir a dificuldade de descrever e aprender uma parte da notação da dificuldade de dominar suas implicações. Por exemplo, aprender as regras para calcular um produto de matriz é fácil, mas o domínio de suas implicações (como sua associatividade, sua distributividade sobre a adição e sua capacidade de representar funções lineares e operações geométricas) é uma questão diferente e muito mais difícil .
Na verdade, a própria sugestividade de uma notação pode torná-la mais difícil de aprender por causa das muitas propriedades que sugere para explorações.
[...]
Os usuários de computadores e linguagens de programação estão frequentemente preocupados principalmente com a eficiência da execução de algoritmos e podem, portanto, descartar sumariamente muitos dos algoritmos apresentados aqui. Tal rejeição seria míope, uma vez que uma declaração clara de um algoritmo geralmente pode ser usada como base a partir da qual alguém pode facilmente derivar um algoritmo mais eficiente.
A base por trás da programação e do pensamento em array é encontrar e explorar as propriedades dos dados onde os elementos individuais são semelhantes ou adjacentes. Ao contrário da orientação a objetos, que implicitamente divide os dados em suas partes constituintes (ou quantidades escalares ), a orientação da matriz procura agrupar os dados e aplicar um tratamento uniforme.
A classificação de funções é um conceito importante para linguagens de programação de array em geral, por analogia com a classificação de tensores em matemática: funções que operam em dados podem ser classificadas pelo número de dimensões nas quais atuam. A multiplicação ordinária, por exemplo, é uma função escalar classificada porque opera em dados de dimensão zero (números individuais). A operação de produto vetorial é um exemplo de função de classificação vetorial porque opera em vetores, não em escalares. A multiplicação de matrizes é um exemplo de função 2-rank, porque opera em objetos bidimensionais (matrizes). Os operadores de recolhimento reduzem a dimensionalidade de uma matriz de dados de entrada em uma ou mais dimensões. Por exemplo, somar os elementos reduz a matriz de entrada em 1 dimensão.
Usos
A programação de array é muito adequada para paralelização implícita ; um tema de muita pesquisa hoje em dia. Além disso, a Intel e CPUs compatíveis desenvolvidas e produzidas após 1997 continham várias extensões de conjunto de instruções, começando com MMX e continuando até SSSE3 e 3DNow! , que incluem recursos rudimentares de matriz SIMD . O processamento de array é diferente do processamento paralelo, pois um processador físico executa operações em um grupo de itens simultaneamente, enquanto o processamento paralelo visa dividir um problema maior em problemas menores ( MIMD ) a serem resolvidos aos poucos por vários processadores. Processadores com dois ou mais núcleos são cada vez mais comuns hoje.
línguas
Os exemplos canónicos de linguagens de programação de matriz são Fortran , APL , e J . Outros incluem: A + , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL e TI-BASIC .
Linguagens escalares
Em linguagens escalares como C e Pascal , as operações se aplicam apenas a valores únicos, portanto, a + b expressa a adição de dois números. Nessas linguagens, adicionar um array a outro requer indexação e loop, cuja codificação é tediosa.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
Em linguagens baseadas em matriz, por exemplo em Fortran, o loop for aninhado acima pode ser escrito no formato de matriz em uma linha,
a = a + b
ou alternativamente, para enfatizar a natureza da matriz dos objetos,
a(:,:) = a(:,:) + b(:,:)
Embora as linguagens escalares como C não tenham elementos de programação de array nativos como parte da linguagem adequada, isso não significa que os programas escritos nessas linguagens nunca tiram vantagem das técnicas subjacentes de vetorização (ou seja, utilizando as instruções baseadas em vetores de uma CPU, se houver ou usando vários núcleos de CPU). Alguns compiladores C, como o GCC, em alguns níveis de otimização, detectam e vetorizam seções de código que sua heurística determina que se beneficiariam com isso. Outra abordagem é dada pela API OpenMP , que permite paralelizar seções de código aplicáveis tirando proveito de vários núcleos de CPU.
Linguagens de matriz
Em linguagens de array, as operações são generalizadas para serem aplicadas a escalares e arrays. Assim, um + b expressa a soma de dois escalares se um e b são escalares, ou a soma de duas matrizes se eles são matrizes.
Uma linguagem de array simplifica a programação, mas possivelmente a um custo conhecido como penalidade de abstração . Como as adições são realizadas isoladamente do restante da codificação, elas podem não produzir o código mais eficiente da forma ideal . (Por exemplo, adições de outros elementos da mesma matriz podem ser encontradas subsequentemente durante a mesma execução, causando pesquisas repetidas desnecessárias.) Mesmo o compilador de otimização mais sofisticado teria uma dificuldade extrema em juntar duas ou mais funções aparentemente díspares que podem aparecer em diferentes seções de programa ou sub-rotinas, embora um programador pudesse fazer isso facilmente, agregando somas na mesma passagem sobre o array para minimizar a sobrecarga ).
Ada
O código C anterior se tornaria o seguinte na linguagem Ada , que oferece suporte à sintaxe de programação de array.
A := A + B;
APL
APL usa símbolos Unicode de caractere único sem açúcar sintático.
A ← A + B
Esta operação funciona em matrizes de qualquer classificação (incluindo classificação 0) e em um escalar e uma matriz. O Dyalog APL estende a linguagem original com atribuições aumentadas :
A +← B
Analytica
Analytica oferece a mesma economia de expressão que Ada.
A := A + B;
BASIC
O Dartmouth BASIC tinha instruções MAT para manipulação de matriz e matriz em sua terceira edição (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
Linguagem de programação de matriz de Stata , Mata, oferece suporte à programação de array. Abaixo, ilustramos adição, multiplicação, adição de uma matriz e um escalar, multiplicação elemento por elemento, subscrito e uma das muitas funções de matriz inversa 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
A implementação em MATLAB permite a mesma economia permitida pelo uso da linguagem Fortran.
A = A + B;
Uma variante da linguagem MATLAB é a linguagem GNU Octave , que estende a linguagem original com atribuições aumentadas:
A += B;
Tanto o MATLAB quanto o GNU Octave suportam nativamente operações de álgebra linear , como multiplicação de matrizes, inversão de matrizes e a solução numérica de sistema de equações lineares , mesmo usando o pseudoinverso de Moore-Penrose .
O exemplo Nial do produto interno de duas matrizes pode ser implementado usando o operador de multiplicação de matriz nativa. Se aé um vetor linha de tamanho [1 n] e bé um vetor coluna correspondente de tamanho [n 1].
a * b;
O produto interno entre duas matrizes com o mesmo número de elementos pode ser implementado com o operador auxiliar (:), que remodela uma dada matriz em um vetor coluna, e o operador de transposição' :
A(:)' * B(:);
rasql
A linguagem de consulta rasdaman é uma linguagem de programação de array orientada a banco de dados. Por exemplo, duas matrizes podem ser adicionadas com a seguinte consulta:
SELECT A + B
FROM A, B
R
A linguagem R oferece suporte ao paradigma de array por padrão. O exemplo a seguir ilustra um processo de multiplicação de duas matrizes seguido pela adição de um escalar (que é, na verdade, um vetor de um elemento) e um vetor:
> 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
Raciocínio matemático e notação de linguagem
O operador de divisão à esquerda da matriz expressa de forma concisa algumas propriedades semânticas das matrizes. Como no equivalente escalar, se o ( determinante do) coeficiente (matriz) Anão for nulo, então é possível resolver a equação (vetorial) A * x = bmultiplicando à esquerda ambos os lados pelo inverso de A: (nas linguagens MATLAB e GNU Octave : ). As seguintes afirmações matemáticas são válidas quando é uma matriz quadrada de classificação completa :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b( associatividade de multiplicação de matriz ) x = A^-1 * b
onde ==é o operador relacional de equivalência . As declarações anteriores também são expressões MATLAB válidas se a terceira for executada antes das outras (as comparações numéricas podem ser falsas devido a erros de arredondamento).
Se o sistema for sobredeterminado - de modo que Atenha mais linhas do que colunas - o pseudoinverso (nas linguagens MATLAB e GNU Octave:) pode substituir o inverso , da seguinte maneira:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(associatividade de multiplicação de matriz) x = pinv(A) * b
No entanto, essas soluções não são nem as mais concisas (por exemplo, ainda resta a necessidade de diferenciar notacionalmente os sistemas sobredeterminados) nem as mais eficientes do ponto de vista computacional. O último ponto é fácil de entender quando se considera novamente o equivalente escalar a * x = b, para o qual a solução x = a^-1 * bexigiria duas operações em vez da mais eficiente x = b / a. O problema é que geralmente as multiplicações da matriz não são comutativas, pois a extensão da solução escalar para o caso da matriz exigiria:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(a comutatividade não é válida para matrizes!) -
x * (a / a)==b / a(associatividade também é válida para matrizes) x = b / a
A linguagem MATLAB introduz o operador de divisão à esquerda \para manter a parte essencial da analogia com o caso escalar, simplificando assim o raciocínio matemático e preservando a concisão:
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(a associatividade também é válida para matrizes, a comutatividade não é mais necessária) x = A \ b
Este não é apenas um exemplo de programação de array concisa do ponto de vista da codificação, mas também da perspectiva da eficiência computacional, que em várias linguagens de programação de array se beneficia de bibliotecas de álgebra linear bastante eficientes, como ATLAS ou LAPACK .
Voltando à citação anterior de Iverson, a razão por trás disso agora deve ser evidente:
é importante distinguir a dificuldade de descrever e aprender uma parte da notação da dificuldade de dominar suas implicações. Por exemplo, aprender as regras para calcular um produto de matriz é fácil, mas o domínio de suas implicações (como sua associatividade, sua distributividade sobre a adição e sua capacidade de representar funções lineares e operações geométricas) é uma questão diferente e muito mais difícil . Na verdade, a própria sugestividade de uma notação pode torná-la mais difícil de aprender por causa das muitas propriedades que sugere para explorações.
Bibliotecas de terceiros
O uso de bibliotecas especializadas e eficientes para fornecer abstrações mais concisas também é comum em outras linguagens de programação. Em C ++, várias bibliotecas de álgebra linear exploram a capacidade da linguagem de sobrecarregar os operadores . Em alguns casos, uma abstração muito concisa nessas linguagens é explicitamente influenciada pelo paradigma de programação de array, como fazem as bibliotecas Armadillo e Blitz ++ .
