Programowanie tablicowe - Array programming
W informatyce , programowanie tablica odnosi się do rozwiązań, które pozwalają na stosowanie operacji do całego zbioru wartości na raz. Takie rozwiązania są powszechnie stosowane w środowisku naukowym i inżynieryjnym .
Nowoczesne języki programowania, które obsługują programowanie tablicowe (znane również jako języki wektorowe lub wielowymiarowe ), zostały zaprojektowane specjalnie w celu uogólnienia operacji na skalarach w celu przezroczystego zastosowania do wektorów , macierzy i tablic wyższych wymiarów. Należą do nich APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (jako listy), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) oraz rozszerzenie NumPy do Pythona . W tych językach operację operującą na całych tablicach można nazwać operacją wektoryzowaną , niezależnie od tego, czy jest wykonywana na procesorze wektorowym , który implementuje instrukcje wektorowe. Prymitywy programowania tablicowego zwięźle wyrażają szerokie koncepcje dotyczące manipulacji danymi. Poziom zwięzłości mogą być dramatyczne w niektórych przypadkach: to nie jest rzadkością, aby znaleźć język programowania tablica jednej wkładki , które wymagają kilku stron kodu obiektowego.
Koncepcje tablicy
Podstawową ideą programowania tablicowego jest to, że operacje dotyczą od razu całego zestawu wartości. To sprawia, że jest to model programowania wysokiego poziomu, ponieważ pozwala programiście myśleć i operować na całych agregatach danych, bez konieczności uciekania się do jawnych pętli pojedynczych operacji skalarnych.
Kenneth E. Iverson opisał przesłanki stojące za programowaniem tablicowym (właściwie odnosząc się do APL) w następujący sposób:
większość języków programowania jest zdecydowanie gorsza od notacji matematycznej i jest mało używana jako narzędzia myślenia w sposób, który byłby uznany za istotny przez, powiedzmy, matematyka stosowanego.
Postawiono tezę, że zalety wykonalności i uniwersalności występujące w językach programowania można skutecznie połączyć, w jednym spójnym języku, z zaletami oferowanymi przez notację matematyczną. ważne jest, aby odróżnić trudność opisywania i uczenia się fragmentu notacji od trudności w opanowaniu jego implikacji. Na przykład nauczenie się zasad obliczania iloczynu macierzowego jest łatwe, ale opanowanie jego implikacji (takich jak asocjatywność, rozdzielność względem dodawania oraz jego zdolność do reprezentowania funkcji liniowych i operacji geometrycznych) jest inną i znacznie trudniejszą sprawą .
Rzeczywiście, sama sugestywność zapisu może sprawiać, że nauka może wydawać się trudniejsza ze względu na wiele właściwości, które sugeruje dla eksploracji.
[...]
Użytkownicy komputerów i języków programowania są często zainteresowani przede wszystkim wydajnością wykonywania algorytmów i dlatego mogą w skrócie odrzucić wiele z przedstawionych tutaj algorytmów. Takie zwolnienie byłoby krótkowzroczne, ponieważ jasne określenie algorytmu może zwykle służyć jako podstawa, z której można łatwo wyprowadzić bardziej wydajny algorytm.
Podstawą programowania i myślenia tablicowego jest znalezienie i wykorzystanie właściwości danych, w których poszczególne elementy są podobne lub sąsiadujące. W przeciwieństwie do orientacji obiektowej, która niejawnie rozkłada dane na części składowe (lub wielkości skalarne ), orientacja tablicowa polega na grupowaniu danych i stosowaniu jednolitej obsługi.
Ranga funkcji jest ważnym pojęciem dla tablicowych języków programowania w ogóle, przez analogię do rangi tensorów w matematyce: funkcje operujące na danych mogą być klasyfikowane według liczby wymiarów, na których działają. Na przykład mnożenie zwykłe jest skalarną funkcją rangowaną, ponieważ działa na danych zerowymiarowych (pojedynczych liczb). Operacja iloczynu krzyżowego jest przykładem funkcji rang wektora, ponieważ działa na wektorach, a nie na skalarach. Mnożenie macierzy jest przykładem funkcji dwurzędowej, ponieważ operuje ona na obiektach dwuwymiarowych (macierzach). Operatory zwijania zmniejszają wymiarowość tablicy danych wejściowych o jeden lub więcej wymiarów. Na przykład sumowanie po elementach zwija tablicę wejściową o 1 wymiar.
Zastosowania
Programowanie tablicowe jest bardzo dobrze przystosowane do niejawnej paralelizacji ; tematem wielu badań w dzisiejszych czasach. Co więcej, procesory Intel i kompatybilne procesory opracowane i wyprodukowane po 1997 roku zawierały różne rozszerzenia zestawu instrukcji, począwszy od MMX, a skończywszy na SSSE3 i 3DNow! , które obejmują podstawowe możliwości macierzy SIMD . Przetwarzanie tablicowe różni się od przetwarzania równoległego tym, że jeden procesor fizyczny wykonuje operacje na grupie elementów jednocześnie, podczas gdy przetwarzanie równoległe ma na celu rozbicie większego problemu na mniejsze ( MIMD ), które rozwiązuje się fragmentarycznie przez wiele procesorów. Procesory z dwoma lub więcej rdzeniami są dziś coraz bardziej popularne.
Języki
Kanoniczne przykłady języków programowania tablicowego to Fortran , APL i J . Inne to: A+ , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL i TI-BASIC .
Języki skalarne
W językach skalarnych, takich jak C i Pascal , operacje dotyczą tylko pojedynczych wartości, więc a + b wyraża dodanie dwóch liczb. W takich językach dodawanie jednej tablicy do drugiej wymaga indeksowania i zapętlania, których kodowanie jest żmudne.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
W językach opartych na tablicach, na przykład w Fortran, zagnieżdżona pętla for powyżej może być zapisana w formacie tablicy w jednym wierszu,
a = a + b
lub alternatywnie, aby podkreślić tablicowy charakter obiektów,
a(:,:) = a(:,:) + b(:,:)
Chociaż języki skalarne, takie jak C, nie mają elementów programowania tablic natywnych jako części właściwego języka, nie oznacza to, że programy napisane w tych językach nigdy nie wykorzystują podstawowych technik wektoryzacji (tj. wykorzystują instrukcje wektorowe procesora, jeśli je lub przy użyciu wielu rdzeni procesora). Niektóre kompilatory C, takie jak GCC, na niektórych poziomach optymalizacji wykrywają i wektoryzują sekcje kodu, które według heurystyki mogą na tym skorzystać. Innym podejściem jest API OpenMP , które pozwala na zrównoleglenie odpowiednich sekcji kodu, wykorzystując wiele rdzeni procesora.
Języki tablic
W językach tablicowych operacje są uogólnione tak, aby miały zastosowanie zarówno do skalarów, jak i tablic. Zatem a + b wyraża sumę dwóch skalarów, jeśli a i b są skalarami, lub sumę dwóch tablic, jeśli są tablicami.
Język tablicowy upraszcza programowanie, ale prawdopodobnie wiąże się to z kosztem znanym jako kara za abstrakcję . Ponieważ dodatki są wykonywane w oderwaniu od reszty kodu, mogą nie dawać optymalnie najbardziej wydajnego kodu. (Na przykład, podczas tego samego wykonania mogą pojawić się dodawanie innych elementów tej samej tablicy, powodując niepotrzebne powtarzające się wyszukiwania.) Nawet najbardziej wyrafinowany kompilator optymalizujący miałby niezwykle trudne połączenie dwóch lub więcej pozornie odmiennych funkcji, które mogą pojawić się w różne sekcje programu lub podprogramy, nawet jeśli programista mógłby to zrobić łatwo, agregując sumy w tym samym przejściu przez tablicę, aby zminimalizować obciążenie ).
Ada
Poprzedni kod C stałby się następujący w języku Ada , który obsługuje składnię programowania tablic.
A := A + B;
APL
APL używa jednoznakowych symboli Unicode bez cukru składniowego.
A ← A + B
Ta operacja działa na tablicach o dowolnej randze (w tym o randze 0) oraz na skalarze i tablicy. Dyalog APL rozszerza oryginalny język o rozszerzone przypisania :
A +← B
Analityka
Analytica zapewnia taką samą ekonomię wyrazu jak Ada.
A := A + B;
PODSTAWOWY
Dartmouth BASIC miał instrukcje MAT do manipulacji macierzą i tablicami w swoim trzecim wydaniu (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
Język programowania macierzy Stata Mata obsługuje programowanie macierzy. Poniżej ilustrujemy dodawanie, mnożenie, dodawanie macierzy i skalara, mnożenie element po elemencie, indeksowanie i jedną z wielu funkcji macierzy odwrotnych Maty.
. 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
Implementacja w MATLAB pozwala na tę samą ekonomię, na jaką pozwala język Fortran.
A = A + B;
Wariantem języka MATLAB jest język GNU Octave , który rozszerza język oryginalny o rozszerzone zadania:
A += B;
Zarówno MATLAB, jak i GNU Octave natywnie obsługują operacje algebry liniowej, takie jak mnożenie macierzy, odwracanie macierzy i numeryczne rozwiązywanie układu równań liniowych , nawet przy użyciu pseudoodwrotności Moore'a-Penrose'a .
Nial przykład wewnętrznej iloczyn dwóch macierzy mogą być realizowane z wykorzystaniem natywnych mnożenia macierzy. If ajest wektorem wierszowym o rozmiarze [1 n] i bjest odpowiednim wektorem kolumnowym o rozmiarze [n 1].
a * b;
Iloczyn skalarny między dwiema macierzami o tej samej liczbie elementów można zaimplementować operatorem pomocniczym (:), który przekształca daną macierz w wektor kolumnowy oraz operatorem transpozycji' :
A(:)' * B(:);
rasql
Język zapytań rasdaman to język programowania baz danych macierz zorientowanych. Na przykład dwie tablice można dodać za pomocą następującego zapytania:
SELECT A + B
FROM A, B
r
Język R domyślnie obsługuje paradygmat tablicowy . Poniższy przykład ilustruje proces mnożenia dwóch macierzy, po którym następuje dodanie skalara (który w rzeczywistości jest wektorem jednoelementowym) i wektora:
> 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
Rozumowanie matematyczne i notacja językowa
Operator dzielenia po lewej stronie macierz zwięźle wyraża niektóre właściwości semantyczne macierzy. Podobnie jak w równoważnej skalarnym, jeżeli ( determinanta z) współczynnik (matryca) Anie jest NULL to można rozwiązać równanie (wektorowe) A * x = bod lewej pomnożenie obu stron przez odwrotność z A: (w obu językach MATLAB GNU Octave : ). Następujące zdania matematyczne mają zastosowanie, gdy jest macierzą kwadratową pełnego rzędu :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b( skojarzenie mnożenia macierzy ) x = A^-1 * b
gdzie ==jest operatorem relacyjnym równoważności . Poprzednie instrukcje są również poprawnymi wyrażeniami MATLAB, jeśli trzecia jest wykonywana przed innymi (porównania liczbowe mogą być fałszywe z powodu błędów zaokrągleń).
Jeśli system jest przedefiniowany – czyli Ama więcej wierszy niż kolumn – pseudoodwrotność (w językach MATLAB i GNU Octave: ) może zastąpić odwrotność w następujący sposób:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(skojarzenie z mnożeniem macierzy) x = pinv(A) * b
Jednak rozwiązania te nie są ani najbardziej zwięzłymi (np. nadal pozostaje potrzeba notacyjnego zróżnicowania systemów naddeterminowanych), ani też najbardziej wydajnymi obliczeniowo. Ten ostatni punkt jest łatwy do zrozumienia, gdy ponownie rozważymy ekwiwalent skalarny a * x = b, dla którego rozwiązanie x = a^-1 * bwymagałoby dwóch operacji zamiast bardziej wydajnej x = b / a. Problem polega na tym, że generalnie mnożenia macierzy nie są przemienne, ponieważ rozszerzenie rozwiązania skalarnego na przypadek macierzy wymagałoby:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(przemienność nie dotyczy macierzy!) -
x * (a / a)==b / a(łączność obowiązuje również dla macierzy) x = b / a
Język MATLAB wprowadza operator dzielenia lewostronnego, \aby zachować zasadniczą część analogii ze skalarnym przypadkiem, upraszczając w ten sposób rozumowanie matematyczne i zachowując zwięzłość:
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(łączność obowiązuje również dla macierzy, przemienność nie jest już wymagana) x = A \ b
Jest to nie tylko przykład zwięzłego programowania tablicowego z punktu widzenia kodowania, ale także z perspektywy wydajności obliczeniowej, która w kilku językach programowania tablicowego korzysta z całkiem wydajnych bibliotek algebry liniowej, takich jak ATLAS czy LAPACK .
Wracając do poprzedniego cytatu Iversona, uzasadnienie tego powinno być teraz oczywiste:
ważne jest, aby odróżnić trudność opisywania i uczenia się fragmentu notacji od trudności w opanowaniu jego implikacji. Na przykład nauczenie się zasad obliczania iloczynu macierzowego jest łatwe, ale opanowanie jego implikacji (takich jak asocjatywność, rozdzielność względem dodawania oraz jego zdolność do reprezentowania funkcji liniowych i operacji geometrycznych) jest inną i znacznie trudniejszą sprawą . Rzeczywiście, sama sugestywność zapisu może sprawiać, że nauka może wydawać się trudniejsza ze względu na wiele właściwości, które sugeruje dla eksploracji.
Biblioteki zewnętrzne
Korzystanie z wyspecjalizowanych i wydajnych bibliotek w celu zapewnienia bardziej zwięzłych abstrakcji jest również powszechne w innych językach programowania. W C++ kilka bibliotek algebry liniowej wykorzystuje zdolność języka do przeciążania operatorów . W niektórych przypadkach na bardzo zwięzłą abstrakcję w tych językach wyraźnie wpływa paradygmat programowania tablicowego, tak jak robią to biblioteki Armadillo i Blitz++ .