מבני נתונים ואלגוריתמים בג'אווה, חלק 3: מערכים רב מימדיים

מבני נתונים ואלגוריתמים בג'אווה, חלק 2 הציג מגוון טכניקות לחיפוש ומיון מערכים חד-ממדיים, שהם המערכים הפשוטים ביותר. במדריך זה תוכלו לחקור מערכים רב מימדיים. אני אראה לך את שלוש הדרכים ליצור מערכים רב ממדיים, ואז תלמד כיצד להשתמש באלגוריתם הכפל של מטריצה ​​כדי להכפיל אלמנטים במערך דו מימדי. אני אציג גם מערכים מרופטים ותלמד מדוע הם פופולריים ליישומי Big Data. לבסוף, נבחן את השאלה האם מערך הוא אובייקט Java או לאו

מאמר זה מגדיר אותך לחלק 4, המציג חיפוש ומיון באמצעות רשימות המקושרות יחידה.

מערכים רב מימדיים

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

אנו יכולים להמחיש מערך דו-ממדי כגריד מלבני של אלמנטים המחולקים לשורות ועמודות. אנו משתמשים (row, column)בסימון כדי לזהות אלמנט, כפי שמוצג באיור 1.

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

יצירת מערכים דו מימדיים

ישנן שלוש טכניקות ליצירת מערך דו מימדי בג'אווה:

  • באמצעות אתחול
  • באמצעות מילת המפתח new
  • שימוש במילת המפתח newעם אתחול

שימוש באתחול ליצירת מערך דו מימדי

הגישה המתחילה בלבד ליצירת מערך דו-ממדי כוללת את התחביר הבא:

'{' [rowInitializer (',' rowInitializer)*] '}'

rowInitializer מכיל את התחביר הבא:

'{' [expr (',' expr)*] '}'

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

הנה דוגמה למערך דו מימדי:

{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }

דוגמה זו יוצרת טבלה עם שתי שורות ושלוש עמודות. איור 2 מציג מבט רעיוני של טבלה זו יחד עם תצוגת זיכרון המראה כיצד ג'אווה מציגה טבלה זו (וכל) בזיכרון.

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

יצירת מילת מפתח חדשה בלבד

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

'new' type '[' int_expr1 ']' '['int_expr2 ']'

תחביר זה קובע כי מערך דו מימדי הוא אזור של int_expr1רכיבי שורה (חיוביים) int_expr2ואלמנטים עמודה (חיוביים) שכולם חולקים אותו דבר type. יתר על כן, כל האלמנטים מאופסים. הנה דוגמה:

new double[2][3] // Create a two-row-by-three-column table.

מילת מפתח חדשה ויצירת אתחול

מילת המפתח newעם גישת אתחול כוללת את התחביר הבא:

'new' type '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'

איפה rowInitializerיש התחביר הבא:

'{' [expr (',' expr)*] '}'

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

new double [][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }

מערכים דו-ממדיים ומשתני מערך

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

typevar_name '[' ']' '[' ']' type '[' ']' '[' ']' var_name

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

double[][] temperatures1 = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }; double[][] temperatures2 = new double[2][3]; double[][] temperatures3 = new double[][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };

בדומה למשתני מערך חד-ממדיים, משתנה מערך דו-ממדי משויך .lengthלמאפיין המחזיר את אורך מערך השורות. לדוגמה, temperatures1.lengthמחזיר 2. כל אלמנט שורה הוא גם משתנה מערך עם .lengthמאפיין, שמחזיר את מספר העמודות עבור מערך העמודות שהוקצה לאלמנט השורה. לדוגמה, temperatures1[0].lengthמחזיר 3.

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

array_var '[' row_index ']' '[' col_index ']'

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

double temp = temperatures1[0][1]; // Get value. temperatures1[0][1] = 75.0; // Set value.

הדוגמה הראשונה מחזירה את הערך בעמודה השנייה בשורה הראשונה ( 30.6). הדוגמה השנייה מחליפה ערך זה ב- 75.0.

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

הכפלת מערכים דו מימדיים

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

How does matrix multiplication work? Let A represent a matrix with m rows and p columns. Similarly, let B represent a matrix with p rows and n columns. Multiply A by B to produce a matrix C, with m rows and n columns. Each cij entry in C is obtained by multiplying all entries in A's ith row by corresponding entries in B's jth column, then adding the results. Figure 3 illustrates these operations.

Left-matrix columns must equal right-matrix rows

Matrix multiplication requires that the number of columns (p) in the left matrix (A) equal the number of rows (p) in the right matrix (B). Otherwise, this algorithm won't work.

The following pseudocode expresses Matrix Multiplication in a 2-row-by-2-column and a 2-row-by-1-column table context. (Recall that I introduced pseudocode in Part 1.)

// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == DECLARE INTEGER a[][] = [ 10, 30 ] [ 20, 40 ] DECLARE INTEGER b[][] = [ 5, 7 ] DECLARE INTEGER m = 2 // Number of rows in left matrix (a) DECLARE INTEGER p = 2 // Number of columns in left matrix (a) // Number of rows in right matrix (b) DECLARE INTEGER n = 1 // Number of columns in right matrix (b) DECLARE INTEGER c[m][n] // c holds 2 rows by 1 columns // All elements initialize to 0 FOR i = 0 TO m - 1 FOR j = 0 TO n - 1 FOR k = 0 TO p - 1 c[i][j] = c[i][j] + a[i][k] * b[k][j] NEXT k NEXT j NEXT i END

Because of the three FOR loops, Matrix Multiplication has a time complexity of O(n3), which is pronounced "Big Oh of n cubed." Matrix Multiplication offers cubic performance, which gets expensive time-wise when large matrixes are multiplied. It offers a space complexity of O(nm), which is pronounced "Big Oh of n*m," for storing an additional matrix of n rows by m columns. This becomes O(n2) for square matrixes.

I've created a MatMult Java application that lets you experiment with Matrix Multiplication. Listing 1 presents this application's source code.

Listing 1. A Java application for experimenting with Matrix Multiplication (MatMult.java)

public final class MatMult { public static void main(String[] args) { int[][] a = {{ 10, 30 }, { 20, 40 }}; int[][] b = {{ 5 }, { 7 }}; dump(a); System.out.println(); dump(b); System.out.println(); int[][] c = multiply(a, b); dump(c); } private static void dump(int[][] x) { if (x == null) { System.err.println("array is null"); return; } // Dump the matrix's element values to the standard output in a tabular // order. for (int i = 0; i < x.length; i++) { for (int j = 0; j < x[0].length; j++) System.out.print(x[i][j] + " "); System.out.println(); } } private static int[][] multiply(int[][] a, int[][] b) { // ==================================================================== // 1. a.length contains a's row count // // 2. a[0].length (or any other a[x].length for a valid x) contains a's // column count // // 3. b.length contains b's row count // // 4. b[0].length (or any other b[x].length for a valid x) contains b's // column count // ==================================================================== // If a's column count != b's row count, bail out if (a[0].length != b.length) { System.err.println("a's column count != b's row count"); return null; } // Allocate result matrix with a size equal to a's row count times b's // column count int[][] result = new int[a.length][]; for (int i = 0; i < result.length; i++) result[i] = new int[b[0].length]; // Perform the multiplication and addition for (int i = 0; i < a.length; i++) for (int j = 0; j < b[0].length; j++) for (int k = 0; k < a[0].length; k++) // or k < b.length result[i][j] += a[i][k] * b[k][j]; // Return the result matrix return result; } }

MatMult declares a pair of matrixes and dumps their values to standard output. It then multiplies both matrixes and dumps the result matrix to standard output.

Compile Listing 1 as follows:

javac MatMult.java

Run the resulting application as follows:

java MatMult

You should observe the following output:

10 30 20 40 5 7 260 380

Example of matrix multiplication

Let's explore a problem that is best solved by matrix multiplication. In this scenario, a fruit grower in Florida loads a couple of semitrailers with 1,250 boxes of oranges, 400 boxes of peaches, and 250 boxes of grapefruit. Figure 4 shows a chart of the market price per box for each kind of fruit, in four different cities.

Our problem is to determine where the fruit should be shipped and sold for maximum gross income. To solve that problem, we first reconstruct the chart from Figure 4 as a four-row by three-column price matrix. From this, we can construct a three-row by one-column quantity matrix, which appears below:

== == | 1250 | | | | 400 | | | | 250 | == ==

With both matrixes on hand, we simply multiply the price matrix by the quantity matrix to produce a gross income matrix:

== == == == | 10.00 8.00 12.00 | == == | 18700.00 | New York | | | 1250 | | | | 11.00 8.50 11.55 | | | | 20037.50 | Los Angeles | | X | 400 | = | | | 8.75 6.90 10.00 | | | | 16197.50 | Miami | | | 250 | | | | 10.50 8.25 11.75 | == == | 19362.50 | Chicago == == == ==

Sending both semitrailers to Los Angeles will produce the highest gross income. But when distance and fuel costs are considered, perhaps New York is a better bet for yielding the highest income.

Ragged arrays

Having learned about two-dimensional arrays, you might now wonder whether it's possible to assign one-dimensional column arrays with different lengths to elements of a row array. The answer is yes. Consider these examples:

double[][] temperatures1 = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3 } }; double[][] temperatures2 = new double[2][]; double[][] temperatures3 = new double[][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3 } };

The first and third examples create a two-dimensional array where the first row contains three columns and the second row contains two columns. The second example creates an array with two rows and an unspecified number of columns.

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

temperatures2[0] = new double[3]; temperatures2[1] = new double[2];

המערך הדו-ממדי שנוצר מכונה מערך מרופט . הנה דוגמה שנייה: