Array programmering - Array programming
I datalogi , vifte programmering refererer til løsninger, der tillader anvendelsen af operationer til et helt sæt af værdier på en gang. Sådanne løsninger bruges almindeligvis i videnskabelige og tekniske omgivelser.
Moderne programmeringssprog, der understøtter matrixprogrammering (også kendt som vektor- eller multidimensionelle sprog), er specielt konstrueret til at generalisere operationer på skalarer for at anvende transparent på vektorer , matricer og højere-dimensionelle arrays. Disse inkluderer APL , J , Fortran 90 , MATLAB , Analytica , TK Solver (som lister), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) og NumPy -udvidelsen til Python . På disse sprog kan en operation, der opererer på hele arrays, kaldes en vektoriseret operation, uanset om den udføres på en vektorprocessor , som implementerer vektorinstruktioner. Array programmerings primitiver udtrykker kortfattet brede ideer om datamanipulation. Konklusionsniveauet kan være dramatisk i visse tilfælde: Det er ikke ualmindeligt at finde array-programmeringssprog one-liners, der kræver flere sider med objektorienteret kode.
Begreber af array
Den grundlæggende idé bag arrayprogrammering er, at operationer på én gang gælder for et helt sæt værdier. Dette gør det til en programmeringsmodel på højt niveau , da det giver programmereren mulighed for at tænke og operere på hele datamængder uden at skulle ty til eksplicitte sløjfer af individuelle skalaroperationer.
Kenneth E. Iverson beskrev begrundelsen bag arrayprogrammering (faktisk henviser til APL) som følger:
de fleste programmeringssprog er decideret ringere end matematisk notation og bruges kun lidt som tankeværktøjer på måder, der ville blive betragtet som betydningsfulde af f.eks. en anvendt matematiker.
Tesen er, at fordelene ved eksekverbarhed og universalitet, der findes i programmeringssprog, effektivt kan kombineres i et enkelt sammenhængende sprog med fordelene ved matematisk notation. det er vigtigt at skelne mellem vanskeligheden ved at beskrive og lære et stykke notation fra vanskeligheden ved at mestre dens konsekvenser. For eksempel er det let at lære reglerne for beregning af et matrixprodukt, men det er en anden og meget vanskeligere sag at beherske dens konsekvenser (såsom dets associativitet, dens distributivitet over addition og dens evne til at repræsentere lineære funktioner og geometriske operationer) .
Selve suggestiviteten af en notation kan få det til at virke sværere at lære på grund af de mange egenskaber, det foreslår til udforskninger.
[...]
Brugere af computere og programmeringssprog er ofte primært bekymrede over effektiviteten af udførelsen af algoritmer og kan derfor summarisk afvise mange af de algoritmer, der præsenteres her. En sådan afskedigelse ville være kortsigtet, da en klar redegørelse for en algoritme normalt kan bruges som et grundlag, hvorfra man let kan udlede en mere effektiv algoritme.
Grundlaget bag matrixprogrammering og tænkning er at finde og udnytte egenskaberne af data, hvor individuelle elementer er ens eller tilstødende. I modsætning til objektorientering, der implicit nedbryder data til dets bestanddele (eller skalarmængder ), ser matrixorientering ud til at gruppere data og anvende en ensartet håndtering.
Funktionsrangering er et vigtigt begreb for at matche programmeringssprog generelt, analogt med tensorrang i matematik: funktioner, der fungerer på data, kan klassificeres efter antallet af dimensioner, de virker på. Almindelig multiplikation er f.eks. En skalærrangeret funktion, fordi den fungerer på nul-dimensionelle data (individuelle tal). Den tværs af produkter operation er et eksempel på en vektor rang funktion, fordi det virker på vektorer, ikke skalarer. Matrixmultiplikation er et eksempel på en 2-rangs funktion, fordi den opererer på 2-dimensionelle objekter (matricer). Skjul operatører reducerer dimensionaliteten af et inputdatamatrix med en eller flere dimensioner. Eksempelvis kollapser summering over elementer inputmatrixen med 1 dimension.
Anvendelser
Array programmering er meget velegnet til implicit parallelisering ; et emne for meget forskning i dag. Desuden indeholdt Intel og kompatible CPU'er udviklet og produceret efter 1997 forskellige udvidelser af instruktionssæt, startende fra MMX og fortsatte gennem SSSE3 og 3DNow! , som inkluderer rudimentære SIMD -arrayfunktioner . Arraybehandling adskiller sig fra parallelbehandling ved, at en fysisk processor udfører operationer på en gruppe emner samtidigt, mens parallelbehandling sigter mod at opdele et større problem i mindre ( MIMD ), der skal løses stykkevis af adskillige processorer. Processorer med to eller flere kerner er mere og mere almindelige i dag.
Sprog
De kanoniske eksempler på række programmeringssprog er Fortran , APL , og J. . Andre omfatter: A+ , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL og TI-BASIC .
Skalære sprog
I skalarsprog som C og Pascal gælder operationer kun for enkeltværdier, så a + b udtrykker tilføjelsen af to tal. På sådanne sprog kræver tilføjelse af et array til et andet indeksering og looping, hvis kodning er kedelig.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
På array-baserede sprog, for eksempel i Fortran, kan den indlejrede for-loop ovenfor skrives i array-format i en linje,
a = a + b
eller alternativt for at understrege objekternes array -karakter,
a(:,:) = a(:,:) + b(:,:)
Selvom skalarsprog som C ikke har native array-programmeringselementer som en del af det korrekte sprog, betyder det ikke, at programmer, der er skrevet på disse sprog, aldrig drager fordel af de underliggende teknikker til vektorisering (dvs. at anvende en CPUs vektorbaserede instruktioner, hvis det har dem eller ved hjælp af flere CPU -kerner). Nogle C -kompilatorer som GCC ved nogle optimeringsniveauer registrerer og vektoriserer kodesnit, som dens heuristik bestemmer, ville have gavn af det. En anden tilgang er givet ved OpenMP API, som gør det muligt at parallelisere gældende sektioner af kode ved at drage fordel af flere CPU -kerner.
Array sprog
I array -sprog generaliseres operationer til at gælde for både skalarer og arrays. Således udtrykker a + b summen af to skalarer, hvis a og b er skalarer, eller summen af to arrays, hvis de er arrays.
Et array -sprog forenkler programmering, men muligvis til en pris kendt som abstraktionsstraffen . Fordi tilføjelserne udføres isoleret fra resten af kodningen, producerer de muligvis ikke den optimalt mest effektive kode. (F.eks. Kan tilføjelser af andre elementer i det samme array efterfølgende stødes på under den samme udførelse, hvilket forårsager unødvendige gentagne opslag.) Selv den mest sofistikerede optimeringskompiler ville have ekstremt svært ved at samle to eller flere tilsyneladende forskellige funktioner, som kan forekomme i forskellige programsektioner eller sub-rutiner, selvom en programmør let kunne gøre dette, og aggregerede summer på samme passerer over arrayet for at minimere omkostninger ).
Ada
Den tidligere C-kode ville blive følgende i Ada- sproget, som understøtter array-programmeringssyntaks.
A := A + B;
APL
APL bruger Unicode -symboler med et enkelt tegn uden syntaktisk sukker.
A ← A + B
Denne operation fungerer på arrays af enhver rang (inklusive rang 0) og på en skalar og et array. Dyalog APL udvider originalsproget med udvidede opgaver :
A +← B
Analytica
Analytica giver den samme udtryksøkonomi som Ada.
A := A + B;
GRUNDLÆGGENDE
Dartmouth BASIC havde MAT -sætninger til matrix- og arraymanipulation i sin tredje udgave (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
Statas matrixprogrammeringssprog Mata understøtter arrayprogrammering. Nedenfor illustrerer vi addition, multiplikation, tilføjelse af en matrix og en skalar, element for element multiplikation, subscripting og en af Matas mange inverse matrixfunktioner.
. 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
Implementeringen i MATLAB tillader den samme økonomi tilladt ved at bruge Fortran -sproget.
A = A + B;
En variant af MATLAB -sproget er GNU Octave -sproget, som udvider originalsproget med udvidede opgaver:
A += B;
Både MATLAB og GNU Octave understøtter indbygget lineære algebraoperationer såsom matrixmultiplikation, matrixinversion og den numeriske løsning af system af lineære ligninger , selv ved at bruge Moore -Penrose pseudoinverse .
Den Nial eksempel på det indre produkt af to arrays kan implementeres ved hjælp af den native matrix multiplikation operatør. If aer en rækkevektor af størrelse [1 n] og ber en tilsvarende kolonnevektor med størrelse [n 1].
a * b;
Det indre produkt mellem to matricer med samme antal elementer kan implementeres med den ekstra operatør (:), som omformer en given matrix i en søjle vektor og den transponerede operatør ':
A(:)' * B(:);
rasql
Den rasdaman query sprog er en database-orienteret vifte-programmeringssprog. F.eks. Kan der tilføjes to arrays med følgende forespørgsel:
SELECT A + B
FROM A, B
R
R -sproget understøtter som standard array -paradigme . Det følgende eksempel illustrerer en multiplikationsproces af to matricer efterfulgt af en tilføjelse af en skalar (som faktisk er en etelementvektor) og en vektor:
> 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
Matematisk begrundelse og sprognotation
Matrix venstre-divisionsoperatøren udtrykker kortfattet nogle semantiske egenskaber ved matricer. Som i skalarækvivalenten, hvis ( determinant for) koefficienten (matrixen) Aikke er nul, er det muligt at løse (vektorial) ligningen A * x = bved at multiplicere begge sider med inversen af A: (i både MATLAB og GNU Octave sprog : ). Følgende matematiske udsagn holder, når er en kvadratmatrix med fuld rang :
A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)-
(A^-1 * A)* x ==A^-1 * b(matrix-multiplikation associativitet ) x = A^-1 * b
hvor ==er ækvivalens relationel operatør . De tidligere udsagn er også gyldige MATLAB-udtryk, hvis den tredje udføres før de andre (numeriske sammenligninger kan være falske på grund af afrundingsfejl).
Hvis systemet er overbestemt - så det Ahar flere rækker end kolonner - kan pseudoinverse (på MATLAB og GNU Octave sprog :) erstatte det inverse som følger:
A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)-
(pinv(A) * A)* x ==pinv(A) * b(matrix-multiplikationsassociativitet) x = pinv(A) * b
Disse løsninger er imidlertid hverken de mest kortfattede (f.eks. Er det stadig behovet for notationelt at differentiere overbestemte systemer) eller de mest beregningsmæssigt effektive. Sidstnævnte punkt er let at forstå, når man igen overvejer skalarækvivalenten a * x = b, for hvilken løsningen x = a^-1 * bville kræve to operationer i stedet for den mere effektive x = b / a. Problemet er, at matrixmultiplikationer generelt ikke er kommutative, da udvidelsen af skalarløsningen til matrixhuset ville kræve:
(a * x)/ a ==b / a-
(x * a)/ a ==b / a(kommutativitet gælder ikke for matricer!) -
x * (a / a)==b / a(associativitet gælder også for matricer) x = b / a
MATLAB-sproget introducerer venstre-divisionsoperatøren \til at bevare den væsentlige del af analogien med skalar-sagen, hvilket forenkler den matematiske begrundelse og bevarer den korte:
A \ (A * x)==A \ b-
(A \ A)* x ==A \ b(associativitet gælder også for matricer, kommutativitet er ikke mere påkrævet) x = A \ b
Dette er ikke kun et eksempel på kortfattet matrixprogrammering ud fra kodningssynspunktet, men også fra beregningseffektivitetsperspektivet, som i flere array -programmeringssprog drager fordel af ganske effektive lineære algebra -biblioteker som ATLAS eller LAPACK .
Når vi vender tilbage til det tidligere citat af Iverson, bør begrundelsen bag det nu være tydelig:
det er vigtigt at skelne mellem vanskeligheden ved at beskrive og lære et stykke notation fra vanskeligheden ved at mestre dens konsekvenser. For eksempel er det let at lære reglerne for beregning af et matrixprodukt, men en beherskelse af dets implikationer (såsom dets associativitet, dets distributivitet over addition og dets evne til at repræsentere lineære funktioner og geometriske operationer) er en anden og meget vanskeligere sag . Selve suggestiviteten af en notation kan få det til at virke sværere at lære på grund af de mange egenskaber, det foreslår til udforskninger.
Tredjepartsbiblioteker
Brugen af specialiserede og effektive biblioteker til at levere mere snævre abstraktioner er også almindelig i andre programmeringssprog. I C ++ udnytter flere lineære algebra -biblioteker sprogets evne til at overbelaste operatører . I nogle tilfælde er en meget snæver abstraktion på disse sprog eksplicit påvirket af array -programmeringsparadigmet, som Armadillo og Blitz ++ bibliotekerne gør.