Tömb programozás - Array programming
A számítástechnika , tömbprogramozással utal megoldásokat, amelyek lehetővé teszik az alkalmazást műveletek egy egész sor értékek egyszerre. Az ilyen megoldásokat gyakran használják tudományos és mérnöki környezetben.
A tömb programozást támogató modern programozási nyelveket (más néven vektoros vagy többdimenziós nyelveket) kifejezetten a skaláris műveletek általánosítására tervezték, hogy átláthatóan alkalmazzák a vektorokra , mátrixokra és magasabb dimenziós tömbökre. Ezek közé tartozik az APL , J , Fortran 90 , MATLAB , Analytica , TK Solver ( listaként ), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) és a Python NumPy kiterjesztése . Ezeken a nyelveken műveletet, hogy működik a teljes tömböt lehet nevezni vektorizált működését, függetlenül attól, hogy végre egy vektor processzor , amely végrehajtja vektor utasításokat. A tömb programozási primitívek tömören fogalmaznak meg széles körű elképzeléseket az adatkezeléssel kapcsolatban. A konklúzió mértéke bizonyos esetekben drámai lehet: nem ritka, hogy tömb programozási nyelvű egysorosokat találunk , amelyek több oldalas objektum-orientált kódot igényelnek.
A tömb fogalmai
A tömbprogramozás alapgondolata az, hogy a műveletek egyszerre vonatkoznak egy egész értékkészletre. Ez egy magas szintű programozási modellt tesz lehetővé, mivel lehetővé teszi a programozó számára, hogy teljes adathalmazokon gondolkodjon és működjön, anélkül, hogy az egyes skaláris műveletek kifejezett hurkaihoz kellene folyamodnia.
Kenneth E. Iverson a következőképpen írta le a tömbprogramozás (valójában az APL -re utaló) indoklását:
a legtöbb programozási nyelv határozottan rosszabb a matematikai jelöléseknél, és kevéssé használják gondolati eszközként olyan módon, amelyet mondjuk egy alkalmazott matematikus jelentősnek tartana.
A tézis az, hogy a programozási nyelvekben megtalálható végrehajthatósági és egyetemességi előnyök hatékonyan kombinálhatók egyetlen összefüggő nyelven, a matematikai jelölés előnyeivel. fontos megkülönböztetni a jelölés leírásának és elsajátításának nehézségeit a következmények elsajátításának nehézségétől. Például egy mátrixtermék kiszámításának szabályainak megtanulása egyszerű, de következményeinek (például asszociativitásának, összeadáson való eloszlásának és lineáris függvények és geometriai műveletek képességének) elsajátítása más és sokkal nehezebb kérdés .
Valóban, egy jelölés önmagában való szuggesztivitása miatt a tanulás nehezebbnek tűnhet, mivel sok olyan tulajdonságot ajánl, amelyet felfedezésre javasol.
[...]
A számítógépek és a programozási nyelvek használói gyakran elsősorban az algoritmusok végrehajtásának hatékonyságával foglalkoznak, és ezért az itt bemutatott algoritmusok közül sokat összefoglalóan elvethetnek. Az ilyen elbocsátás rövidlátó lenne, mivel egy algoritmus egyértelmű kijelentése általában alapul szolgálhat, amelyből könnyen le lehet vezetni egy hatékonyabb algoritmust.
A tömb programozás és gondolkodás alapja az adatok tulajdonságainak megtalálása és kiaknázása, ahol az egyes elemek hasonlóak vagy szomszédosak. Ellentétben az objektum -orientációval, amely implicit módon lebontja az adatokat az alkotóelemeire (vagy skaláris mennyiségekre), a tömb -orientáció az adatok csoportosítására törekszik , és egységes kezelést alkalmaz.
A függvény rangsor fontos fogalom a programozási nyelvek tömbjében általában, a matematika tenzor rangjához hasonlóan : az adatokon működő függvények osztályozhatók az általuk gyakorolt dimenziók száma alapján. A közönséges szorzás például skaláris rangsorolású függvény, mivel nulla dimenziós adatokon (egyedi számokon) működik. A kereszttermék művelet egy példa a vektor rang függvényére, mivel vektorokon működik, nem skalárokon. A mátrixszorzás egy példa a 2 rangú függvényre, mivel 2 dimenziós objektumokon (mátrixokon) működik. Az összecsukási operátorok egy vagy több dimenzióval csökkentik a bemeneti adattömb méretét. Például az elemek összegzése összecsukja a bemeneti tömböt 1 dimenzióval.
Felhasználások
A tömb programozás nagyon jól illeszkedik az implicit párhuzamosításhoz ; manapság sok kutatási téma. Továbbá az 1997 után kifejlesztett és gyártott Intel és kompatibilis CPU -k különféle utasításkészleteket tartalmaztak, kezdve az MMX -től az SSSE3 és 3DNow! , amelyek kezdetleges SIMD tömb képességeket tartalmaznak. A tömbfeldolgozás abban különbözik a párhuzamos feldolgozástól , hogy egy fizikai processzor egyidejűleg hajt végre műveleteket egy elemcsoporton, míg a párhuzamos feldolgozás célja egy nagyobb probléma kisebbekre bontása ( MIMD ), amelyeket számos processzor darabonként megold. Manapság egyre gyakoribbak a két vagy több magos processzorok.
Nyelvek
A kanonikus példái tömbprogramozással nyelvek Fortran , APL , és J . Egyéb: A+ , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL és TI-BASIC .
Skaláris nyelvek
A skalár nyelvekben, mint például a C és a Pascal , a műveletek csak egyetlen értékre vonatkoznak, így a + b két szám összeadását fejezi ki. Ilyen nyelvekben az egyik tömb hozzáadása a másikhoz indexelést és ciklusozást igényel, amelynek kódolása unalmas.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
A tömb-alapú nyelvekben, például a Fortranban, a fenti beágyazott for-ciklus tömbformátumban írható egy sorba,
a = a + b
vagy alternatívaként az objektumok tömbjellegének hangsúlyozására,
a(:,:) = a(:,:) + b(:,:)
Míg a skaláris nyelvek, mint például a C, nem rendelkeznek natív tömb programozási elemekkel a megfelelő nyelv részeként, ez nem jelenti azt, hogy az ezeken a nyelveken írt programok soha nem használják ki a vektorizálás alapjául szolgáló technikákat (azaz a CPU vektor-alapú utasításainak felhasználását, ha van ilyen) vagy több CPU mag használatával). Egyes C -fordítók, például a GCC bizonyos optimalizálási szinteken észlelik és vektorizálják a kód azon részeit, amelyek heurisztikája szerint hasznot húznak belőle. Egy másik megközelítést kínál az OpenMP API, amely lehetővé teszi, hogy párhuzamba állítsuk az alkalmazandó kódrészleteket a több CPU -mag kihasználásával.
Tömbnyelvek
A tömbnyelvekben a műveletek általánosak, és mind a skalárokra, mind a tömbökre vonatkoznak. Így az a + b két skalár összegét fejezi ki, ha a és b skalár, vagy két tömb összegét, ha tömbök.
A tömbnyelv leegyszerűsíti a programozást, de esetleg absztrakciós büntetésként ismert költséggel . Mivel a kiegészítéseket a kódolás többi részétől elkülönítve hajtják végre, előfordulhat, hogy nem hozzák létre az optimálisan leghatékonyabb kódot. (Például ugyanazon tömb más elemeinek hozzáadása később is előfordulhat ugyanazon végrehajtás során, ami szükségtelen ismételt kereséseket okozhat.) Még a legkifinomultabb optimalizáló fordítónak is rendkívül nehéz lenne összevonni két vagy több látszólag eltérő funkciót, amelyek megjelenhetnek a különbözõ programrészek vagy alrutinok, annak ellenére, hogy egy programozó ezt könnyedén megtehetné, összesítheti az összegeket ugyanazon a passzuson a tömbön a minimális rezsicsökkentés érdekében ).
Ada
A korábbi C kód a következő lesz az Ada nyelvben, amely támogatja a tömb programozási szintaxist.
A := A + B;
APL
Az APL egy karakteres Unicode szimbólumokat használ szintaktikai cukor nélkül.
A ← A + B
Ez a művelet bármilyen rangú tömbön (beleértve a 0 rangot is), valamint skaláron és tömbön működik. A Dyalog APL kiterjeszti az eredeti nyelvet kibővített hozzárendelésekkel :
A +← B
Analytica
Az Analytica ugyanazt a kifejezési gazdaságosságot biztosítja, mint az Ada.
A := A + B;
ALAPVETŐ
A Dartmouth BASIC harmadik kiadása (1966) tartalmazott MAT utasításokat a mátrix és tömb manipulációra vonatkozóan.
DIM A(4),B(4),C(4)
MAT A = 1
MAT B = 2 * A
MAT C = A + B
MAT PRINT A,B,C
Mata
A Stata mátrix programozási nyelve A Mata támogatja a tömb programozást. Az alábbiakban szemléltetjük az összeadást, a szorzást, a mátrix és a skalár összeadását, az elemenkénti szorzást, az aláírást és a Mata számos inverz mátrixfüggvényét.
. 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 MATLAB megvalósítása ugyanazt a gazdaságosságot teszi lehetővé a Fortran nyelv használatával.
A = A + B;
A MATLAB nyelv egyik változata a GNU Octave nyelv, amely kiterjeszti az eredeti nyelvet kibővített hozzárendelésekkel:
A += B;
Mind a MATLAB, mind a GNU Octave natív módon támogatja a lineáris algebra műveleteket, például a mátrixszorzást, a mátrix inverziót és a lineáris egyenletrendszer numerikus megoldását , még a Moore – Penrose pszeudoinverz alkalmazásával is .
A két tömb belső termékének Nial példája a natív mátrixszorzási operátorral valósítható meg. Ha aegy [1 n] méretű sorvektor, és begy megfelelő [n 1] méretű oszlopvektor.
a * b;
Az azonos számú elemet tartalmazó mátrix közötti belső termék megvalósítható a segédoperátorral (:), amely egy adott mátrixot oszlopvektorrá alakít át, és a transzponáló operátorral ':
A(:)' * B(:);
rasql
A rasdaman lekérdezési nyelv egy adatbázis-orientált tömb-programozási nyelv. Például két tömböt lehet hozzáadni a következő lekérdezéssel:
SELECT A + B
FROM A, B
R
Az R nyelvet támogat tömb paradigma alapértelmezés szerint. A következő példa két mátrix szorzási folyamatát szemlélteti, amelyet egy skalár (ami valójában egy elemű vektor) és egy vektor hozzáadása követ:
> 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
Matematikai érvelés és nyelvi jelölés
A mátrix balosztásos operátora tömören kifejezi a mátrixok néhány szemantikai tulajdonságát. Ahogy a skalár egyenértékű, ha a ( meghatározó a) együttható (mátrix) Anem nulla, akkor lehetőség van arra, hogy megoldja a (vektoriális) egyenlet A * x = báltal hagyott megszorozzuk mindkét fél által fordított a A: (mind MATLAB és a GNU Octave nyelv : ). A következő matematikai állítások tartani, ha egy teljes rangú négyzetes mátrix :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b(mátrix-szorzás asszociativitás ) x = A^-1 * b
hol ==van az ekvivalencia relációs operátor . Az előző állítások szintén érvényes MATLAB kifejezések, ha a harmadikat a többiek előtt hajtják végre (a számszerű összehasonlítások hamisak lehetnek a kerekítési hibák miatt).
Ha a rendszer túldeterminált - tehát Atöbb sora van, mint oszlopa -, az ál -inverz (MATLAB és GNU Octave nyelveken :) helyettesítheti az inverzt , az alábbiak szerint:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(mátrix-szorzás asszociativitás) x = pinv(A) * b
Ezek a megoldások azonban nem a legkonkrétabbak (pl. Továbbra is fennáll az igény az előre meghatározott rendszerek jelölés szerinti megkülönböztetésére), és nem a leghatékonyabbak a számítás szempontjából. Ez utóbbi pont könnyen érthető, ha újra figyelembe vesszük a skalár megfelelőjét a * x = b, amelyhez a megoldás x = a^-1 * bkét műveletet igényelne a hatékonyabb helyett x = b / a. A probléma az, hogy a mátrixszorzások általában nem kommutatívak, mivel a skaláris megoldás kiterjesztése a mátrix esetre megkövetelné:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(a kommutativitás nem vonatkozik a mátrixokra!) -
x * (a / a)==b / a(az asszociativitás a mátrixokra is érvényes) x = b / a
A MATLAB nyelv bevezeti a balosztály operátort, \hogy fenntartsa a skaláris esettel való analógia lényeges részét, egyszerűsítve ezzel a matematikai érvelést és megőrizve a tömörséget:
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(az asszociativitás a mátrixokra is érvényes, a kommutativitásra már nincs szükség) x = A \ b
Ez nemcsak példa a tömör tömb programozására a kódolás szempontjából, hanem a számítási hatékonyság szempontjából is, amely számos tömb programozási nyelven részesül az olyan hatékony lineáris algebrai könyvtárakból, mint az ATLAS vagy a LAPACK .
Visszatérve Iverson előző idézetére, e mögött rejlő indokoknak nyilvánvalónak kell lenniük:
fontos megkülönböztetni a jelölés leírásának és elsajátításának nehézségeit a következmények elsajátításának nehézségétől. Például egy mátrixtermék kiszámításának szabályainak megtanulása egyszerű, de következményeinek (például asszociativitásának, összeadáson való eloszlásának és lineáris függvények és geometriai műveletek képességének) elsajátítása más és sokkal nehezebb kérdés . Valóban, egy jelölés önmagában való szuggesztivitása miatt nehezebbnek tűnhet a tanulás, mivel sok olyan tulajdonságot ajánl, amelyet felfedezésre javasol.
Harmadik féltől származó könyvtárak
A speciális és hatékony könyvtárak használata tömörebb absztrakciók biztosítására más programozási nyelveken is gyakori. A C ++ nyelvben több lineáris algebra könyvtár kihasználja a nyelv azon képességét, hogy túlterheli az operátorokat . Bizonyos esetekben egy nagyon szűk absztrakciót ezeken a nyelveken kifejezetten befolyásol a tömb programozási paradigma, mint az Armadillo és a Blitz ++ könyvtárak.
