Matrixmultiplikation i Java
1. Oversigt
I denne vejledning ser vi på, hvordan vi kan multiplicere to matricer i Java.
Da matrixkonceptet ikke findes indfødt på sproget, implementerer vi det selv, og vi vil også arbejde med et par biblioteker for at se, hvordan de håndterer matrixmultiplikation.
I sidste ende foretager vi en lille benchmarking af de forskellige løsninger, vi har undersøgt for at bestemme den hurtigste.
2. Eksemplet
Lad os starte med at oprette et eksempel, som vi kan henvise til i hele denne tutorial.
Først forestiller vi os en 3 × 2 matrix:
Lad os forestille os en anden matrix, to rækker med fire kolonner denne gang:
Derefter multipliceres den første matrix med den anden matrix, hvilket vil resultere i en 3 × 4 matrix:
Som en påmindelse, dette resultat opnås ved at beregne hver celle i den resulterende matrix med denne formel:
Hvor r er antallet af matrixrækker EN, c er antallet af kolonner i matrix B og n er antallet af kolonner i matrixen EN, som skal matche antallet af matrixrækker B.
3. Multiplikation af matrix
3.1. Egen implementering
Lad os starte med vores egen implementering af matricer.
Vi holder det enkelt og retfærdigt bruge to dimensionelle dobbelt arrays:
dobbelt [] [] firstMatrix = {new double [] {1d, 5d}, new double [] {2d, 3d}, new double [] {1d, 7d}}; dobbelt [] [] secondMatrix = {ny dobbelt [] {1d, 2d, 3d, 7d}, ny dobbelt [] {5d, 2d, 8d, 1d}};Det er de to matricer i vores eksempel. Lad os oprette den forventede som resultatet af deres multiplikation:
dobbelt [] [] forventet = {nyt dobbelt [] {26d, 12d, 43d, 12d}, nyt dobbelt [] {17d, 10d, 30d, 17d}, nyt dobbelt [] {36d, 16d, 59d, 14d}} ;Nu hvor alt er sat op, lad os implementere multiplikationsalgoritmen. Vi opretter først et tomt resultatarray og gentages gennem dets celler for at gemme den forventede værdi i hver af dem:
dobbelt [] [] multiplyMatrices (double [] [] firstMatrix, double [] [] secondMatrix) {double [] [] result = new double [firstMatrix.length] [secondMatrix [0] .length]; for (int række = 0; række <resultat.længde; række ++) {for (int col = 0; col <resultat [række] .længde; col ++) {resultat [række] [col] = multiplyMatricesCell (firstMatrix, secondMatrix, række , col); }} returner resultat; }Lad os endelig implementere beregningen af en enkelt celle. For at opnå det, vi bruger formlen vist tidligere i præsentationen af eksemplet:
dobbelt multiplicereMatricesCell (dobbelt [] [] firstMatrix, dobbelt [] [] secondMatrix, int række, int col) {dobbelt celle = 0; for (int i = 0; i <secondMatrix.length; i ++) {celle + = firstMatrix [række] [i] * secondMatrix [i] [col]; } returcelle }Lad os endelig kontrollere, at resultatet af algoritmen matcher vores forventede resultat:
dobbelt [] [] faktisk = multiplymatricer (firstMatrix, secondMatrix); assertThat (faktisk) .isEqualTo (forventet);3.2. EJML
Det første bibliotek, vi vil se på, er EJML, som står for Efficient Java Matrix Library. På tidspunktet for skrivningen af denne vejledning er det et af de senest opdaterede Java-matrixbiblioteker. Formålet er at være så effektiv som muligt med hensyn til beregning og hukommelsesforbrug.
Vi bliver nødt til at tilføje afhængigheden af biblioteket i vores pom.xml:
org.ejml ejml-alle 0.38 Vi bruger stort set det samme mønster som før: Opret to matricer i henhold til vores eksempel og kontroller, at resultatet af deres multiplikation er det, vi har beregnet tidligere.
Så lad os oprette vores matricer ved hjælp af EJML. For at opnå dette, vi bruger SimpleMatrix klasse, der tilbydes af biblioteket.
Det kan tage en to dimension dobbelt array som input til sin konstruktør:
SimpleMatrix firstMatrix = ny SimpleMatrix (ny dobbelt [] [] {ny dobbelt [] {1d, 5d}, ny dobbelt [] {2d, 3d}, ny dobbelt [] {1d, 7d}}); SimpleMatrix secondMatrix = ny SimpleMatrix (ny dobbelt [] [] {ny dobbelt [] {1d, 2d, 3d, 7d}, ny dobbelt [] {5d, 2d, 8d, 1d}});Og lad os nu definere vores forventede matrix til multiplikationen:
SimpleMatrix forventet = ny SimpleMatrix (ny dobbelt [] [] {ny dobbelt [] {26d, 12d, 43d, 12d}, ny dobbelt [] {17d, 10d, 30d, 17d}, ny dobbelt [] {36d, 16d, 59d, 14d}});Nu hvor vi alle er klar, lad os se, hvordan vi multiplicerer de to matricer sammen. Det SimpleMatrix klasse tilbyder en mult () metode tager en anden SimpleMatrix som en parameter og returnerer multiplikationen af de to matricer:
SimpleMatrix faktisk = firstMatrix.mult (secondMatrix);Lad os kontrollere, om det opnåede resultat matcher det forventede.
Som SimpleMatrix tilsidesætter ikke lige med() metode, kan vi ikke stole på, at det udfører verifikationen. Men, det tilbyder et alternativ: isIdentical () metode som ikke kun tager en anden matrixparameter, men også en dobbelt fejltolerance man ignorerer små forskelle på grund af dobbelt præcision:
assertThat (faktisk) .matches (m -> m.is Identisk (forventet, 0d));Det afsluttes multiplikation af matricer med EJML-biblioteket. Lad os se, hvad de andre tilbyder.
3.3. ND4J
Lad os nu prøve ND4J-biblioteket. ND4J er et beregningsbibliotek og er en del af deeplearning4j-projektet. Blandt andet tilbyder ND4J matrixberegningsfunktioner.
Først og fremmest skal vi få bibliotekets afhængighed:
org.nd4j nd4j-native 1.0.0-beta4 Bemærk, at vi bruger betaversionen her, fordi der ser ud til at have nogle fejl med GA-frigivelse.
Af kortheds skyld skal vi ikke omskrive de to dimensioner dobbelt arrays og bare fokusere på, hvordan de bruges i hvert bibliotek. Således med ND4J skal vi oprette en INDArray. For at gøre det, vi kalder Nd4j.create () fabriksmetode og videregive den a dobbelt array, der repræsenterer vores matrix:
INDArray matrix = Nd4j.create (/ * en todimension dobbelt array * /);Som i det foregående afsnit opretter vi tre matricer: de to, vi skal multiplicere sammen, og den ene er det forventede resultat.
Derefter ønsker vi faktisk at multiplicere mellem de to første matricer ved hjælp af INDArray.mmul () metode:
INDArray faktisk = firstMatrix.mmul (secondMatrix);Derefter kontrollerer vi igen, at det faktiske resultat matcher det forventede. Denne gang kan vi stole på en ligestillingskontrol:
assertThat (faktisk) .isEqualTo (forventet);Dette viser, hvordan ND4J-biblioteket kan bruges til at udføre matrixberegninger.
3.4. Apache Commons
Lad os nu tale om Apache Commons Math3-modulet, som giver os matematiske beregninger inklusive matrixmanipulationer.
Igen bliver vi nødt til at specificere afhængigheden i vores pom.xml:
org.apache.commons commons-math3 3.6.1 Når vi er konfigureret, kan vi bruge det RealMatrix interface og dens Array2DRowRealMatrix implementering at skabe vores sædvanlige matricer. Konstruktøren af implementeringsklassen tager en todimensional dobbelt array som parameter:
RealMatrix-matrix = ny Array2DRowRealMatrix (/ * et todimensionalt dobbeltarray * /);Hvad angår multiplikation af matricer, det RealMatrix interface tilbyder en formere sig() metode tager en anden RealMatrix parameter:
RealMatrix faktisk = firstMatrix.multiply (secondMatrix);Vi kan endelig kontrollere, at resultatet er lig med det, vi forventer:
assertThat (faktisk) .isEqualTo (forventet);Lad os se det næste bibliotek!
3.5. LA4J
Denne hedder LA4J, som står for Lineær algebra til Java.
Lad os også tilføje afhængigheden af denne:
org.la4j la4j 0.6.0 Nu fungerer LA4J stort set som de andre biblioteker. Det tilbyder en Matrix interface til en Basic2DMatrix implementering der tager en to-dimensionel dobbelt array som input:
Matrixmatrix = ny Basic2DMatrix (/ * et todimensionalt dobbelt array * /);Som i Apache Commons Math3-modulet, multiplikationsmetoden er formere sig() og tager en anden Matrix som sin parameter:
Matrix actual = firstMatrix.multiply (secondMatrix);Endnu en gang kan vi kontrollere, at resultatet svarer til vores forventninger:
assertThat (faktisk) .isEqualTo (forventet);Lad os nu se på vores sidste bibliotek: Colt.
3.6. Hingst
Colt er et bibliotek udviklet af CERN. Det giver funktioner, der muliggør højtydende videnskabelig og teknisk computing.
Som med de tidligere biblioteker skal vi have den rigtige afhængighed:
hingsteføl 1.2.0 For at skabe matricer med Colt, vi skal gøre brug af DoubleFactory2D klasse. Den leveres med tre fabriksinstanser: tæt, sparsom og række Komprimeret. Hver er optimeret til at skabe den matchende slags matrix.
Til vores formål bruger vi tæt eksempel. Denne gang, metoden til at ringe til er lave() og det tager en to-dimensionel dobbelt array igen, producerer en DoubleMatrix2D objekt:
DoubleMatrix2D matrix = doubleFactory2D.make (/ * en todimension dobbelt array * /);Når vores matricer er instantieret, vil vi multiplicere dem. Denne gang er der ingen metode på matrixobjektet til at gøre det. Vi er nødt til at oprette en forekomst af Algebra klasse, der har en mult () metode tager to matricer til parametre:
Algebra algebra = ny algebra (); DoubleMatrix2D actual = algebra.mult (firstMatrix, secondMatrix);Derefter kan vi sammenligne det faktiske resultat med det forventede:
assertThat (faktisk) .isEqualTo (forventet);4. Benchmarking
Nu hvor vi er færdige med at udforske de forskellige muligheder for matrixmultiplikation, lad os kontrollere, hvilke der er mest effektive.
4.1. Små matricer
Lad os begynde med små matricer. Her er en 3 × 2 og en 2 × 4 matricer.
For at implementere præstationstesten bruger vi JMH benchmarking-bibliotek. Lad os konfigurere en benchmarking klasse med følgende muligheder:
offentlig statisk ugyldig hoved (String [] args) kaster undtagelse {Options opt = new OptionsBuilder () .include (MatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (5) .measurementIterations (10) .timeUnit (TimeUnit.MICROSECONDS) .build (); ny Runner (opt) .run (); }På denne måde foretager JMH to fulde kørsler for hver metode, der er kommenteret med @Benchmark, hver med fem opvarmnings-iterationer (ikke taget med i den gennemsnitlige beregning) og ti målinger. Med hensyn til målingerne samler den den gennemsnitlige tid til udførelse af de forskellige biblioteker i mikrosekunder.
Vi er derefter nødt til at oprette et tilstandsobjekt, der indeholder vores arrays:
@State (Scope.Benchmark) offentlig klasse MatrixProvider {privat dobbelt [] [] firstMatrix; privat dobbelt [] [] secondMatrix; offentlig MatrixProvider () {firstMatrix = ny dobbelt [] [] {ny dobbelt [] {1d, 5d}, ny dobbelt [] {2d, 3d}, ny dobbelt [] {1d, 7d}}; secondMatrix = ny dobbelt [] [] {ny dobbelt [] {1d, 2d, 3d, 7d}, ny dobbelt [] {5d, 2d, 8d, 1d}}; }}På den måde sørger vi for, at initialisering af arrays ikke er en del af benchmarking. Derefter er vi stadig nødt til at oprette metoder, der multiplicerer matricerne ved hjælp af MatrixProvider objekt som datakilde. Vi gentager ikke koden her, da vi så hvert bibliotek tidligere.
Endelig kører vi benchmarking-processen ved hjælp af vores vigtigste metode. Dette giver os følgende resultat:
Benchmark-tilstand Cnt Score Fejl Enheder MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1008 ± 0032 os / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0219 ± 0014 os / op MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0226 ± 0013 os / op MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 0389 ± 0045 os / op MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12.670 ± 2.582 us / opSom vi kan se, EJML og Hingst klarer sig rigtig godt med omkring en femtedel af en mikrosekund pr. operation, hvor ND4j er mindre performant med lidt mere end ti mikrosekunder pr. operation. De andre biblioteker har forestillinger midt imellem.
Det er også værd at bemærke, at ydeevnen stiger for alle biblioteker, når antallet af opvarmnings-iterationer øges fra 5 til 10.
4.2. Store matricer
Hvad sker der nu, hvis vi tager større matricer som 3000 × 3000? For at kontrollere hvad der sker, lad os først oprette en anden tilstandsklasse, der giver genererede matricer af den størrelse:
@State (Scope.Benchmark) offentlig klasse BigMatrixProvider {privat dobbelt [] [] firstMatrix; privat dobbelt [] [] secondMatrix; offentlig BigMatrixProvider () {} @ Setup offentlig tomrumsopsætning (BenchmarkParams-parametre) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } privat dobbelt [] [] createMatrix () {Random random = new Random (); dobbelt [] [] resultat = nyt dobbelt [3000] [3000]; for (int række = 0; række <resultat.længde; række ++) {for (int col = 0; col <resultat [række] .længde; col ++) {resultat [række] [col] = random.nextDouble (); }} returner resultat; }}Som vi kan se, opretter vi 3000 × 3000 todimensionelle dobbeltarrays fyldt med tilfældige reelle tal.
Lad os nu oprette benchmarking-klassen:
offentlig klasse BigMatrixMultiplicationBenchmarking {public static void main (String [] args) throw Exception {Map parameters = parseParameters (args); ChainedOptionsBuilder builder = new OptionsBuilder () .include (BigMatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (10) .målingIterations (10) .timeUnit (TimeUnit.SECONDS); ny Runner (builder.build ()). run (); } @Benchmark public Objekt homemadeMatrixMultiplication (BigMatrixProvider matrixProvider) {returner HomemadeMatrix .multiplyMatrices (matrixProvider.getFirstMatrix (), matrixProvider.getSecondMatrix ()); } @Benchmark public Object ejmlMatrixMultiplication (BigMatrixProvider matrixProvider) {SimpleMatrix firstMatrix = ny SimpleMatrix (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = ny SimpleMatrix (matrixProvider.getSecondMatrix ()); returnere firstMatrix.mult (secondMatrix); } @Benchmark public Object apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = new Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = ny Array2DRowRealMatrix (matrixProvider.getSecondMatrix ()); returnere firstMatrix.multiply (secondMatrix); } @Benchmark public Object la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = new Basic2DMatrix (matrixProvider.getFirstMatrix ()); Matrix secondMatrix = ny Basic2DMatrix (matrixProvider.getSecondMatrix ()); returnere firstMatrix.multiply (secondMatrix); } @Benchmark public Object nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); returnere firstMatrix.mmul (secondMatrix); } @Benchmark public Object coltMatrixMultiplication (BigMatrixProvider matrixProvider) {DoubleFactory2D doubleFactory2D = DoubleFactory2D.dense; DoubleMatrix2D firstMatrix = doubleFactory2D.make (matrixProvider.getFirstMatrix ()); DoubleMatrix2D secondMatrix = doubleFactory2D.make (matrixProvider.getSecondMatrix ()); Algebra algebra = ny algebra (); returnere algebra.mult (firstMatrix, secondMatrix); }}Når vi kører denne benchmarking, opnår vi helt andre resultater:
Benchmark tilstand Cnt Score Fejl Units BigMatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 511,140 ± 13,535 s / op BigMatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 197,914 ± 2,453 s / op BigMatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 25,830 ± 0,059 s / op BigMatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 497,493 ± 2.121 s / op BigMatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 35.523 ± 0.102 s / op BigMatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 0.548 ± 0.006 s / opSom vi kan se, er de hjemmelavede implementeringer og Apache-biblioteket nu langt dårligere end før, og det tager næsten 10 minutter at udføre multiplikationen af de to matricer.
Colt tager lidt mere end 3 minutter, hvilket er bedre, men stadig meget lang. EJML og LA4J klarer sig ret godt, da de kører på næsten 30 sekunder. Men det er ND4J, der vinder denne benchmarking på under et sekund på en CPU-backend.
4.3. Analyse
Det viser os, at benchmarking-resultaterne virkelig afhænger af matrixernes egenskaber, og det er derfor vanskeligt at påpege en enkelt vinder.
5. Konklusion
I denne artikel har vi lært, hvordan man multiplicerer matricer i Java, enten af os selv eller med eksterne biblioteker. Efter at have undersøgt alle løsninger, gjorde vi et benchmark for dem alle og så, at de med undtagelse af ND4J alle klarede sig ret godt på små matricer. På den anden side tager ND4J føringen på større matricer.
Som sædvanlig kan den fulde kode til denne artikel findes på GitHub.
