Struktur data dan algoritma di Java, Bahagian 3: Susunan multidimensi

Struktur data dan algoritma di Java, Bahagian 2 memperkenalkan berbagai teknik untuk mencari dan menyusun susunan satu dimensi, yang merupakan susunan paling mudah. Dalam tutorial ini, anda akan meneroka tatasusunan pelbagai dimensi. Saya akan menunjukkan kepada anda tiga cara untuk membuat tatasusunan multidimensi, maka anda akan belajar bagaimana menggunakan algoritma Pendaraban Matriks untuk memperbanyak unsur dalam susunan dua dimensi. Saya juga akan memperkenalkan tatasusunan ragged dan anda akan mengetahui mengapa ia popular untuk aplikasi data besar. Akhirnya, kita akan mempertimbangkan persoalan sama ada array adalah atau tidak objek Java. 

Artikel ini menyediakan anda untuk Bahagian 4, yang memperkenalkan mencari dan menyusun dengan senarai yang dipautkan secara tunggal.

Susunan pelbagai dimensi

A pelbagai multidimensi mengaitkan setiap elemen dalam array dengan pelbagai indeks. Susunan multidimensi yang paling biasa digunakan ialah susunan dua dimensi , juga dikenali sebagai jadual atau matriks . Susunan dua dimensi mengaitkan setiap elemennya dengan dua indeks.

Kita dapat mengkonseptualisasikan susunan dua dimensi sebagai grid elemen segi empat tepat yang dibahagikan kepada baris dan lajur. Kami menggunakan (row, column)notasi untuk mengenali elemen, seperti yang ditunjukkan pada Gambar 1.

Kerana tatasusunan dua dimensi sangat biasa digunakan, saya akan memfokuskannya. Apa yang anda pelajari mengenai susunan dua dimensi dapat digeneralisasikan kepada susunan dimensi yang lebih tinggi.

Membuat susunan dua dimensi

Terdapat tiga teknik untuk membuat susunan dua dimensi di Java:

• Menggunakan pemula
• Menggunakan kata kunci new
• Menggunakan kata kunci newdengan pemula

Menggunakan inisialisasi untuk membuat susunan dua dimensi

Pendekatan inisialisasi sahaja untuk membuat susunan dua dimensi mempunyai sintaks berikut:

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

rowInitializer mempunyai sintaks berikut:

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

Sintaks ini menyatakan bahawa susunan dua dimensi adalah pilihan, pemula baris yang dipisahkan dengan koma yang muncul antara watak terbuka dan pendakap dekat. Selanjutnya, setiap penginisialisasi baris adalah pilihan ungkapan yang dipisahkan dengan koma yang muncul antara watak terbuka dan pendakap dekat. Seperti tatasusunan satu dimensi, semua ungkapan mesti dinilai mengikut jenis yang serasi.

Berikut adalah contoh tatasusunan dua dimensi:

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

Contoh ini membuat jadual dengan dua baris dan tiga lajur. Gambar 2 menunjukkan pandangan konseptual jadual ini bersama dengan pandangan memori yang menunjukkan bagaimana Java meletakkan jadual ini (dan setiap) dalam memori.

Gambar 2 menunjukkan bahawa Java mewakili tatasusunan dua dimensi sebagai tatasusunan satu dimensi yang unsurnya merujuk susunan lajur satu dimensi. Indeks baris mengenal pasti susunan lajur; indeks lajur mengenal pasti item data.

Kata kunci penciptaan baru sahaja

Kata kunci newmemperuntukkan memori untuk susunan dua dimensi dan mengembalikan rujukannya. Pendekatan ini mempunyai sintaks berikut:

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

Sintaks ini menyatakan bahawa susunan dua dimensi adalah kawasan int_expr1elemen baris (positif) dan elemen positif (positif) int_expr2yang semuanya sama type. Selanjutnya, semua elemen sifar. Inilah contohnya:

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

Kata kunci baru dan penciptaan pemula

Kata kunci newdengan pendekatan inisialisasi mempunyai sintaks berikut:

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

di mana rowInitializermempunyai sintaks berikut:

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

Sintaks ini menggabungkan dua contoh sebelumnya. Oleh kerana bilangan elemen dapat ditentukan dari senarai ungkapan yang dipisahkan koma, anda tidak memberikan int_exprantara kedua-dua pasangan tanda kurung. Berikut adalah contoh:

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

Susunan dua dimensi dan pemboleh ubah larik

Dengan sendirinya, susunan dua dimensi yang baru dibuat tidak berguna. Rujukannya mesti diberikan kepada pemboleh ubah array dari jenis yang serasi, sama ada secara langsung atau melalui panggilan kaedah. Sintaks berikut menunjukkan bagaimana anda akan menyatakan pemboleh ubah ini:

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

Each syntax declares an array variable that stores a reference to a two-dimensional array. It's preferred to place the square brackets after type. Consider the following examples:

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

Like one-dimensional array variables, a two-dimensional array variable is associated with a .length property, which returns the length of the row array. For example, temperatures1.length returns 2. Each row element is also an array variable with a .length property, which returns the number of columns for the column array assigned to the row element. For example, temperatures1[0].length returns 3.

Given an array variable, you can access any element in a two-dimensional array by specifying an expression that agrees with the following syntax:

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.

Setelah membuat temperature2susunan baris, elemennya mesti diisi dengan rujukan kepada susunan lajur baru. Contoh berikut menunjukkan, menetapkan 3 lajur ke baris pertama dan 2 lajur ke baris kedua:

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

Susunan dua dimensi yang dihasilkan dikenali sebagai tatasusunan ragged . Berikut adalah contoh kedua: