streamalism.org

1. Oversikt

I denne opplæringen vil vi se på hvordan vi kan multiplisere to matriser i Java.

Ettersom matrikskonseptet ikke eksisterer naturlig i språket, implementerer vi det selv, og vi vil også jobbe med noen få biblioteker for å se hvordan de håndterer matriksmultiplikasjon.

Til slutt vil vi gjøre en liten benchmarking av de forskjellige løsningene vi utforsket for å bestemme den raskeste.

2. Eksemplet

La oss begynne med å sette opp et eksempel vi kan referere til gjennom hele denne opplæringen.

Først vil vi forestille oss en 3 × 2 matrise:

La oss nå forestille oss en andre matrise, to rader med fire kolonner denne gangen:

Multipliseringen av den første matrisen med den andre matrisen, som vil resultere i en 3 × 4 matrise:

Som en påminnelse, dette resultatet oppnås ved å beregne hver celle i den resulterende matrisen med denne formelen:

Hvor r er antall matriserader EN, c er antall kolonner i matrisen B og n er antall kolonner i matrisen EN, som må matche antall rader med matrise B.

3. Matriksmultiplikasjon

3.1. Egen implementering

La oss starte med vår egen implementering av matriser.

Vi holder det enkelt og rettferdig bruk todimensjonalt dobbelt arrays:

dobbelt [] [] firstMatrix = {new double [] {1d, 5d}, new double [] {2d, 3d}, new double [] {1d, 7d}}; dobbel [] [] secondMatrix = {ny dobbel [] {1d, 2d, 3d, 7d}, ny dobbel [] {5d, 2d, 8d, 1d}};

Dette er de to matrisene i eksemplet vårt. La oss lage den som forventes som et resultat av multiplikasjonen deres:

dobbel [] [] forventet = {ny dobbel [] {26d, 12d, 43d, 12d}, ny dobbel [] {17d, 10d, 30d, 17d}, ny dobbel [] {36d, 16d, 59d, 14d}} ;

Nå som alt er satt opp, la oss implementere multiplikasjonsalgoritmen. Vi oppretter først et tomt resultatarray og gjentar det gjennom cellene for å lagre den forventede verdien i hver av dem:

dobbelt [] [] multiplyMatrices (double [] [] firstMatrix, double [] [] secondMatrix) {double [] [] result = new double [firstMatrix.length] [secondMatrix [0] .length]; for (int rad = 0; rad <result.length; rad ++) {for (int col = 0; col <resultat [rad] .length; col ++) {resultat [rad] [col] = multiplyMatricesCell (firstMatrix, secondMatrix, rad , kol); }} returner resultat; }

Til slutt, la oss implementere beregningen av en enkelt celle. For å oppnå det, vi bruker formelen vist tidligere i presentasjonen av eksemplet:

dobbelt multiplikereMatricesCell (dobbelt [] [] firstMatrix, dobbelt [] [] secondMatrix, int rad, int col) {dobbel celle = 0; for (int i = 0; i <secondMatrix.length; i ++) {cell + = firstMatrix [rad] [i] * secondMatrix [i] [col]; } returcelle; }

Til slutt, la oss sjekke at resultatet av algoritmen samsvarer med vårt forventede resultat:

dobbelt [] [] faktisk = multipliserMatriser (firstMatrix, secondMatrix); assertThat (faktisk) .isEqualTo (forventet);

3.2. EJML

Det første biblioteket vi skal se på er EJML, som står for Efficient Java Matrix Library. Når du skriver denne opplæringen, er det en av de sist oppdaterte Java-matrisebibliotekene. Hensikten er å være så effektiv som mulig når det gjelder beregning og minnebruk.

Vi må legge til avhengigheten til biblioteket i vår pom.xml:

 org.ejml ejml-all 0.38 

Vi bruker stort sett det samme mønsteret som før: å lage to matriser i henhold til vårt eksempel og sjekke at resultatet av multiplikasjonen deres er det vi beregnet tidligere.

Så la oss lage matriser ved hjelp av EJML. For å oppnå dette, vi bruker SimpleMatrix klasse som tilbys av biblioteket.

Det kan ta en to dimensjon dobbelt array som input for konstruktøren:

SimpleMatrix firstMatrix = ny SimpleMatrix (ny dobbel [] [] {ny dobbel [] {1d, 5d}, ny dobbel [] {2d, 3d}, ny dobbel [] {1d, 7d}}); SimpleMatrix secondMatrix = ny SimpleMatrix (ny dobbel [] [] {ny dobbel [] {1d, 2d, 3d, 7d}, ny dobbel [] {5d, 2d, 8d, 1d}};

Og la oss nå definere vår forventede matrise for multiplikasjonen:

SimpleMatrix forventet = ny SimpleMatrix (ny dobbel [] [] {ny dobbel [] {26d, 12d, 43d, 12d}, ny dobbel [] {17d, 10d, 30d, 17d}, ny dobbel [] {36d, 16d, 59d, 14d}});

Nå som vi alle er klar, la oss se hvordan vi kan multiplisere de to matrisene sammen. De SimpleMatrix klasse tilbyr en mult () metode tar en annen SimpleMatrix som parameter og returnerer multiplikasjonen av de to matrisene:

SimpleMatrix faktisk = firstMatrix.mult (secondMatrix);

La oss sjekke om det oppnådde resultatet samsvarer med det forventede.

Som SimpleMatrix overstyrer ikke er lik() metoden, kan vi ikke stole på den for å utføre bekreftelsen. Men, det tilbyr et alternativ: isIdentical () metode som ikke bare tar en annen matriseparameter, men også en dobbelt feiltoleranse man ignorerer små forskjeller på grunn av dobbel presisjon:

assertThat (actual) .matches (m -> m.is Identical (forventet, 0d));

Det avslutter matriksmultiplikasjon med EJML-biblioteket. La oss se hva de andre tilbyr.

3.3. ND4J

La oss nå prøve ND4J-biblioteket. ND4J er et beregningsbibliotek og er en del av deeplearning4j-prosjektet. Blant annet tilbyr ND4J matrixberegningsfunksjoner.

Først og fremst må vi få bibliotekavhengighet:

 org.nd4j nd4j-native 1.0.0-beta4 

Merk at vi bruker betaversjonen her fordi det ser ut til å ha noen feil med GA-utgivelse.

For korthets skyld vil vi ikke skrive om de to dimensjonene dobbelt arrays og bare fokusere på hvordan de brukes med hvert bibliotek. Derfor, med ND4J, må vi opprette en INDArray. For å gjøre det, vi vil kalle Nd4j.create () fabriksmetoden og gi den en dobbelt matrise som representerer matrisen vår:

INDArray-matrise = Nd4j.create (/ * en todimensjon dobbel array * /);

Som i forrige avsnitt oppretter vi tre matriser: de to vi skal multiplisere sammen og den ene er det forventede resultatet.

Etter det ønsker vi å faktisk multiplisere mellom de to første matrisene ved hjelp av INDArray.mmul () metode:

INDArray faktisk = firstMatrix.mmul (secondMatrix);

Deretter sjekker vi igjen at det faktiske resultatet samsvarer med det forventede. Denne gangen kan vi stole på en likhetskontroll:

assertThat (faktisk) .isEqualTo (forventet);

Dette demonstrerer hvordan ND4J-biblioteket kan brukes til å gjøre matriseberegninger.

3.4. Apache Commons

La oss nå snakke om Apache Commons Math3-modulen, som gir oss matematiske beregninger inkludert matrisebehandling.

Igjen må vi spesifisere avhengigheten i vår pom.xml:

 org.apache.commons commons-math3 3.6.1 

Når den er satt opp, kan vi bruke den de RealMatrix grensesnitt og dets Array2DRowRealMatrix gjennomføring for å lage våre vanlige matriser. Konstruktøren av implementeringsklassen tar en todimensjonal dobbelt array som parameter:

RealMatrix matrise = ny Array2DRowRealMatrix (/ * en todimensjon dobbel matrise * /);

Når det gjelder multiplikasjon av matriser, de RealMatrix grensesnittet tilbyr en multiplisere() metode tar en annen RealMatrix parameter:

RealMatrix actual = firstMatrix.multiply (secondMatrix);

Vi kan endelig bekrefte at resultatet er lik det vi forventer:

assertThat (faktisk) .isEqualTo (forventet);

La oss se neste bibliotek!

3.5. LA4J

Denne heter LA4J, som står for Lineær algebra for Java.

La oss legge til avhengigheten for denne også:

 org.la4j la4j 0.6.0 

Nå fungerer LA4J omtrent som de andre bibliotekene. Det tilbyr en Matrise grensesnitt med en Basic2DMatrix gjennomføring det tar et todimensjonalt dobbelt array som input:

Matrisematrise = ny Basic2DMatrix (/ * en todimensjon dobbel matrise * /);

Som i Apache Commons Math3-modulen, multiplikasjonsmetoden er multiplisere() og tar en til Matrise som parameter:

Matrix actual = firstMatrix.multiply (secondMatrix);

Nok en gang kan vi sjekke at resultatet samsvarer med forventningene våre:

assertThat (faktisk) .isEqualTo (forventet);

La oss nå ta en titt på vårt siste bibliotek: Colt.

3.6. Colt

Colt er et bibliotek utviklet av CERN. Den har funksjoner som muliggjør høy ytelse vitenskapelig og teknisk databehandling.

Som med tidligere biblioteker, må vi få riktig avhengighet:

 colt colt 1.2.0 

For å lage matriser med Colt, vi må gjøre bruk av DoubleFactory2D klasse. Den leveres med tre fabrikkinstanser: tett, sparsom og rad Komprimert. Hver er optimalisert for å lage den matchende matrisen.

For vårt formål bruker vi tett forekomst. Denne gangen, metoden å ringe er gjøre() og det tar et todimensjonalt dobbelt array igjen, produserer en DoubleMatrix2D gjenstand:

DoubleMatrix2D matrise = doubleFactory2D.make (/ * en to dimensjon dobbel array * /);

Når matrisene våre er instantiert, vil vi multiplisere dem. Denne gangen er det ingen metode på matriseobjektet for å gjøre det. Vi må lage en forekomst av Algebra klasse som har en mult () metode tar to matriser for parametere:

Algebra algebra = ny algebra (); DoubleMatrix2D actual = algebra.mult (firstMatrix, secondMatrix);

Deretter kan vi sammenligne det faktiske resultatet med det forventede:

assertThat (faktisk) .isEqualTo (forventet);

4. Benchmarking

Nå som vi er ferdige med å utforske de forskjellige mulighetene for matriksmultiplikasjon, la oss sjekke hvilke som er mest effektive.

4.1. Små matriser

La oss begynne med små matriser. Her en 3 × 2 og en 2 × 4 matrise.

For å implementere ytelsestesten bruker vi JMH benchmarking-bibliotek. La oss konfigurere en benchmarking-klasse med følgende alternativer:

offentlig statisk ugyldig hoved (String [] args) kaster Unntak {Options opt = new OptionsBuilder () .include (MatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (5) .measurementIterations (10) .timeUnit (TimeUnit.MICROSECONDS) .build (); new Runner (opt) .run (); }

På denne måten vil JMH foreta to hele kjøringer for hver metode som er merket med @Benchmark, hver med fem oppvarmings-iterasjoner (ikke tatt med i gjennomsnittlig beregning) og ti måling. Når det gjelder målingene, samler den gjennomsnittlig tid for utførelse av de forskjellige bibliotekene, i mikrosekunder.

Vi må da lage et tilstandsobjekt som inneholder våre matriser:

@State (Scope.Benchmark) offentlig klasse MatrixProvider {privat dobbel [] [] firstMatrix; privat dobbel [] [] secondMatrix; offentlig MatrixProvider () {firstMatrix = ny dobbel [] [] {ny dobbel [] {1d, 5d}, ny dobbel [] {2d, 3d}, ny dobbel [] {1d, 7d}}; secondMatrix = ny dobbel [] [] {ny dobbel [] {1d, 2d, 3d, 7d}, ny dobbel [] {5d, 2d, 8d, 1d}}; }}

På den måten sørger vi for at initialisering av arrays ikke er en del av benchmarking. Etter det må vi fremdeles lage metoder som multiplikerer matriser ved hjelp av MatrixProvider objekt som datakilde. Vi vil ikke gjenta koden her som vi så hvert bibliotek tidligere.

Til slutt vil vi kjøre referanseprosessen ved hjelp av vår hoved- metode. Dette gir oss følgende resultat:

Benchmark Mode teller Score Feil Units MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1008 ± 0032 oss / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0219 ± 0014 oss / op MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0226 ± 0013 oss / op MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 0389 ± 0045 oss / op MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12,670 ± 2,582 us / op

Som vi kan se, EJML og Colt fungerer veldig bra med omtrent en femtedel mikrosekund per operasjon, hvor ND4j er mindre performant med litt mer enn ti mikrosekunder per operasjon. De andre bibliotekene har forestillinger som ligger i mellom.

Det er også verdt å merke seg at når du øker antall oppvarmings-iterasjoner fra 5 til 10, øker ytelsen for alle bibliotekene.

4.2. Store matriser

Nå, hva skjer hvis vi tar større matriser, som 3000 × 3000? For å sjekke hva som skjer, la oss først opprette en annen tilstandsklasse som gir genererte matriser av den størrelsen:

@State (Scope.Benchmark) offentlig klasse BigMatrixProvider {privat dobbel [] [] firstMatrix; privat dobbel [] [] secondMatrix; public BigMatrixProvider () {} @ Setet public void setup (BenchmarkParams parameters) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } privat dobbel [] [] createMatrix () {Tilfeldig tilfeldig = ny tilfeldig (); dobbelt [] [] resultat = nytt dobbelt [3000] [3000]; for (int rad = 0; rad <resultat.lengde; rad ++) {for (int col = 0; col <resultat [rad] .lengde; col ++) {resultat [rad] [col] = random.nextDouble (); }} returner resultat; }}

Som vi kan se, oppretter vi 3000 × 3000 todimensjonale dobbeltmatriser fylt med tilfeldige reelle tall.

La oss nå lage 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) .measurementIterations (10) .timeUnit (TimeUnit.SECONDS); new Runner (builder.build ()). run (); } @Benchmark public Object homemadeMatrixMultiplication (BigMatrixProvider matrixProvider) {return HomemadeMatrix .multiplyMatrices (matrixProvider.getFirstMatrix (), matrixProvider.getSecondMatrix ()); } @Benchmark public Object ejmlMatrixMultiplication (BigMatrixProvider matrixProvider) {SimpleMatrix firstMatrix = new SimpleMatrix (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = ny SimpleMatrix (matrixProvider.getSecondMatrix ()); returner firstMatrix.mult (secondMatrix); } @Benchmark public Object apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = new Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = ny Array2DRowRealMatrix (matrixProvider.getSecondMatrix ()); returner firstMatrix.multiply (secondMatrix); } @Benchmark public Object la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = new Basic2DMatrix (matrixProvider.getFirstMatrix ()); Matrise secondMatrix = ny Basic2DMatrix (matrixProvider.getSecondMatrix ()); returner firstMatrix.multiply (secondMatrix); } @Benchmark public Object nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); returner 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 (); returner algebra.mult (firstMatrix, secondMatrix); }}

Når vi kjører denne benchmarkingen, får vi helt andre resultater:

Benchmark Mode teller Score Feil 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 / op

Som vi kan se, er hjemmelagde implementeringer og Apache-biblioteket nå langt verre enn før, og det tar nesten 10 minutter å utføre multiplikasjonen av de to matrisene.

Colt tar litt mer enn 3 minutter, noe som er bedre, men likevel veldig lenge. EJML og LA4J presterer ganske bra ettersom de kjører på nesten 30 sekunder. Men det er ND4J som vinner denne benchmarkingen på under ett sekund på en CPU-backend.

4.3. Analyse

Det viser oss at benchmarking-resultatene virkelig avhenger av matrisenes egenskaper, og det er derfor vanskelig å påpeke en enkelt vinner.

5. Konklusjon

I denne artikkelen har vi lært hvordan vi kan multiplisere matriser i Java, enten selv eller med eksterne biblioteker. Etter å ha utforsket alle løsningene, gjorde vi en målestokk for dem alle og så at bortsett fra ND4J, presterte de alle ganske bra på små matriser. På den annen side tar ND4J ledelsen på større matriser.

Som vanlig kan du finne den fulle koden for denne artikkelen på GitHub.