Matrix szorzás Java-ban

1. Áttekintés

Ebben az oktatóanyagban megnézzük, hogyan szaporíthatunk két mátrixot a Java-ban.

Mivel a mátrixkoncepció nem létezik natív módon a nyelvben, mi magunk fogjuk megvalósítani, és néhány könyvtárral is együttműködünk, hogy lássuk, hogyan kezelik a mátrixok szorzását.

Végül egy kis összehasonlító elemzést készítünk a különböző megoldásokról, amelyeket feltártunk, hogy meghatározzuk a leggyorsabb megoldást.

2. A példa

Kezdjük egy olyan példa felállításával, amelyre az oktatóanyagban hivatkozhatunk.

Először egy 3 × 2 mátrixot fogunk elképzelni:

Most képzeljünk el egy második mátrixot, két sor négy oszloppal:

Ezután az első mátrix szorzata a második mátrixszal, amely 3 × 4 mátrixot eredményez:

Emlékeztetőül, ezt az eredményt úgy kapjuk, hogy a kapott mátrix minden celláját kiszámítjuk ezzel a képlettel:

Hol r a mátrix sorainak száma A, c a mátrix oszlopainak száma B és n a mátrix oszlopainak száma A, amelynek meg kell egyeznie a mátrix sorainak számával B.

3. Mátrixszorzás

3.1. Saját megvalósítás

Kezdjük a mátrixok saját megvalósításával.

Mi ezt egyszerűen és igazságosan fogjuk tartani kétdimenziós kettős tömbök:

dupla [] [] firstMatrix = {új dupla [] {1d, 5d}, új dupla [] {2d, 3d}, új dupla [] {1d, 7d}}; double [] [] secondMatrix = {új kettős [] {1d, 2d, 3d, 7d}, új kettős [] {5d, 2d, 8d, 1d}};

Ez a példánk két mátrixa. Készítsük el azt, amelyik szorzásuk eredményeként várható:

dupla [] [] várható = {új dupla [] {26d, 12d, 43d, 12d}, új dupla [] {17d, 10d, 30d, 17d}, új dupla [] {36d, 16d, 59d, 14d}} ;

Most, hogy minden be van állítva, valósítsuk meg a szorzási algoritmust. Először létrehozunk egy üres eredménytömböt, és iterálunk a celláin keresztül, hogy mindegyikben tároljuk a várható értéket:

dupla [] [] szorzásMátrixok (dupla [] [] elsőMátrix, kettős [] [] másodikMátrix) {kettős [] [] eredmény = új kettős [elsőMátrix.hossz] [másodMátrix [0] .hossz]; for (int sor = 0; sor <eredmény.hossz; sor ++) {for (int col = 0; col <eredmény [sor] .hossz; col ++) {eredmény [sor] [oszlop] = szorozMatricesCell (elsőMátrix, másodikMátrix, sor , col); }} visszatérési eredmény; }

Végül valósítsuk meg egyetlen cella számítását. Ennek elérése érdekében a példa bemutatásánál korábban bemutatott képletet fogjuk használni:

dupla szorzásMatricesCell (dupla [] [] elsőMátrix, kettős [] [] másodikMátrix, int sor, int col) {kettős cella = 0; for (int i = 0; i <másodpercMátrix.hossz; i ++) {cella + = elsőMátrix [sor] [i] * másodikMátrix [i] [oszlop]; } visszatérő cella; }

Végül ellenőrizzük, hogy az algoritmus eredménye megegyezik-e a várt eredményünkkel:

dupla [] [] tényleges = szorzásMátrixok (elsőMátrix, másodikMátrix); assertThat (tényleges) .isEqualTo (várható);

3.2. EJML

Az első könyvtár, amelyet megnézünk, az EJML, amely az Efficient Java Matrix Library rövidítése. A bemutató megírásakor ez az az egyik legfrissebb Java mátrix könyvtár. Célja, hogy a lehető leghatékonyabb legyen a számítások és a memóriahasználat szempontjából.

Hozzá kell adnunk a könyvtár függőségét a könyvtárunkban pom.xml:

 org.ejml ejml-mind 0,38 

Nagyjából ugyanazt a mintát fogjuk használni, mint korábban: két mátrixot hozunk létre a példánk szerint, és ellenőrizzük, hogy szorzásuk eredménye megegyezik-e az általunk korábban kiszámítottakkal.

Tehát hozzuk létre az EJML segítségével a mátrixainkat. Ennek elérése érdekében használjuk a SimpleMatrix osztály által kínált könyvtár.

Két dimenzióba kerülhet kettős tömb a konstruktor bemeneteként:

SimpleMatrix firstMatrix = új SimpleMatrix (új dupla [] [] {új dupla [] {1d, 5d}, új dupla [] {2d, 3d}, új dupla [] {1d, 7d}}); SimpleMatrix secondMatrix = új SimpleMatrix (új dupla [] [] {új dupla [] {1d, 2d, 3d, 7d}, új dupla [] {5d, 2d, 8d, 1d}});

Most pedig definiáljuk a szorzás várható mátrixát:

Várható SimpleMatrix = új SimpleMatrix (új dupla [] [] {új dupla [] {26d, 12d, 43d, 12d}, új dupla [] {17d, 10d, 30d, 17d}, új dupla [] {36d, 16d, 59d, 14d}});

Most, hogy mindannyian felkészültünk, nézzük meg, hogyan lehet megszorozni a két mátrixot együtt. A SimpleMatrix osztály kínál a mult () módszer vesz egy másikat SimpleMatrix paraméterként és visszaadva a két mátrix szorzását:

SimpleMatrix aktuális = firstMatrix.mult (secondMatrix);

Ellenőrizzük, hogy a kapott eredmény megfelel-e a vártnak.

Mint SimpleMatrix nem írja felül a egyenlő () módszerrel nem támaszkodhatunk rá az ellenőrzés elvégzéséhez. De, alternatívát kínál: a isIdentical () módszer amely nemcsak egy másik mátrixparamétert vesz fel, hanem a kettős hibatűrés, a kettős pontosság miatti kis különbségek figyelmen kívül hagyása:

assertThat (tényleges) .egyezik (m -> m.isIdentical (várható, 0d));

Ezzel lezárul a mátrixok szorzása az EJML könyvtárral. Lássuk, mit kínálnak a többiek.

3.3. ND4J

Próbálja ki most az ND4J könyvtárat. Az ND4J egy számítási könyvtár, és része a deeplearning4j projektnek. Az ND4J többek között mátrixszámítási funkciókat kínál.

Először meg kell kapnunk a könyvtár függőségét:

 org.nd4j nd4j-natív 1.0.0-beta4 

Vegye figyelembe, hogy itt a béta verziót használjuk, mert úgy tűnik, hogy vannak hibák a GA kiadással.

A rövidség kedvéért nem írjuk át a két dimenziót kettős tömböket, és csak arra kell összpontosítani, hogy miként használják az egyes könyvtárakat. Így az ND4J segítségével létre kell hoznunk egy INDArray. Ennek érdekében felhívjuk a Nd4j.create () gyári módszer és adja át a kettős tömb reprezentálja a mátrixunkat:

INDArray mátrix = Nd4j.create (/ * kétdimenziós dupla tömb * /);

Az előző szakaszhoz hasonlóan három mátrixot is létrehozunk: a kettőt együtt szorozzuk, és az egyik a várt eredmény.

Ezt követően az első két mátrix közötti szorzást akarjuk elvégezni a INDArray.mmul () módszer:

INDArray tényleges = firstMatrix.mmul (secondMatrix);

Ezután újra ellenőrizzük, hogy a tényleges eredmény megfelel-e a várt eredménynek. Ezúttal az egyenlőség ellenőrzésére támaszkodhatunk:

assertThat (tényleges) .isEqualTo (várható);

Ez bemutatja, hogy az ND4J könyvtár hogyan használható mátrixszámításra.

3.4. Apache Commons

Beszéljünk most az Apache Commons Math3 modulról, amely matematikai számításokat nyújt számunkra, beleértve a mátrix manipulációkat is.

Ismét meg kell adnunk a függőséget a pom.xml:

 org.apache.commons commons-math3 3.6.1 

Miután beállítottuk, használhatjuk a RealMatrix interfész és annak Array2DRowRealMatrix végrehajtás hogy létrehozzuk a szokásos mátrixainkat. A megvalósítási osztály kivitelezője kétdimenziós kettős tömb paraméterként:

RealMatrix mátrix = new Array2DRowRealMatrix (/ * kétdimenziós dupla tömb * /);

Ami a mátrixok szorzását illeti, a RealMatrix interfész kínál a szorozni () módszer vesz egy másikat RealMatrix paraméter:

RealMatrix tényleges = firstMatrix.multiply (secondMatrix);

Végül ellenőrizhetjük, hogy az eredmény megegyezik-e azzal, amit várunk:

assertThat (tényleges) .isEqualTo (várható);

Nézzük meg a következő könyvtárat!

3.5. LA4J

Ennek a neve LA4J, amely a Linear Algebra Java-t jelenti.

Tegyük hozzá ennek a függőségét is:

 org.la4j la4j 0.6.0 

Az LA4J nagyjából úgy működik, mint a többi könyvtár. Felajánlja a Mátrix interfész a Basic2DMatrix végrehajtás hogy kétdimenziós kettős tömb bemenetként:

Matrix mátrix = new Basic2DMatrix (/ * kétdimenziós dupla tömb * /);

Mint az Apache Commons Math3 modulban, a szorzási módszer az szorozni () és elvesz egy másikat Mátrix paraméterként:

Mátrix tényleges = firstMatrix.multiply (secondMatrix);

Még egyszer ellenőrizhetjük, hogy az eredmény megfelel-e az elvárásainknak:

assertThat (tényleges) .isEqualTo (várható);

Vessünk egy pillantást utolsó könyvtárunkra: Colt.

3.6. Csikó

A Colt a CERN által fejlesztett könyvtár. Olyan funkciókat kínál, amelyek lehetővé teszik a nagy teljesítményű tudományos és műszaki számítást.

A korábbi könyvtárakhoz hasonlóan a megfelelő függőséget is meg kell kapnunk:

 csikós csikó 1.2.0 

Ahhoz, hogy mátrixokat hozzunk létre Colt segítségével, ki kell használnunk a DoubleFactory2D osztály. Három gyári példány érkezik: sűrű, ritka és sorTömörített. Mindegyik optimalizálva van a megfelelő típusú mátrix létrehozására.

Célunkhoz a sűrű példa. Ezúttal, a hívás módja az gyártmány () és kétdimenziós kell kettős tömb ismét előállítva a DoubleMatrix2D tárgy:

DoubleMatrix2D mátrix = doubleFactory2D.make (/ * kétdimenziós dupla tömb * /);

Amint mátrixaink példányosak, meg akarjuk szorozni őket. Ezúttal a mátrix objektumon nincs módszer erre. Létre kell hoznunk a Algebra osztály, amelynek van egy mult () módszer két mátrixot veszünk a paraméterekhez:

Algebra algebra = új Algebra (); DoubleMatrix2D aktuális = algebra.mult (firstMatrix, secondMatrix);

Ezután összehasonlíthatjuk a tényleges eredményt a vártval:

assertThat (tényleges) .isEqualTo (várható);

4. Benchmarking

Most, hogy befejeztük a mátrixszorzás különféle lehetőségeinek feltárását, ellenőrizzük, melyek a legjobban teljesítők.

4.1. Kis mátrixok

Kezdjük kis mátrixokkal. Itt egy 3 × 2 és egy 2 × 4 mátrix.

A teljesítményteszt végrehajtásához a JMH benchmarking könyvtár. Konfiguráljuk az benchmarking osztályt a következő lehetőségekkel:

public static void main (String [] args) dobja a Kivételt {Options opt = new OptionsBuilder () .include (MatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .villa (2) .warmupIterations (5) .measurementIterations (10) .timeUnit (TimeUnit.MICROSECONDS) .build (); új Runner (opt) .run (); }

Így a JMH két teljes futást hajt végre minden egyes metódussal, amelyekhez a jegyzetet adták @Viszonyítási alap, mindegyik öt felmelegedési iterációval (az átlagos számításba nem számítva) és tíz méréssel. Ami a méréseket illeti, a különböző könyvtárak átlagos végrehajtási idejét gyűjti össze mikroszekundumokban.

Ezután létre kell hoznunk egy olyan állapotobjektumot, amely a tömbjeinket tartalmazza:

@State (Scope.Benchmark) public class MatrixProvider {private double [] [] firstMatrix; privát dupla [] [] másodpercMátrix; public MatrixProvider () {firstMatrix = new double [] [] {new double [] {1d, 5d}, new double [] {2d, 3d}, new double [] {1d, 7d}}; secondMatrix = új kettős [] [] {új kettős [] {1d, 2d, 3d, 7d}, új kettős [] {5d, 2d, 8d, 1d}}; }}

Így megbizonyosodunk arról, hogy a tömbök inicializálása nem része a benchmarkingnak. Ezt követően még mindig létre kell hoznunk a mátrixok szorzását végző módszereket a MatrixProvider objektum mint adatforrás. Itt nem fogjuk megismételni a kódot, mivel minden könyvtárat korábban láttunk.

Végül lefuttatjuk a benchmarking folyamatot a mi segítségével fő- módszer. Ez a következő eredményt adja:

Benchmark Mode Cnt Score Error egységek MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1008 ± 0032 us / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0219 ± 0014 us / op MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0226 ± 0013 us / op MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 0389 ± 0045 us / op MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12,670 ± 2,582 us / op

Ahogy látjuk, EJML és Csikó nagyon jól teljesítenek műveletenként körülbelül egy mikroszekundummal, ahol ND4j kevésbé teljesítő, műveletenként valamivel több, mint tíz mikroszekundum. A többi könyvtár között vannak előadások.

Érdemes megjegyezni azt is, hogy amikor a bemelegítő iterációk számát 5-ről 10-re növeljük, az összes könyvtár esetében növekszik a teljesítmény.

4.2. Nagy mátrixok

Mi történik, ha nagyobb mátrixokat veszünk fel, például 3000 × 3000? A történtek ellenőrzéséhez először hozzunk létre egy másik állapotosztályt, amely akkora generált mátrixokat biztosít:

@State (Scope.Benchmark) nyilvános osztály BigMatrixProvider {private double [] [] firstMatrix; privát dupla [] [] másodpercMátrix; public BigMatrixProvider () {} @Setup public void setup (BenchmarkParams paraméterek) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } private double [] [] createMatrix () {Véletlenszerű véletlenszerű = új Véletlenszerű (); dupla [] [] eredmény = új dupla [3000] [3000]; for (int sor = 0; sor <eredmény.hossz; sor ++) {for (int col = 0; col <eredmény [sor] .hossz; col ++) {eredmény [sor] [col] = véletlen.nextDouble (); }} visszatérési eredmény; }}

Mint láthatjuk, 3000 × 3000 méretű kétdimenziós kettős tömböt hozunk létre véletlenszerű valós számokkal.

Most hozzuk létre az benchmarking osztályt:

public class BigMatrixMultiplicationBenchmarking {public static void main (String [] args) dobja a Kivételt {Map parameters = parseParameters (args); ChainedOptionsBuilder builder = new OptionsBuilder () .include (BigMatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .villák (2) .warmupIterations (10) .measurementIterations (10) .timeUnit (TimeUnit. TimeUnit. TimeUnit új 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 = új SimpleMatrix (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = új SimpleMatrix (matrixProvider.getSecondMatrix ()); return firstMatrix.mult (secondMatrix); } @Benchmark public Object apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = new Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = new Array2DRowRealMatrix (matrixProvider.getSecondMatrix ()); return firstMatrix.multiply (secondMatrix); } @Benchmark public Object la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = új Basic2DMatrix (matrixProvider.getFirstMatrix ()); Matrix secondMatrix = új Basic2DMatrix (matrixProvider.getSecondMatrix ()); return firstMatrix.multiply (secondMatrix); } @Benchmark public Object nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); return 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 = új Algebra (); return algebra.mult (firstMatrix, secondMatrix); }}

A benchmarking futtatásakor teljesen más eredményeket kapunk:

Benchmark Mode Cnt Score Error egységek 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

Mint láthatjuk, a házi megvalósítások és az Apache könyvtár most sokkal rosszabb, mint korábban, csaknem 10 percet vesz igénybe a két mátrix szorzása.

Colt valamivel több mint 3 percet vesz igénybe, ami jobb, de még mindig nagyon hosszú. Az EJML és az LA4J elég jól teljesít, mivel közel 30 másodperc alatt futnak. De az ND4J nyeri ezt az összehasonlító teljesítményt egy másodperc alatt CPU háttérprogramon.

4.3. Elemzés

Ez azt mutatja számunkra, hogy az összehasonlító eredmények valóban a mátrixok jellemzőitől függenek, ezért bonyolult egyetlen nyertest kiemelni.

5. Következtetés

Ebben a cikkben megtanultuk, hogyan lehet saját magunkkal vagy külső könyvtárakkal szaporítani a mátrixokat a Java-ban. Az összes megoldás feltárása után összehasonlító elemzést készítettünk mindegyikről, és láttuk, hogy az ND4J kivételével mind nagyon jól teljesítenek kis mátrixokon. Másrészt nagyobb mátrixokon az ND4J veszi át a vezetést.

Szokás szerint a cikk teljes kódja megtalálható a GitHubon.