Datenstrukturen und Algorithmen in Java, Teil 3: Mehrdimensionale Arrays

Datenstrukturen und Algorithmen in Java, Teil 2, führten eine Vielzahl von Techniken zum Suchen und Sortieren eindimensionaler Arrays ein, die die einfachsten Arrays sind. In diesem Tutorial werden Sie mehrdimensionale Arrays untersuchen. Ich zeige Ihnen die drei Möglichkeiten zum Erstellen mehrdimensionaler Arrays. Anschließend lernen Sie, wie Sie mit dem Matrix-Multiplikationsalgorithmus Elemente in einem zweidimensionalen Array multiplizieren. Ich werde auch zerlumpte Arrays vorstellen und erfahren, warum sie für Big-Data-Anwendungen beliebt sind. Abschließend betrachten wir die Frage, ob ein Array ein Java-Objekt ist oder nicht

Dieser Artikel bereitet Sie auf Teil 4 vor, in dem das Suchen und Sortieren mit einfach verknüpften Listen vorgestellt wird.

Mehrdimensionale Arrays

Ein mehrdimensionales Array ordnet jedes Element im Array mehreren Indizes zu. Das am häufigsten verwendete mehrdimensionale Array ist das zweidimensionale Array , das auch als Tabelle oder Matrix bezeichnet wird . Ein zweidimensionales Array ordnet jedes seiner Elemente zwei Indizes zu.

Wir können ein zweidimensionales Array als rechteckiges Gitter von Elementen konzipieren, die in Zeilen und Spalten unterteilt sind. Wir verwenden die (row, column)Notation, um ein Element zu identifizieren, wie in Abbildung 1 gezeigt.

Da zweidimensionale Arrays so häufig verwendet werden, werde ich mich auf sie konzentrieren. Was Sie über zweidimensionale Arrays lernen, kann auf höherdimensionale Arrays verallgemeinert werden.

Erstellen zweidimensionaler Arrays

Es gibt drei Techniken zum Erstellen eines zweidimensionalen Arrays in Java:

  • Verwenden eines Initialisierers
  • Verwenden Sie das Schlüsselwort new
  • Verwenden des Schlüsselworts newmit einem Initialisierer

Verwenden eines Initialisierers zum Erstellen eines zweidimensionalen Arrays

Der Nur-Initialisierer-Ansatz zum Erstellen eines zweidimensionalen Arrays hat die folgende Syntax:

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

rowInitializer hat die folgende Syntax:

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

Diese Syntax besagt, dass ein zweidimensionales Array eine optionale, durch Kommas getrennte Liste von Zeileninitialisierern ist, die zwischen Zeichen mit offener und geschlossener Klammer angezeigt werden. Darüber hinaus ist jeder Zeileninitialisierer eine optionale, durch Kommas getrennte Liste von Ausdrücken, die zwischen Zeichen mit offener und geschlossener Klammer angezeigt werden. Wie eindimensionale Arrays müssen alle Ausdrücke zu kompatiblen Typen ausgewertet werden.

Hier ist ein Beispiel für ein zweidimensionales Array:

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

In diesem Beispiel wird eine Tabelle mit zwei Zeilen und drei Spalten erstellt. Abbildung 2 zeigt eine konzeptionelle Ansicht dieser Tabelle sowie eine Speicheransicht, die zeigt, wie Java diese (und jede) Tabelle im Speicher anordnet.

Abbildung 2 zeigt, dass Java ein zweidimensionales Array als eindimensionales Zeilenarray darstellt, dessen Elemente auf eindimensionale Spaltenarrays verweisen. Der Zeilenindex identifiziert das Spaltenarray. Der Spaltenindex identifiziert das Datenelement.

Nur Schlüsselwort-Neuerstellung

Das Schlüsselwort newreserviert Speicher für ein zweidimensionales Array und gibt seine Referenz zurück. Dieser Ansatz hat die folgende Syntax:

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

Diese Syntax besagt, dass ein zweidimensionales Array ein Bereich von (positiven) int_expr1Zeilenelementen und (positiven) int_expr2Spaltenelementen ist, die alle dasselbe teilen type. Außerdem werden alle Elemente auf Null gesetzt. Hier ist ein Beispiel:

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

Schlüsselwort neu und Initialisierungserstellung

Das Schlüsselwort newmit einem Initialisierungsansatz hat die folgende Syntax:

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

Wo rowInitializerhat die folgende Syntax:

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

Diese Syntax kombiniert die beiden vorherigen Beispiele. Da die Anzahl der Elemente aus den durch Kommas getrennten Listen von Ausdrücken bestimmt werden kann, geben Sie kein int_exprPaar eckiger Klammern an. Hier ist ein Beispiel:

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

Zweidimensionale Arrays und Arrayvariablen

Ein neu erstelltes zweidimensionales Array ist an sich nutzlos. Die Referenz muss einer Array-Variablen eines kompatiblen Typs entweder direkt oder über einen Methodenaufruf zugewiesen werden . Die folgenden Syntaxen zeigen, wie Sie diese Variable deklarieren würden:

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

Jede Syntax deklariert eine Arrayvariable, die einen Verweis auf ein zweidimensionales Array speichert. Es wird bevorzugt, die eckigen Klammern danach zu platzieren type. Betrachten Sie die folgenden Beispiele:

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 } };

Wie eindimensionale Arrayvariablen ist eine zweidimensionale Arrayvariable einer .lengthEigenschaft zugeordnet, die die Länge des Zeilenarrays zurückgibt. Gibt beispielsweise temperatures1.length2 zurück. Jedes Zeilenelement ist auch eine Arrayvariable mit einer .lengthEigenschaft, die die Anzahl der Spalten für das dem Zeilenelement zugewiesene Spaltenarray zurückgibt. Gibt beispielsweise temperatures1[0].length3 zurück.

Bei einer gegebenen Array-Variablen können Sie auf jedes Element in einem zweidimensionalen Array zugreifen, indem Sie einen Ausdruck angeben, der mit der folgenden Syntax übereinstimmt:

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

Both indexes are positive ints that range from 0 to one less than the value returned from the respective .length properties. Consider the next two examples:

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

The first example returns the value in the second column of the first row (30.6). The second example replaces this value with 75.0.

If you specify a negative index or an index that is greater than or equal to the value returned by the array variable's .length property, Java creates and throws an ArrayIndexOutOfBoundsException object.

Multiplying two-dimensional arrays

Multiplying one matrix by another matrix is a common operation in fields ranging from computer graphics, to economics, to the transportation industry. Developers usually use the Matrix Multiplication algorithm for this operation.

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.

Nach dem Erstellen temperature2des Zeilenarrays müssen seine Elemente mit Verweisen auf neue Spaltenarrays gefüllt werden. Das folgende Beispiel zeigt, wie der ersten Zeile 3 Spalten und der zweiten Zeile 2 Spalten zugewiesen werden:

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

Das resultierende zweidimensionale Array ist als zerlumptes Array bekannt . Hier ist ein zweites Beispiel: