Structures de données et algorithmes en Java, Partie 3: Tableaux multidimensionnels

Structures de données et algorithmes en Java, la partie 2 a introduit une variété de techniques pour rechercher et trier les tableaux unidimensionnels, qui sont les tableaux les plus simples. Dans ce didacticiel, vous explorerez les tableaux multidimensionnels. Je vais vous montrer les trois façons de créer des tableaux multidimensionnels, puis vous apprendrez à utiliser l'algorithme de multiplication matricielle pour multiplier des éléments dans un tableau à deux dimensions. Je vais également présenter des tableaux déchiquetés et vous apprendrez pourquoi ils sont populaires pour les applications Big Data. Enfin, nous examinerons la question de savoir si un tableau est ou non un objet Java. 

Cet article vous prépare à la partie 4, qui présente la recherche et le tri avec des listes à lien unique.

Tableaux multidimensionnels

Un tableau multidimensionnel associe chaque élément du tableau à plusieurs index. Le tableau multidimensionnel le plus couramment utilisé est le tableau à deux dimensions , également appelé tableau ou matrice . Un tableau à deux dimensions associe chacun de ses éléments à deux index.

Nous pouvons conceptualiser un tableau à deux dimensions comme une grille rectangulaire d'éléments divisés en lignes et colonnes. Nous utilisons la (row, column)notation pour identifier un élément, comme le montre la figure 1.

Parce que les tableaux à deux dimensions sont si couramment utilisés, je vais me concentrer sur eux. Ce que vous apprenez sur les tableaux à deux dimensions peut être généralisé à ceux de dimension supérieure.

Création de tableaux à deux dimensions

Il existe trois techniques pour créer un tableau à deux dimensions en Java:

  • Utilisation d'un initialiseur
  • Utilisation du mot-clé new
  • Utilisation du mot-clé newavec un initialiseur

Utilisation d'un initialiseur pour créer un tableau à deux dimensions

L'approche de l'initialiseur uniquement pour créer un tableau à deux dimensions a la syntaxe suivante:

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

rowInitializer a la syntaxe suivante:

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

Cette syntaxe indique qu'un tableau à deux dimensions est une liste facultative, séparée par des virgules, d'initialiseurs de ligne apparaissant entre des accolades ouvertes et fermées. En outre, chaque initialiseur de ligne est une liste d'expressions facultative, séparées par des virgules, apparaissant entre des accolades ouvertes et fermées. Comme les tableaux unidimensionnels, toutes les expressions doivent s'évaluer en types compatibles.

Voici un exemple de tableau à deux dimensions:

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

Cet exemple crée une table avec deux lignes et trois colonnes. La figure 2 présente une vue conceptuelle de cette table avec une vue de la mémoire qui montre comment Java dispose cette (et toutes) table en mémoire.

La figure 2 révèle que Java représente un tableau à deux dimensions sous la forme d'un tableau de lignes à une dimension dont les éléments font référence à des tableaux de colonnes à une dimension. L'index de ligne identifie le tableau de colonnes; l'index de colonne identifie l'élément de données.

Création de mot-clé nouveau uniquement

Le mot-clé newalloue de la mémoire pour un tableau à deux dimensions et renvoie sa référence. Cette approche a la syntaxe suivante:

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

Cette syntaxe indique qu'un tableau à deux dimensions est une région d' int_expr1éléments de ligne (positifs) et d' int_expr2éléments de colonne (positifs) qui partagent tous la même chose type. De plus, tous les éléments sont remis à zéro. Voici un exemple:

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

Création d'un nouveau mot-clé et d'un initialiseur

Le mot-clé newavec une approche d'initialisation a la syntaxe suivante:

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

rowInitializera la syntaxe suivante:

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

Cette syntaxe mélange les deux exemples précédents. Comme le nombre d'éléments peut être déterminé à partir des listes d'expressions séparées par des virgules, vous ne fournissez int_expraucune paire de crochets. Voici un exemple:

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

Tableaux bidimensionnels et variables de tableau

En soi, un tableau bidimensionnel nouvellement créé est inutile. Sa référence doit être affectée à une variable tableau d'un type compatible, soit directement, soit via un appel de méthode. Les syntaxes suivantes montrent comment vous déclareriez cette variable:

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

Chaque syntaxe déclare une variable de tableau qui stocke une référence à un tableau à deux dimensions. Il est préférable de placer les crochets après type. Considérez les exemples suivants:

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

Comme les variables de tableau à une dimension, une variable de tableau à deux dimensions est associée à une .lengthpropriété qui renvoie la longueur du tableau de lignes. Par exemple, temperatures1.lengthrenvoie 2. Chaque élément de ligne est également une variable de tableau avec une .lengthpropriété, qui renvoie le nombre de colonnes pour le tableau de colonnes affecté à l'élément de ligne. Par exemple, temperatures1[0].lengthrenvoie 3.

Étant donné une variable de tableau, vous pouvez accéder à n'importe quel élément d'un tableau à deux dimensions en spécifiant une expression qui correspond à la syntaxe suivante:

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.

Une fois temperature2le tableau de lignes créé , ses éléments doivent être remplis avec des références aux nouveaux tableaux de colonnes. L'exemple suivant montre comment affecter 3 colonnes à la première ligne et 2 colonnes à la deuxième ligne:

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

Le tableau bidimensionnel résultant est connu sous le nom de tableau irrégulier . Voici un deuxième exemple: