Estructuras de datos y algoritmos en Java, Parte 3: Matrices multidimensionales

Estructuras de datos y algoritmos en Java, Parte 2 introdujo una variedad de técnicas para buscar y clasificar arreglos unidimensionales, que son los arreglos más simples. En este tutorial, explorará matrices multidimensionales. Le mostraré las tres formas de crear matrices multidimensionales, luego aprenderá a usar el algoritmo de multiplicación de matrices para multiplicar elementos en una matriz bidimensional. También presentaré arreglos irregulares y aprenderá por qué son populares para aplicaciones de big data. Finalmente, consideraremos la cuestión de si una matriz es o no un objeto Java. 

Este artículo lo prepara para la Parte 4, que presenta la búsqueda y clasificación con listas de enlaces individuales.

Matrices multidimensionales

Una matriz multidimensional asocia cada elemento de la matriz con varios índices. La matriz multidimensional más utilizada es la matriz bidimensional , también conocida como tabla o matriz . Una matriz bidimensional asocia cada uno de sus elementos con dos índices.

Podemos conceptualizar una matriz bidimensional como una cuadrícula rectangular de elementos divididos en filas y columnas. Usamos la (row, column)notación para identificar un elemento, como se muestra en la Figura 1.

Debido a que las matrices bidimensionales se usan con tanta frecuencia, me centraré en ellas. Lo que aprenda sobre matrices bidimensionales puede generalizarse a matrices de dimensiones superiores.

Crear matrices bidimensionales

Hay tres técnicas para crear una matriz bidimensional en Java:

  • Usando un inicializador
  • Usando la palabra clave new
  • Usando la palabra clave newcon un inicializador

Usando un inicializador para crear una matriz bidimensional

El enfoque de solo inicializador para crear una matriz bidimensional tiene la siguiente sintaxis:

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

rowInitializer tiene la siguiente sintaxis:

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

Esta sintaxis establece que una matriz bidimensional es una lista opcional, separada por comas, de inicializadores de fila que aparecen entre los caracteres de llaves abiertas y cerradas. Además, cada inicializador de fila es una lista opcional, separada por comas, de expresiones que aparecen entre caracteres de llaves abiertas y cerradas. Al igual que las matrices unidimensionales, todas las expresiones deben evaluarse a tipos compatibles.

Aquí hay un ejemplo de una matriz bidimensional:

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

Este ejemplo crea una tabla con dos filas y tres columnas. La Figura 2 presenta una vista conceptual de esta tabla junto con una vista de memoria que muestra cómo Java presenta esta (y todas) tablas en la memoria.

La Figura 2 revela que Java representa una matriz bidimensional como una matriz de filas unidimensional cuyos elementos hacen referencia a matrices de columnas unidimensionales. El índice de fila identifica la matriz de columnas; el índice de la columna identifica el elemento de datos.

Creación de palabra clave solo nueva

La palabra clave newasigna memoria para una matriz bidimensional y devuelve su referencia. Este enfoque tiene la siguiente sintaxis:

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

Esta sintaxis establece que una matriz bidimensional es una región de int_expr1elementos de fila (positivos) y int_expr2elementos de columna (positivos) que comparten lo mismo type. Además, todos los elementos se ponen a cero. He aquí un ejemplo:

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

Creación de inicializador y nueva palabra clave

La palabra clave newcon un enfoque de inicializador tiene la siguiente sintaxis:

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

donde rowInitializertiene la siguiente sintaxis:

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

Esta sintaxis combina los dos ejemplos anteriores. Debido a que la cantidad de elementos se puede determinar a partir de las listas de expresiones separadas por comas, no proporciona un int_exprpar de corchetes entre ambos. Aquí hay un ejemplo:

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

Matrices bidimensionales y variables de matriz

Por sí mismo, una matriz bidimensional recién creada es inútil. Su referencia debe asignarse a una variable de matriz de un tipo compatible, ya sea directamente o mediante una llamada a un método. Las siguientes sintaxis muestran cómo declararía esta variable:

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

Cada sintaxis declara una variable de matriz que almacena una referencia a una matriz bidimensional. Se prefiere colocar los corchetes después type. Considere los siguientes ejemplos:

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

Como las variables de matriz unidimensionales, una variable de matriz bidimensional se asocia con una .lengthpropiedad, que devuelve la longitud de la matriz de fila. Por ejemplo, temperatures1.lengthdevuelve 2. Cada elemento de fila es también una variable de matriz con una .lengthpropiedad, que devuelve el número de columnas para la matriz de columna asignada al elemento de fila. Por ejemplo, temperatures1[0].lengthdevuelve 3.

Dada una variable de matriz, puede acceder a cualquier elemento de una matriz bidimensional especificando una expresión que esté de acuerdo con la siguiente sintaxis:

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.

Después de crear temperature2la matriz de filas, sus elementos deben rellenarse con referencias a nuevas matrices de columnas. El siguiente ejemplo demuestra la asignación de 3 columnas a la primera fila y 2 columnas a la segunda fila:

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

La matriz bidimensional resultante se conoce como matriz irregular . Aquí hay un segundo ejemplo: