Maticové násobenie v Jave
1. Prehľad
V tomto výučbe sa pozrieme na to, ako môžeme v Jave znásobiť dve matice.
Pretože koncept matice v jazyku natívne neexistuje, implementujeme ho sami a tiež budeme pracovať s niekoľkými knižnicami, aby sme zistili, ako zvládajú násobenie matíc.
Nakoniec urobíme malé porovnanie rôznych riešení, ktoré sme preskúmali, aby sme určili najrýchlejšie riešenie.
2. Príklad
Začnime nastavením príkladu, na ktorý sa budeme môcť odvolávať v tomto návode.
Najskôr si predstavíme maticu 3 × 2:
Poďme si teraz predstaviť druhú maticu, tentoraz dva riadky o štyri stĺpce:
Potom sa vynásobí prvá matica druhou maticou, výsledkom čoho bude matica 3 × 4:
Ako pripomienka, tento výsledok sa získa výpočtom každej bunky výslednej matice pomocou tohto vzorca:
Kde r je počet riadkov matice A, c je počet stĺpcov matice B a n je počet stĺpcov matice A, ktoré sa musia zhodovať s počtom riadkov matice B.
3. Násobenie matice
3.1. Vlastná implementácia
Začnime s vlastnou implementáciou matíc.
Budeme to udržiavať jednoduché a spravodlivé používať dvojrozmerné dvojitý polia:
double [] [] firstMatrix = {new double [] {1d, 5d}, new double [] {2d, 3d}, new double [] {1d, 7d}}; double [] [] secondMatrix = {new double [] {1d, 2d, 3d, 7d}, new double [] {5d, 2d, 8d, 1d}};To sú dve matice nášho príkladu. Vytvorme ten, ktorý sa očakáva ako výsledok ich znásobenia:
double [] [] očakávaný = {new double [] {26d, 12d, 43d, 12d}, nový double [] {17d, 10d, 30d, 17d}, nový double [] {36d, 16d, 59d, 14d}} ;Teraz, keď je všetko nastavené, implementujme multiplikačný algoritmus. Najskôr vytvoríme prázdne výsledkové pole a iterujeme jeho bunkami, aby sme do každého z nich uložili očakávanú hodnotu:
double [] [] multiplyMatrices (double [] [] firstMatrix, double [] [] secondMatrix) {double [] [] výsledok = nový double [firstMatrix.length] [secondMatrix [0] .length]; pre (int riadok = 0; riadok <result.length; riadok ++) {for (int col = 0; col <výsledok [riadok] .length; col ++) {výsledok [riadok] [col] = multiplyMatricesCell (firstMatrix, secondMatrix, riadok , col); }} vrátiť výsledok; }Na záver poďme implementovať výpočet jednej bunky. Aby sa to dosiahlo, použijeme vzorec uvedený skôr v prezentácii príkladu:
double multiplyMatricesCell (double [] [] firstMatrix, double [] [] secondMatrix, int riadok, int col) {dvojitá bunka = 0; for (int i = 0; i <secondMatrix.length; i ++) {cell + = firstMatrix [riadok] [i] * secondMatrix [i] [col]; } vratna bunka; }Na záver skontrolujeme, či sa výsledok algoritmu zhoduje s našim očakávaným výsledkom:
double [] [] actual = multiplyMatrices (firstMatrix, secondMatrix); assertThat (skutočné) .isEqualTo (očakávané);3.2. EJML
Prvá knižnica, na ktorú sa pozrieme, je EJML, čo je skratka pre Efficient Java Matrix Library. V čase písania tohto návodu to je jedna z naposledy aktualizovaných knižníc matice Java. Jeho účelom je byť čo najúčinnejší, pokiaľ ide o výpočet a využitie pamäte.
Budeme musieť pridať závislosť do knižnice v našom pom.xml:
org.ejml ejml-all 0,38 Použijeme v podstate rovnaký vzor ako predtým: vytvorenie dvoch matíc podľa nášho príkladu a skontrolujeme, či je výsledkom ich násobenia ten, ktorý sme vypočítali skôr.
Vytvorme teda svoje matice pomocou EJML. Na dosiahnutie tohto použijeme SimpleMatrix triedy, ktorú ponúka knižnica.
Môže to mať dvojrozmerný rozmer dvojitý pole ako vstup pre jeho konštruktor:
SimpleMatrix firstMatrix = nový SimpleMatrix (nový double [] [] {nový double [] {1d, 5d}, nový double [] {2d, 3d}, nový double [] {1d, 7d}}); SimpleMatrix secondMatrix = nový SimpleMatrix (nový double [] [] {nový double [] {1d, 2d, 3d, 7d}, nový double [] {5d, 2d, 8d, 1d}});A teraz definujme našu očakávanú maticu pre násobenie:
SimpleMatrix očakávaný = nový SimpleMatrix (nový double [] [] {nový double [] {26d, 12d, 43d, 12d}, nový double [] {17d, 10d, 30d, 17d}, nový double [] {36d, 16d, 59d, 14d}});Teraz, keď sme všetci pripravení, pozrime sa, ako spojiť dve matice dohromady. The SimpleMatrix trieda ponúka a mult () metóda brať ďalšie SimpleMatrix ako parameter a vrátenie násobenia dvoch matíc:
SimpleMatrix actual = firstMatrix.mult (secondMatrix);Skontrolujme, či sa získaný výsledok zhoduje s očakávaným.
Ako SimpleMatrix neprepíše rovná sa () metódou, nemôžeme sa spoliehať na to, že vykoná overenie. Ale, ponúka alternatívu: isIdentical () metóda ktorá berie nielen ďalší parameter matice, ale aj a dvojitý tolerancia chýb ignorovať malé rozdiely v dôsledku dvojitej presnosti:
assertThat (skutočné) .zhody (m -> m.isIdentical (očakávané, 0d));Tým sa končí násobenie matíc pomocou knižnice EJML. Pozrime sa, čo ponúkajú ostatní.
3.3. ND4J
Vyskúšajme teraz knižnicu ND4J. ND4J je výpočtová knižnica a je súčasťou projektu deeplearning4j. ND4J okrem iného ponúka funkcie výpočtu matice.
Najskôr musíme získať závislosť od knižnice:
org.nd4j nd4j-native 1.0.0-beta4 Upozorňujeme, že tu používame beta verziu, pretože sa zdá, že pri vydaní GA existujú nejaké chyby.
Kvôli stručnosti tieto dva rozmery neprepíšeme dvojitý polia a zamerať sa len na to, ako sa používajú s každou knižnicou. Takže s ND4J musíme vytvoriť INDArray. Za týmto účelom zavoláme Nd4j.create () továrenská metóda a odovzdať ju a dvojitý pole predstavujúce našu maticu:
Matica INDArray = Nd4j.create (/ * dvojrozmerné dvojité pole * /);Rovnako ako v predchádzajúcej časti, aj tu vytvoríme tri matice: dve, ktoré sa spoločne množíme a jedna je očakávaným výsledkom.
Potom chceme vlastne urobiť násobenie medzi prvými dvoma maticami pomocou INDArray.mmul () metóda:
INDArray actual = firstMatrix.mmul (secondMatrix);Potom znova skontrolujeme, či sa skutočný výsledok zhoduje s očakávaným. Tentokrát sa môžeme spoľahnúť na kontrolu rovnosti:
assertThat (skutočné) .isEqualTo (očakávané);To ukazuje, ako možno knižnicu ND4J použiť na maticové výpočty.
3.4. Apache Commons
Poďme si teraz povedať o module Apache Commons Math3, ktorý nám poskytuje matematické výpočty vrátane manipulácií s maticami.
Znova budeme musieť špecifikovať závislosť v našom pom.xml:
org.apache.commons commons-math3 3.6.1 Po nastavení môžeme použiť the RealMatrix rozhranie a jeho Array2DRowRealMatrix implementácia aby sme vytvorili naše obvyklé matice. Konštruktor implementačnej triedy má dvojrozmerný rozmer dvojitý pole ako jeho parameter:
Matica RealMatrix = nový Array2DRowRealMatrix (/ * dvojrozmerné dvojité pole * /);Čo sa týka násobenia matíc, the RealMatrix rozhranie ponúka a znásobiť () metóda brať ďalšie RealMatrix parameter:
RealMatrix skutočný = firstMatrix.multiply (secondMatrix);Konečne môžeme overiť, že výsledok sa rovná tomu, čo očakávame:
assertThat (skutočné) .isEqualTo (očakávané);Pozrime sa na ďalšiu knižnicu!
3.5. LA4J
Tento sa volá LA4J, čo je skratka pre Linear Algebra pre jazyk Java.
Pridajme závislosť aj pre túto:
org.la4j la4j 0,6.0 Teraz LA4J funguje podobne ako ostatné knižnice. Ponúka Matrix rozhranie s a Basic2DMatrix implementácia to trvá dvojrozmerne dvojitý pole ako vstup:
Maticová matica = nová Basic2DMatrix (/ * dvojrozmerné dvojité pole * /);Rovnako ako v module Apache Commons Math3, metóda násobenia je znásobiť () a vezme ďalšiu Matrix ako jeho parameter:
Skutočná matica = firstMatrix.multiply (secondMatrix);Opäť môžeme skontrolovať, či výsledok zodpovedá našim očakávaniam:
assertThat (skutočné) .isEqualTo (očakávané);Poďme sa teraz pozrieť na našu poslednú knižnicu: Colt.
3.6. Kolt
Colt je knižnica vyvinutá v CERN-e. Poskytuje funkcie umožňujúce vysoko výkonné vedecké a technické výpočty.
Rovnako ako v predchádzajúcich knižniciach, aj tu musíme získať správnu závislosť:
žriebä žriebä 1.2.0 Aby sme vytvorili matice s Coltom, musíme využiť Trieda DoubleFactory2D. Dodáva sa s tromi inštanciami z výroby: hustý, riedky a riadok komprimovaný. Každá z nich je optimalizovaná na vytvorenie zhodného druhu matice.
Pre náš účel použijeme hustý inštancia. Tentokrát, spôsob volania je urobiť() a trvá to dvojrozmerne dvojité pole opäť produkujúce a DoubleMatrix2D objekt:
DoubleMatrix2D matrix = doubleFactory2D.make (/ * dvojrozmerné dvojité pole * /);Po vytvorení inštancie našich matíc ich budeme chcieť znásobiť. Tentokrát neexistuje na maticovom objekte žiadna metóda, ktorá by to robila. Musíme vytvoriť inštanciu súboru Algebra trieda, ktorá má a mult () metóda pričom dve matice pre parametre:
Algebra algebra = nová Algebra (); DoubleMatrix2D actual = algebra.mult (firstMatrix, secondMatrix);Potom môžeme porovnať skutočný výsledok s očakávaným:
assertThat (skutočné) .isEqualTo (očakávané);4. Benchmarking
Teraz, keď sme skončili s preskúmaním rôznych možností násobenia matíc, poďme skontrolovať, ktoré sú najvýkonnejšie.
4.1. Malé matice
Začnime malými maticami. Tu matice 3 × 2 a 2 × 4.
Na implementáciu testu výkonnosti použijeme Benchmarkingová knižnica JMH. Nakonfigurujme testovaciu triedu s nasledujúcimi možnosťami:
public static void main (String [] args) hodí Exception {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 (); }Týmto spôsobom urobí JMH dva úplné behy pre každú metódu s poznámkami @Benchmark, každá s piatimi iteráciami zahrievania (nezapočítava sa do priemerného výpočtu) a desiatimi meracími. Pokiaľ ide o merania, zhromaždí sa priemerný čas vykonania rôznych knižníc v mikrosekundách.
Potom musíme vytvoriť objekt stavu obsahujúci naše polia:
@State (Scope.Benchmark) verejná trieda MatrixProvider {private double [] [] firstMatrix; súkromné dvojité [] [] secondMatrix; public MatrixProvider () {firstMatrix = new double [] [] {new double [] {1d, 5d}, new double [] {2d, 3d}, new double [] {1d, 7d}}; secondMatrix = nový double [] [] {nový double [] {1d, 2d, 3d, 7d}, nový double [] {5d, 2d, 8d, 1d}}; }}Týmto spôsobom zabezpečíme, aby inicializácia polí nebola súčasťou benchmarkingu. Potom musíme ešte vytvoriť metódy na násobenie matíc pomocou funkcie MatrixProvider objekt ako zdroj údajov. Nebudeme tu opakovať kód, pretože sme jednotlivé knižnice videli skôr.
Na záver spustíme proces testovania pomocou nášho hlavný metóda. Získame tak nasledujúci výsledok:
Benchmark Mode Cnt Score Error Units MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1008 ± 0,032 nás / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0219 ± 0,014 nás / op MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0226 ± 0,013 nás / op MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20. 0389 ± 0045 nás / op MatrixMultiplicationBenchmarking.la4jMatrixMultiplication priem. 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication priem. 20 12 670 ± 2 582 us / opAko vidíme, EJML a Kolt fungujú naozaj dobre s asi pätinou mikrosekundy na operáciu, kde ND4j je menej výkonný s o niečo viac ako desiatimi mikrosekundami na operáciu. Ostatné knižnice majú predstavenia umiestnené medzi nimi.
Tiež stojí za zmienku, že pri zvyšovaní počtu zahrievacích iterácií z 5 na 10 sa zvyšuje výkon všetkých knižníc.
4.2. Veľké matice
Čo sa stane, ak vezmeme väčšie matice, napríklad 3000 × 3000? Aby sme skontrolovali, čo sa stane, najskôr vytvoríme ďalšiu triedu stavu poskytujúcu vygenerované matice tejto veľkosti:
@State (Scope.Benchmark) verejná trieda BigMatrixProvider {private double [] [] firstMatrix; súkromné dvojité [] [] secondMatrix; public BigMatrixProvider () {} @Setup nastavenie verejnej neplatnosti (parametre BenchmarkParams) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } private double [] [] createMatrix () {Random random = new Random (); výsledok double [] [] = nový double [3000] [3000]; pre (int riadok = 0; riadok <result.length; riadok ++) {for (int col = 0; col <výsledok [riadok] .length; col ++) {výsledok [riadok] [col] = random.nextDouble (); }} vrátiť výsledok; }}Ako vidíme, vytvoríme dvojrozmerné polia 3000 × 3000 vyplnené náhodnými reálnymi číslami.
Poďme teraz vytvoriť testovaciu triedu:
public class BigMatrixMultiplicationBenchmarking {public static void main (String [] args) hodí Exception {Map parameters = parseParameters (args); ChainedOptionsBuilder builder = new OptionsBuilder () .include (BigMatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime). Forks (2) .warmupIterations (10) .measurementIterations (10) .timeUnit (TimeUnit.SONDS) nový 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 = nový SimpleMatrix (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = nový SimpleMatrix (matrixProvider.getSecondMatrix ()); návrat firstMatrix.mult (secondMatrix); } @Benchmark public Object apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = nový Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = nový Array2DRowRealMatrix (matrixProvider.getSecondMatrix ()); návrat firstMatrix.multiply (secondMatrix); } @Benchmark public Object la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = nový Basic2DMatrix (matrixProvider.getFirstMatrix ()); Matrix secondMatrix = nový Basic2DMatrix (matrixProvider.getSecondMatrix ()); návrat firstMatrix.multiply (secondMatrix); } @Benchmark public Object nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); návrat 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 = nová Algebra (); návratová algebra.mult (firstMatrix, secondMatrix); }}Keď spustíme tento test, dostaneme úplne odlišné výsledky:
Porovnávací režim Cnt Skóre Chyba jednotky 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 priem. 20 35,523 ± 0,102 s / op BigMatrixMultiplicationBenchmarking.nd4jMatrixMultiplication priem. 20 0,548 ± 0,006 s / opAko vidíme, domáce implementácie a knižnica Apache sú teraz oveľa horšie ako predtým, pričom znásobenie týchto dvoch matíc trvá takmer 10 minút.
Koltovi to trvá o niečo viac ako 3 minúty, čo je lepšie, ale stále veľmi dlhé. EJML a LA4J si vedú veľmi dobre, pretože bežia takmer za 30 sekúnd. Ale je to ND4J, ktorý vyhráva tento benchmarking za menej ako sekundu na backend CPU.
4.3. Analýza
To nám ukazuje, že výsledky testovania skutočne závisia od charakteristík matíc, a preto je zložité poukázať na jediného víťaza.
5. Záver
V tomto článku sme sa naučili, ako násobiť matice v Jave, a to buď sami, alebo pomocou externých knižníc. Po preskúmaní všetkých riešení sme vykonali test všetkých z nich a zistili sme, že až na ND4J si všetky na malých matriciach počínali dosť dobre. Na druhej strane sa na väčších maticiach ujíma vedenia ND4J.
Celý kód tohto článku nájdete ako obvykle na GitHub.
