streamalism.org

1. Pregled

U ovom uputstvu ćemo pogledati kako možemo množiti dvije matrice u Javi.

Kako koncept matrice ne postoji izvorno u jeziku, implementirat ćemo ga sami, a surađivat ćemo i s nekoliko knjižnica kako bismo vidjeli kako se bave umnožavanjem matrica.

Na kraju ćemo napraviti malo usporedbe različitih rješenja koja smo istražili kako bismo odredili ono najbrže.

2. Primjer

Počnimo s postavljanjem primjera na koji ćemo se moći pozivati ​​u ovom vodiču.

Prvo ćemo zamisliti matricu 3 × 2:

Zamislimo sada drugu matricu, dva puta po četiri stupca ovaj put:

Zatim, množenje prve matrice s drugom matricom, što će rezultirati matricom 3 × 4:

Kao podsjetnik, taj se rezultat dobiva računanjem svake ćelije rezultirajuće matrice s ovom formulom:

Gdje r je broj redaka matrice A, c je broj stupaca matrice B i n je broj stupaca matrice A, koji mora odgovarati broju redaka matrice B.

3. Množenje matrica

3.1. Vlastita provedba

Počnimo s vlastitom implementacijom matrica.

Bit ćemo jednostavni i pravedni koristiti dvodimenzionalni dvostruko nizovi:

double [] [] firstMatrix = {novi double [] {1d, 5d}, novi double [] {2d, 3d}, novi double [] {1d, 7d}}; double [] [] secondMatrix = {novi double [] {1d, 2d, 3d, 7d}, novi dvostruki [] {5d, 2d, 8d, 1d}};

To su dvije matrice našeg primjera. Stvorimo onu koja se očekuje kao rezultat njihovog množenja:

double [] [] očekuje se = {novi double [] {26d, 12d, 43d, 12d}, novi dvostruki [] {17d, 10d, 30d, 17d}, novi dvostruki [] {36d, 16d, 59d, 14d}} ;

Sad kad je sve postavljeno, provedimo algoritam množenja. Prvo ćemo stvoriti prazan niz rezultata i iterirati kroz njegove ćelije kako bismo pohranili očekivanu vrijednost u svaku od njih:

double [] [] multiplyMatricks (double [] [] firstMatrix, double [] [] secondMatrix) {double [] [] rezultat = novi double [firstMatrix.length] [secondMatrix [0] .length]; for (int row = 0; row <result.length; row ++) {for (int col = 0; col <result [row] .length; col ++) {result [row] [col] = multiplyMatricksCell (firstMatrix, secondMatrix, row , col); }} vratiti rezultat; }

Konačno, provedimo izračunavanje jedne ćelije. Da bi se to postiglo, koristit ćemo formulu prikazanu ranije u prezentaciji primjera:

dvostruka multiplyMatricksCell (dvostruka [] [] prva matrica, dvostruka [] [] druga matrica, int redak, int kol) {dvostruka ćelija = 0; za (int i = 0; i <secondMatrix.length; i ++) {cell + = firstMatrix [red] [i] * secondMatrix [i] [col]; } povratna ćelija; }

Na kraju, provjerimo odgovara li rezultat algoritma našem očekivanom rezultatu:

double [] [] stvarni = multiplyMatricks (prviMatrix, drugiMatrix); assertThat (actual) .isEqualTo (očekuje se);

3.2. EJML

Prva knjižnica koju ćemo pogledati je EJML, što je skraćenica od Efficient Java Matrix Library. U vrijeme pisanja ovog vodiča, to je jedna od najnovije ažuriranih Java matričnih knjižnica. Njegova je svrha biti što učinkovitiji u pogledu izračunavanja i korištenja memorije.

Morat ćemo dodati ovisnost knjižnici u našoj pom.xml:

 org.ejml ejml-svi 0,38 

Upotrijebit ćemo gotovo isti obrazac kao i prije: stvoriti dvije matrice prema našem primjeru i provjeriti je li rezultat njihovog množenja onaj koji smo izračunali ranije.

Dakle, kreirajmo naše matrice pomoću EJML-a. Da bi se to postiglo, koristit ćemo SimpleMatrix razred koji nudi knjižnica.

To može imati dvije dimenzije dvostruko niz kao ulaz za njegov konstruktor:

SimpleMatrix firstMatrix = novi SimpleMatrix (novi double [] [] {novi double [] {1d, 5d}, novi double [] {2d, 3d}, novi double [] {1d, 7d}}); SimpleMatrix secondMatrix = nova SimpleMatrix (nova dvostruka [] [] {nova dvostruka [] {1d, 2d, 3d, 7d}, nova dvostruka [] {5d, 2d, 8d, 1d}});

A sada, definirajmo našu očekivanu matricu za množenje:

Očekuje se SimpleMatrix = novi SimpleMatrix (novi dvostruki [] [] {novi dvostruki [] {26d, 12d, 43d, 12d}, novi dvostruki [] {17d, 10d, 30d, 17d}, novi dupla [] {36d, 16d, 59d, 14d}});

Sad kad smo svi postavljeni, pogledajmo kako pomnožiti dvije matrice zajedno. The SimpleMatrix razred nudi a više () metoda uzimajući drugu SimpleMatrix kao parametar i vraća množenje dviju matrica:

SimpleMatrix stvarni = firstMatrix.mult (secondMatrix);

Provjerimo poklapa li se dobiveni rezultat s očekivanim.

Kao SimpleMatrix ne poništava jednako () metodom, na nju se ne možemo osloniti za provjeru. Ali, nudi alternativu: isIdentical () metoda koji uzima ne samo drugi parametar matrice već i a dvostruko tolerancija kvara zanemarivanje malih razlika zbog dvostruke preciznosti:

assertThat (stvarni) .matches (m -> m.isIdentical (očekuje se, 0d));

Time se množenje matrica završava s EJML knjižnicom. Pogledajmo što nude ostali.

3.3. ND4J

Pokušajmo sada s knjižnicom ND4J. ND4J je računska knjižnica i dio je projekta deeplearning4j. Između ostalog, ND4J nudi značajke matričnog računanja.

Prije svega, moramo dobiti ovisnost o knjižnici:

 org.nd4j nd4j-izvorni 1.0.0-beta4 

Imajte na umu da ovdje koristimo beta verziju jer se čini da postoje neke pogreške u izdanju GA.

Radi kratkoće, nećemo prepisivati ​​dvije dimenzije dvostruko nizova i samo se usredotočite na to kako se koriste u svakoj knjižnici. Dakle, s ND4J moramo stvoriti INDArray. Da bi to učinili, nazvat ćemo Nd4j.create () tvornička metoda i proslijedite je a dvostruko niz koji predstavlja našu matricu:

INDArray matrica = Nd4j.create (/ * dvodimenzionalni dvostruki niz * /);

Kao i u prethodnom odjeljku, stvorit ćemo tri matrice: dvije koje ćemo pomnožiti i jedna koja je očekivani rezultat.

Nakon toga želimo zapravo izvršiti množenje između prve dvije matrice pomoću INDArray.mmul () metoda:

INDArray stvarni = firstMatrix.mmul (secondMatrix);

Zatim ponovno provjeravamo odgovara li stvarni rezultat očekivanom. Ovaj put možemo se osloniti na provjeru jednakosti:

assertThat (actual) .isEqualTo (očekuje se);

To pokazuje kako se knjižnica ND4J može koristiti za izračun matrica.

3.4. Apache Commons

Razgovarajmo sada o modulu Apache Commons Math3, koji nam pruža matematička izračunavanja, uključujući manipulacije matricama.

Opet, morat ćemo navesti ovisnost u našem pom.xml:

 org.apache.commons commons-math3 3.6.1 

Jednom postavljeni, možemo koristiti the RealMatrix sučelje i njegovo Array2DRowRealMatrix provedba stvoriti naše uobičajene matrice. Konstruktor klase implementacije uzima dvodimenzionalnu dvostruko niz kao njegov parametar:

RealMatrix matrica = novi Array2DRowRealMatrix (/ * dvodimenzionalni dvostruki niz * /);

Što se tiče umnožavanja matrica, the RealMatrix sučelje nudi a pomnožiti() metoda uzimajući drugu RealMatrix parametar:

RealMatrix stvarni = firstMatrix.multiply (secondMatrix);

Napokon možemo provjeriti je li rezultat jednak onome što očekujemo:

assertThat (actual) .isEqualTo (očekuje se);

Pogledajmo sljedeću knjižnicu!

3.5. LA4J

Ovaj se zove LA4J, što znači Linearna algebra za Javu.

Dodajmo ovisnost i za ovu:

 org.la4j la4j 0.6.0 

Sada LA4J djeluje gotovo kao i ostale knjižnice. Nudi a Matrica sučelje s a Basic2DMatrix provedba to traje dvodimenzionalno dvostruko niz kao ulaz:

Matrica matrice = nova Basic2DMatrix (/ * dvodimenzionalni dvostruki niz * /);

Kao i u Apache Commons Math3 modulu, metoda množenja je pomnožiti() i uzima drugu Matrica kao njegov parametar:

Matrica stvarna = firstMatrix.multiply (secondMatrix);

Još jednom možemo provjeriti odgovara li rezultat našim očekivanjima:

assertThat (actual) .isEqualTo (očekuje se);

Pogledajmo sada našu posljednju knjižnicu: Colt.

3.6. Colt

Colt je knjižnica koju je razvio CERN. Pruža značajke koje omogućuju znanstveno i tehničko računanje visokih performansi.

Kao i u prethodnim knjižnicama, i mi moramo dobiti pravu ovisnost:

 kolt kolt 1.2.0 

Da bi stvorili matrice s Coltom, moramo se poslužiti Klasa DoubleFactory2D. Dolazi s tri tvorničke instance: gusta, rijetka i redKomprimiran. Svaka je optimizirana za stvaranje odgovarajuće vrste matrice.

U našu svrhu koristit ćemo gusta primjer. Ovaj put, metoda pozivanja je napraviti() a potreban je dvodimenzionalni dvostruki niz opet, proizvodeći a DoubleMatrix2D objekt:

DoubleMatrix2D matrica = doubleFactory2D.make (/ * dvodimenzionalni dvostruki niz * /);

Jednom kada se naše matrice izgrade, poželjet ćemo ih pomnožiti. Ovaj put na objektu matrice ne postoji metoda koja bi to učinila. Moramo stvoriti instancu Algebra razred koji ima a više () metoda uzimanje dvije matrice za parametre:

Algebra algebra = nova algebra (); DoubleMatrix2D stvarni = algebra.mult (firstMatrix, secondMatrix);

Tada možemo usporediti stvarni rezultat s očekivanim:

assertThat (actual) .isEqualTo (očekuje se);

4. Benchmarking

Sad kad smo završili s istraživanjem različitih mogućnosti množenja matrica, provjerimo koje su najučinkovitije.

4.1. Male matrice

Počnimo s malim matricama. Ovdje su matrice 3 × 2 i 2 × 4.

Da bismo proveli test izvedbe, koristit ćemo JMH referentna biblioteka. Konfigurirajmo klasu referentne analize sa sljedećim opcijama:

public static void main (String [] args) baca iznimku {Options opt = new OptionsBuilder () .include (MatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (5) .measurementIterations (10) .timeUnit (TimeUnit.MICROSECONDS) .build (); novi Runner (opt) .run (); }

Na taj će način JMH napraviti dva puna izvođenja za svaku metodu označenu s @Benchmark, svaka s pet ponavljanja zagrijavanja (koje nisu uzete u prosjek izračuna) i deset mjernih. Što se tiče mjerenja, prikupit će prosječno vrijeme izvršavanja različitih knjižnica, u mikrosekundama.

Zatim moramo stvoriti objekt stanja koji sadrži naše nizove:

@State (Scope.Benchmark) javna klasa MatrixProvider {private double [] [] firstMatrix; private double [] [] secondMatrix; javni MatrixProvider () {firstMatrix = new double [] [] {new double [] {1d, 5d}, novi double [] {2d, 3d}, novi double [] {1d, 7d}}; secondMatrix = novi dvostruki [] [] {novi dvostruki [] {1d, 2d, 3d, 7d}, novi dvostruki [] {5d, 2d, 8d, 1d}}; }}

Na taj način osiguravamo da inicijalizacija nizova nije dio benčmarkinga. Nakon toga, još uvijek moramo stvoriti metode koje vrše množenje matrica, koristeći MatrixProvider objekt kao izvor podataka. Ovdje nećemo ponoviti kod kao što smo ranije vidjeli svaku knjižnicu.

Na kraju ćemo pokrenuti postupak usporedne analize koristeći naš glavni metoda. To nam daje sljedeći rezultat:

Benchmark Mode Cnt Rezultat Jedinice grešaka MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1,008 ± 0,032 us / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0,219 ± 0,014 us / op MatrixMultiplicationBenchmarking.ejmlvmultimatMarkMarkmultiMarkMarkmultiMarkMarkmultiMarkMarkMarkmultiMarkMarkmultiMarkMarkmultiMarkMarkmultiMarkMarkmultiMarkMarkmultiMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkMarkm MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12,670 ± 2,582 us / op

Kao što vidimo, EJML i Colt stvarno dobro rade s otprilike petinom mikrosekunde po operaciji, gdje ND4j je manje izveden s nešto više od deset mikrosekundi po operaciji. Ostale knjižnice imaju predstave smještene između.

Također, vrijedi napomenuti da se povećavanjem broja ponavljanja zagrijavanja s 5 na 10 povećava učinkovitost svih knjižnica.

4.2. Velike matrice

Sad, što se događa ako uzmemo veće matrice, poput 3000 × 3000? Da provjerimo što se događa, napravimo prvo drugu klasu stanja koja pruža generirane matrice te veličine:

@State (Scope.Benchmark) javna klasa BigMatrixProvider {private double [] [] firstMatrix; private double [] [] secondMatrix; javni BigMatrixProvider () {} @Setup postavljanje javne praznine (parametri BenchmarkParams) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } private double [] [] createMatrix () {Random random = novo Random (); dvostruki [] [] rezultat = novi dvostruki [3000] [3000]; for (int row = 0; row <result.length; row ++) {for (int col = 0; col <result [row] .length; col ++) {result [row] [col] = random.nextDouble (); }} vratiti rezultat; }}

Kao što vidimo, stvorit ćemo 3000 × 3000 dvodimenzionalnih dvostrukih polja ispunjenih slučajnim realnim brojevima.

Stvorimo sada klasu referentne ocjene:

javna klasa BigMatrixMultiplicationBenchmarking {javna statička void glavna (String [] args) baca izuzetak {Parametri karte = parseParameters (args); Graditelj ChainedOptionsBuilder = new OptionsBuilder () .include (BigMatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (10) .measurementIterations (10); timeUnit (TimeUnit.SECON (TimeUnit.SECON (TimeUnit.SECON (TimeUnit.SECON (TimeUnit.SECON (TimeUnit.SECON)). novi Runner (builder.build ()). run (); } @Benchmark javni objekt homemadeMatrixMultiplication (BigMatrixProvider matrixProvider) {return HomemadeMatrix .multiplyMatricks (matrixProvider.getFirstMatrix (), matrixProvider.getSecondMatrix ()); } @Benchmark javni objekt ejmlMatrixMultiplication (BigMatrixProvider matrixProvider) {SimpleMatrix firstMatrix = novi SimpleMatrix (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = nova SimpleMatrix (matrixProvider.getSecondMatrix ()); vrati firstMatrix.mult (secondMatrix); } @Benchmark javni objekt apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = novi Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = novi Array2DRowRealMatrix (matrixProvider.getSecondMatrix ()); vrati firstMatrix.multiply (secondMatrix); } @Benchmark javni objekt la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = novi Basic2DMatrix (matrixProvider.getFirstMatrix ()); Matrica secondMatrix = nova Basic2DMatrix (matrixProvider.getSecondMatrix ()); vrati firstMatrix.multiply (secondMatrix); } @Benchmark javni objekt nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); vrati firstMatrix.mmul (secondMatrix); } @Benchmark javni objekt coltMatrixMultiplication (BigMatrixProvider matrixProvider) {DoubleFactory2D doubleFactory2D = DoubleFactory2D.dense; DoubleMatrix2D firstMatrix = doubleFactory2D.make (matrixProvider.getFirstMatrix ()); DoubleMatrix2D secondMatrix = doubleFactory2D.make (matrixProvider.getSecondMatrix ()); Algebra algebra = nova algebra (); povratna algebra.mult (firstMatrix, secondMatrix); }}

Kada pokrenemo ovu usporedbu, dobivamo potpuno drugačije rezultate:

Referentna način CNT rezultat pogrešaka jedinice BigMatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 511,140 ± 13,535 e / op BigMatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 197,914 ± 2,453 s / op BigMatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 25,830 0,059 ± e / op BigMatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 497,493 ± 2.121 e / op BigMatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 35,523 ± 0,102 s / op BigMatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 0,548 ± 0,006 s / op

Kao što vidimo, domaće implementacije i Apache knjižnica sada su puno lošije nego prije, treba im gotovo 10 minuta da izvedu množenje dviju matrica.

Coltu treba malo više od 3 minute, što je bolje, ali još uvijek jako dugo. EJML i LA4J rade prilično dobro jer rade u gotovo 30 sekundi. Ali, ND4J je taj koji pobjeđuje u usporedbi s manje od sekunde na pozadini procesora.

4.3. Analiza

To nam pokazuje da rezultati benchmarkinga stvarno ovise o karakteristikama matrica i stoga je nezgodno istaknuti jednog pobjednika.

5. Zaključak

U ovom smo članku naučili kako množiti matrice u Javi, bilo sami ili pomoću vanjskih knjižnica. Nakon istraživanja svih rješenja, napravili smo mjerilo svih njih i vidjeli da su, osim ND4J, svi imali prilično dobre performanse na malim matricama. S druge strane, na većim matricama ND4J preuzima vodeću ulogu.

Kao i obično, puni kod za ovaj članak nalazi se na GitHubu.