streamalism.org

1. סקירה כללית

במדריך זה נבחן כיצד נוכל להכפיל שתי מטריצות ב- Java.

מכיוון שתפישת המטריצה ​​אינה קיימת בשפה המקומית, אנו ניישם אותה בעצמנו, ונעבוד גם עם כמה ספריות כדי לראות כיצד הן מטפלות בכפל מטריצות.

בסופו של דבר, נעשה מעט ביצועים של פתרונות שונים שבדקנו כדי לקבוע את המהיר ביותר.

2. הדוגמה

נתחיל בהגדרת דוגמה שנוכל להתייחס אליה במהלך כל הדרכה זו.

ראשית, נדמיין מטריצה ​​של 3 × 2:

בואו נדמיין מטריצה ​​שנייה, שתי שורות על ארבע עמודות הפעם:

לאחר מכן, הכפל של המטריצה ​​הראשונה במטריצה ​​השנייה, שתביא למטריצה ​​של 3 × 4:

כתזכורת, תוצאה זו מתקבלת על ידי חישוב כל תא של המטריצה ​​המתקבלת באמצעות נוסחה זו:

איפה ר הוא מספר שורות המטריצה א, ג הוא מספר העמודות של המטריצה ב ו נ הוא מספר העמודות של המטריצה א, אשר חייב להתאים למספר שורות המטריצה ב.

3. כפל מטריקס

3.1. יישום עצמי

נתחיל מיישום מטריצות משלנו.

נשמור על זה פשוט וצודק השתמש דו מימדי לְהַכפִּיל מערכים:

כפול [] [] firstMatrix = כפול חדש [] {1d, 5d}, כפול חדש [] {2d, 3d}, כפול חדש [] {1d, 7d}}; כפול [] [] secondMatrix = {כפול חדש [] {1d, 2d, 3d, 7d}, כפול חדש [] {5d, 2d, 8d, 1d}};

אלה שתי המטריצות של הדוגמה שלנו. בואו ניצור את זה הצפוי כתוצאה מכפלם:

כפול [] [] צפוי = {חדש כפול [] {26d, 12d, 43d, 12d}, כפול חדש [] {17d, 10d, 30d, 17d}, כפול חדש [] {36d, 16d, 59d, 14d}} ;

עכשיו, כשהכל מוגדר, בואו נשתמש באלגוריתם הכפל. ראשית ניצור מערך תוצאות ריק ונחזור דרך התאים שלו כדי לאחסן את הערך הצפוי בכל אחד מהם:

כפול [] [] multiplyMatrices (כפול [] [] firstMatrix, כפול [] [] secondMatrix) {כפול [] [] תוצאה = כפול חדש [firstMatrix.length] [secondMatrix [0] .length]; עבור (int שורה = 0; שורה <result.length; שורה ++) {עבור (int col = 0; col <תוצאה [שורה] .length; col ++) {תוצאה [שורה] [col] = multiplyMatricesCell (firstMatrix, secondMatrix, שורה , col); }} להחזיר תוצאה; }

לבסוף, בואו נבצע חישוב של תא בודד. על מנת להשיג זאת, נשתמש בנוסחה שהוצגה קודם לכן בהצגת הדוגמה:

כפול multiplyMatricesCell (כפול [] [] firstMatrix, כפול [] [] secondMatrix, int שורה, int col) {תא כפול = 0; עבור (int i = 0; i <secondMatrix.length; i ++) {cell + = firstMatrix [row] [i] * secondMatrix [i] [col]; } החזרת תא; }

לסיום, בואו נבדוק שתוצאת האלגוריתם תואמת את התוצאה הצפויה שלנו:

כפול [] [] בפועל = multiplyMatrices (firstMatrix, secondMatrix); assertThat (בפועל). isEqualTo (צפוי);

3.2. EJML

הספרייה הראשונה שנבחן היא EJML, שמייצג את ספריית ה- Java Matrix יעילה. בזמן כתיבת הדרכה זו, זה אחת מספריות מטריצות Java שעודכנו לאחרונה. מטרתו להיות יעילה ככל האפשר בכל הקשור לחישוב ולשימוש בזיכרון.

נצטרך להוסיף את התלות בספרייה שלנו pom.xml:

 org.ejml ejml-all 0.38 

נשתמש באותה תבנית כמו קודם: ליצור שתי מטריצות לפי הדוגמה שלנו ולבדוק שתוצאת הכפל שלהן היא זו שחישבנו קודם.

אז בואו ניצור את המטריצות שלנו באמצעות EJML. על מנת להשיג זאת, נשתמש ב- SimpleMatrix שיעור המוצע על ידי הספרייה.

זה יכול לקחת דו מימד לְהַכפִּיל מערך כקלט לבנאי שלו:

SimpleMatrix firstMatrix = חדש SimpleMatrix (כפול חדש [] [] {חדש כפול [] {1d, 5d}, כפול חדש [] {2d, 3d}, כפול חדש [] {1d, 7d}}); SimpleMatrix secondMatrix = חדש SimpleMatrix (כפול חדש [] [] {כפול חדש [] {1d, 2d, 3d, 7d}, כפול חדש [] {5d, 2d, 8d, 1d}});

ועכשיו, בואו נגדיר את המטריצה ​​הצפויה שלנו לכפל:

SimpleMatrix צפוי = SimpleMatrix חדש (כפול חדש [] [] {כפול חדש [] {26d, 12d, 43d, 12d}, כפול חדש [] {17d, 10d, 30d, 17d}, כפול חדש [] {36d, 16d, 59 ד, 14 ד}});

עכשיו כשכולנו ערוכים, בואו נראה איך להכפיל את שתי המטריצות יחד. ה SimpleMatrix הכיתה מציעה א רב () שיטה לוקח עוד אחד SimpleMatrix כפרמטר ומחזיר את הכפל של שתי המטריצות:

SimpleMatrix בפועל = firstMatrix.mult (secondMatrix);

בואו לבדוק אם התוצאה שהתקבלה תואמת את התוצאה הצפויה.

כפי ש SimpleMatrix אינו עוקף את שווים() בשיטה, אנחנו לא יכולים לסמוך עליה כדי לבצע את האימות. אבל, הוא מציע חלופה: isIdentical () שיטה שלוקח לא רק פרמטר מטריצה ​​נוסף אלא גם a לְהַכפִּיל סובלנות תקלות אחד להתעלם מהבדלים קטנים בגלל דיוק כפול:

assertThat (בפועל) .matches (m -> m.is זהות (צפוי, 0d));

בכך מסתיים הכפל של מטריצות עם ספריית EJML. בואו נראה מה האחרים מציעים.

3.3. ND4J

בואו ננסה כעת את ספריית ND4J. ND4J היא ספריית חישוב והיא חלק מפרויקט deeplearning4j. בין היתר, ND4J מציעה תכונות חישוב מטריצות.

קודם כל עלינו להשיג את התלות בספריה:

 org.nd4j nd4j-native 1.0.0-beta4 

שים לב שאנחנו משתמשים בגרסת בטא כאן מכיוון שנראה שיש כמה באגים עם שחרור GA.

מטעמי קיצור, לא נכתוב מחדש את שני הממדים לְהַכפִּיל מערכים ופשוט התמקדו כיצד משתמשים בהם בכל ספרייה. לפיכך, עם ND4J, עלינו ליצור INDArray. על מנת לעשות זאת, נקרא Nd4j.create () שיטת המפעל ולהעביר אותה א לְהַכפִּיל מערך המייצג את המטריצה ​​שלנו:

מטריצת INDArray = Nd4j.create (/ * מערך כפול דו מימדי * /);

כמו בסעיף הקודם, ניצור שלוש מטריצות: השניים שנכפיל יחד וזו התוצאה הצפויה.

לאחר מכן, אנו רוצים לבצע את הכפל בין שתי המטריצות הראשונות באמצעות ה- INDArray.mmul () שיטה:

INDArray בפועל = firstMatrix.mmul (secondMatrix);

לאחר מכן, אנו בודקים שוב שהתוצאה בפועל תואמת את התוצאה הצפויה. הפעם נוכל להסתמך על בדיקת שוויון:

assertThat (בפועל). isEqualTo (צפוי);

זה מדגים כיצד ניתן להשתמש בספריית ND4J לביצוע חישובי מטריצה.

3.4. אפאצ'י קומונס

בואו נדבר עכשיו על מודול Apache Commons Math3, המספק לנו חישובים מתמטיים כולל מניפולציות של מטריצות.

שוב, נצטרך לציין את התלות שלנו pom.xml:

 org.apache.commons commons-math3 3.6.1 

לאחר ההגדרה נוכל להשתמש ה RealMatrix ממשק שלו Array2DRowRealMatrix יישום כדי ליצור את המטריצות הרגילות שלנו. הקונסטרוקטור של כיתת היישום לוקח דו מימד לְהַכפִּיל מערך כפרמטר שלו:

מטריקס RealMatrix = Array2DRowRealMatrix חדש (/ * מערך כפול דו מימדי * /);

באשר להכפלת מטריצות, ה RealMatrix ממשק מציע לְהַכפִּיל() שיטה לוקח עוד אחד RealMatrix פָּרָמֶטֶר:

RealMatrix בפועל = firstMatrix.multiply (secondMatrix);

סוף סוף נוכל לוודא שהתוצאה שווה למה שאנחנו מצפים:

assertThat (בפועל). isEqualTo (צפוי);

בואו נראה את הספרייה הבאה!

3.5. LA4J

זה נקרא LA4J, שמייצג אלגברה לינארית עבור Java.

בואו נוסיף את התלות גם זו:

 org.la4j la4j 0.6.0 

עכשיו, LA4J עובד בערך כמו הספריות האחרות. הוא מציע מַטרִיצָה ממשק עם Basic2DMatrix יישום שלוקח דו מימד לְהַכפִּיל מערך כקלט:

מטריקס מטריקס = Basic2DMatrix חדש (/ * מערך כפול דו ממדי * /);

כמו במודול Apache Commons Math3, שיטת הכפל היא לְהַכפִּיל() ולוקח אחר מַטרִיצָה כפרמטר שלו:

מטריקס בפועל = firstMatrix.multiply (secondMatrix);

שוב נוכל לבדוק שהתוצאה תואמת את הציפיות שלנו:

assertThat (בפועל). isEqualTo (צפוי);

בואו נסתכל בספרייה האחרונה שלנו: קולט.

3.6. סוּסוֹן

קולט היא ספרייה שפותחה על ידי CERN. הוא מספק תכונות המאפשרות ביצועים גבוהים של מחשוב מדעי וטכני.

כמו בספריות הקודמות, עלינו לקבל את התלות הנכונה:

 קולט קולט 1.2.0 

על מנת ליצור מטריצות עם קולט, עלינו לעשות שימוש ב מחלקה DoubleFactory2D. זה מגיע עם שלושה מקרים מפעליים: צפוף, דליל ו שורה דחוסה. כל אחד מהם מותאם ליצירת סוג מטריצה ​​תואם.

למטרתנו, נשתמש ב- צָפוּף למשל. הפעם, השיטה להתקשר היא עשה() וזה לוקח דו מימד מערך כפול שוב, מייצר א DoubleMatrix2D לְהִתְנַגֵד:

מטריצה ​​של DoubleMatrix2D = doubleFactory2D.make (/ * מערך כפול דו ממדי * /);

ברגע שהמטריצות שלנו מיוצרות, נרצה להכפיל אותן. הפעם, אין שום שיטה על אובייקט המטריצה ​​לעשות זאת. עלינו ליצור מופע של ה- אַלגֶבּרָה כיתה שיש בה רב () שיטה לקיחת שתי מטריצות לפרמטרים:

אלגברה אלגברה = אלגברה חדשה (); DoubleMatrix2D actual = algebra.mult (firstMatrix, secondMatrix);

לאחר מכן אנו יכולים להשוות את התוצאה בפועל לתוצאה הצפויה:

assertThat (בפועל). isEqualTo (צפוי);

4. מידוד

עכשיו כשסיימנו לבחון את האפשרויות השונות של הכפלת מטריצות, בואו לבדוק אילו הביצועים ביותר הם.

4.1. מטריצות קטנות

נתחיל עם מטריצות קטנות. הנה, מטריצות 3 × 2 ו- 2 × 4.

על מנת ליישם את מבחן הביצועים, נשתמש ב- ספריית ביצועים של JMH. בואו להגדיר כיתת מידוד עם האפשרויות הבאות:

main static public ריק (String [] args) זורק Exception {Options opt = new OptionsBuilder () .include (MatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime). forks (2). warmupIterations (5) .measurementIterations (10) .timeUnit (TimeUnit.MICROSECONDS) .build (); רץ חדש (opt) .run (); }

בדרך זו, JMH יבצע שתי ריצות מלאות עבור כל שיטה עם הערות @ בנצ'מרק, לכל אחד מהם חמש איטרציות חימום (לא נלקחות בחישוב הממוצע) ועשרה מדידות. באשר למדידות, הוא יאסוף את זמן הביצוע הממוצע של הספריות השונות, במיקרו-שניות.

לאחר מכן עלינו ליצור אובייקט מדינה המכיל את המערכים שלנו:

@State (Scope.Benchmark) מחלקה ציבורית MatrixProvider {פרטי כפול [] [] firstMatrix; כפול פרטי [] [] secondMatrix; MatrixProvider ציבורי () {firstMatrix = כפול חדש [] [] {כפול חדש [] {1d, 5d}, כפול חדש [] {2d, 3d}, כפול חדש [] {1d, 7d}}; secondMatrix = כפול חדש [] [] כפול חדש [] {1d, 2d, 3d, 7d}, כפול חדש [] {5d, 2d, 8d, 1d}}; }}

באופן זה, אנו מוודאים כי אתחול מערכים אינו חלק מהמידוד. אחרי זה, אנחנו עדיין צריכים ליצור שיטות שעושות את הכפל של המטריצות באמצעות ה- MatrixProvider אובייקט כמקור הנתונים. לא נחזור על הקוד כאן כפי שראינו כל ספרייה קודם לכן.

לבסוף נפעיל את תהליך המידוד באמצעות שלנו רָאשִׁי שיטה. זה נותן לנו את התוצאה הבאה:

בנצ'מרק מצב CNT שגיאה ציון יחידות MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1008 ± 0,032 אותנו / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0219 ± 0,014 אותנו / op MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0226 ± 0,013 אותנו / op MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 0389 ± 0,045 אותנו / op MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12,670 ± 2,582 us / op

כמו שאנו יכולים לראות, EJML ו סוּסוֹן מבצעים ממש טוב עם כחמישית מיקרו-שנייה לכל פעולה, איפה ND4j הוא פחות ביצועי עם קצת יותר מעשר מיקרו-שניות לכל פעולה. בספריות האחרות יש הופעות שביניהן.

כמו כן, ראוי לציין שכאשר מגדילים את מספר חזרות החימום מ -5 ל -10, הביצועים הולכים וגדלים לכל הספריות.

4.2. מטריצות גדולות

עכשיו, מה קורה אם ניקח מטריצות גדולות יותר, כמו 3000 × 3000? כדי לבדוק מה קורה, בואו ניצור תחילה מחלקת מדינה אחרת המספקת מטריצות שנוצרו באותו גודל:

@State (Scope.Benchmark) מחלקה ציבורית BigMatrixProvider {כפול פרטי [] [] firstMatrix; כפול פרטי [] [] secondMatrix; BigMatrixProvider ציבורי () {} הגדרת חלל ציבורי @Setup (פרמטרים של BenchmarkParams) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } כפול פרטי [] [] createMatrix () {אקראי אקראי = אקראי חדש (); כפול [] [] תוצאה = כפול חדש [3000] [3000]; עבור (int שורה = 0; שורה <result.length; שורה ++) {עבור (int col = 0; col <תוצאה [שורה] .length; col ++) {תוצאה [שורה] [col] = random.nextDouble (); }} להחזיר תוצאה; }}

כפי שאנו רואים ניצור 3000 × 3000 מערכים כפולים דו מימדיים מלאים במספרים ממשיים אקראיים.

בואו ניצור כעת את כיתת המידוד:

class class BigMatrixMultiplicationBenchmarking {public static void main (String [] args) throw Exception {Map parameters = parseParameters (args); ChainedOptionsBuilder builder = OptionsBuilder new () .include (BigMatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (10) .measurementIterations (10). TimeUnit (TimeUnit.SECONDS); רץ חדש (builder.build ()). run (); } @Benchmark public Object homemadeMatrixMultiplication (BigMatrixProvider matrixProvider) {return HomemadeMatrix .multiplyMatrices (matrixProvider.getFirstMatrix (), matrixProvider.getSecondMatrix ()); } @ Benchmark public Object ejmlMatrixMultiplication (BigMatrixProvider matrixProvider) {SimpleMatrix firstMatrix = SimpleMatrix new (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = SimpleMatrix חדש (matrixProvider.getSecondMatrix ()); להחזיר firstMatrix.mult (secondMatrix); } @Benchmark אובייקט ציבורי apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = new Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = Array2DRowRealMatrix חדש (matrixProvider.getSecondMatrix ()); חזור firstMatrix.multiply (secondMatrix); } @Benchmark אובייקט ציבורי la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = new Basic2DMatrix (matrixProvider.getFirstMatrix ()); מטריקס secondMatrix = חדש Basic2DMatrix (matrixProvider.getSecondMatrix ()); להחזיר firstMatrix.multiply (secondMatrix); } @Benchmark אובייקט ציבורי nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); להחזיר firstMatrix.mmul (secondMatrix); } @Benchmark אובייקט ציבורי coltMatrixMultiplication (BigMatrixProvider matrixProvider) {DoubleFactory2D doubleFactory2D = DoubleFactory2D.dense; DoubleMatrix2D firstMatrix = doubleFactory2D.make (matrixProvider.getFirstMatrix ()); DoubleMatrix2D secondMatrix = doubleFactory2D.make (matrixProvider.getSecondMatrix ()); אלגברה אלגברה = אלגברה חדשה (); להחזיר אלגברה.mult (firstMatrix, secondMatrix); }}

כשאנחנו מריצים את המבחן הזה, אנו מקבלים תוצאות אחרות לגמרי:

בנצ'מרק מצב CNT שגיאה ציון יחידות 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

כפי שאנו רואים, היישומים הביתיים וספריית אפאצ'י גרועים כעת מבעבר, ולוקח כמעט 10 דקות לבצע את הכפל של שתי המטריצות.

קולט לוקח קצת יותר משלוש דקות, וזה יותר טוב אבל עדיין ארוך מאוד. EJML ו- LA4J מתפקדים די טוב מכיוון שהם פועלים כמעט 30 שניות. אבל זה ND4J שזוכה בביצוע הייחוס הזה תוך פחות משנייה על גבי backend של המעבד.

4.3. אָנָלִיזָה

זה מראה לנו שתוצאות המבחן באמת תלויות במאפייני המטריצות ולכן זה מסובך להצביע על זוכה יחיד.

5. מסקנה

במאמר זה למדנו כיצד להכפיל מטריצות בג'אווה, בעצמנו או באמצעות ספריות חיצוניות. לאחר שבדקנו את כל הפתרונות, עשינו אמת מידה של כולם וראינו שלמעט ND4J, כולם ביצעו די טוב על מטריצות קטנות. מצד שני, על מטריצות גדולות יותר, ND4J לוקח את ההובלה.

כרגיל, ניתן למצוא את הקוד המלא עבור מאמר זה ב- GitHub.