Algoritma dan struktur data di Java, Bagian 3: Array multidimensi

Algoritma dan struktur data di Java, Bagian 2 memperkenalkan berbagai teknik untuk mencari dan menyortir array satu dimensi, yang merupakan array paling sederhana. Dalam tutorial ini Anda akan menjelajahi array multidimensi. Saya akan menunjukkan tiga cara untuk membuat array multidimensi, lalu Anda akan belajar cara menggunakan algoritma Perkalian Matriks untuk mengalikan elemen dalam array dua dimensi. Saya juga akan memperkenalkan array compang-camping dan Anda akan belajar mengapa mereka populer untuk aplikasi data besar. Akhirnya, kita akan mempertimbangkan pertanyaan apakah sebuah array adalah objek Java atau bukan

Artikel ini menyiapkan Anda untuk Bagian 4, yang memperkenalkan pencarian dan pengurutan dengan daftar tertaut tunggal.

Array multidimensi

Sebuah array multidimensi rekan setiap elemen dalam array dengan beberapa indeks. Larik multidimensi yang paling umum digunakan adalah larik dua dimensi , juga dikenal sebagai tabel atau matriks . Array dua dimensi mengaitkan setiap elemennya dengan dua indeks.

Kita dapat mengkonseptualisasikan larik dua dimensi sebagai kisi persegi panjang elemen yang dibagi menjadi baris dan kolom. Kami menggunakan (row, column)notasi untuk mengidentifikasi elemen, seperti yang ditunjukkan pada Gambar 1.

Karena array dua dimensi sangat umum digunakan, saya akan fokus padanya. Apa yang Anda pelajari tentang larik dua dimensi dapat digeneralisasikan ke larik berdimensi lebih tinggi.

Membuat array dua dimensi

Ada tiga teknik untuk membuat larik dua dimensi di Java:

  • Menggunakan penginisialisasi
  • Menggunakan kata kunci new
  • Menggunakan kata kunci newdengan penginisialisasi

Menggunakan penginisialisasi untuk membuat larik dua dimensi

Pendekatan khusus penginisialisasi untuk membuat larik dua dimensi memiliki sintaks berikut:

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

rowInitializer memiliki sintaks berikut:

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

Sintaks ini menyatakan bahwa larik dua dimensi adalah daftar penginisialisasi baris opsional yang dipisahkan koma yang muncul di antara karakter kurung kurawal dan buka. Selain itu, setiap penginisialisasi baris adalah daftar opsional yang dipisahkan koma dari ekspresi yang muncul di antara karakter kurung kurawal dan buka. Seperti array satu dimensi, semua ekspresi harus dievaluasi ke tipe yang kompatibel.

Berikut contoh larik dua dimensi:

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

Contoh ini membuat tabel dengan dua baris dan tiga kolom. Gambar 2 menyajikan tampilan konseptual tabel ini bersama dengan tampilan memori yang menunjukkan bagaimana Java mengatur tabel ini (dan setiap) dalam memori.

Gambar 2 menunjukkan bahwa Java mewakili larik dua dimensi sebagai larik baris satu dimensi yang elemennya mereferensikan larik kolom satu dimensi. Indeks baris mengidentifikasi larik kolom; indeks kolom mengidentifikasi item data.

Kata kunci pembuatan hanya-baru

Kata kunci newmengalokasikan memori untuk array dua dimensi dan mengembalikan referensinya. Pendekatan ini memiliki sintaks berikut:

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

Sintaks ini menyatakan bahwa larik dua dimensi adalah kawasan int_expr1elemen baris (positif) dan int_expr2elemen kolom (positif) yang semuanya memiliki kesamaan type. Selanjutnya, semua elemen dikosongkan. Berikut contohnya:

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

Kata kunci baru dan pembuatan penginisialisasi

Kata kunci newdengan pendekatan penginisialisasi memiliki sintaks berikut:

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

di mana rowInitializermemiliki sintaks berikut:

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

Sintaks ini menggabungkan dua contoh sebelumnya. Karena jumlah elemen dapat ditentukan dari daftar ekspresi yang dipisahkan koma, Anda tidak boleh memberikan di int_exprantara kedua pasangan tanda kurung siku. Berikut ini contohnya:

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

Array dua dimensi dan variabel larik

Dengan sendirinya, array dua dimensi yang baru dibuat tidak berguna. Referensinya harus ditetapkan ke variabel array dari jenis yang kompatibel, baik secara langsung atau melalui panggilan metode. Sintaks berikut menunjukkan bagaimana Anda akan mendeklarasikan variabel ini:

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

Setiap sintaks mendeklarasikan variabel array yang menyimpan referensi ke array dua dimensi. Lebih disukai menempatkan tanda kurung siku setelah type. Perhatikan contoh berikut:

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

Seperti variabel larik satu dimensi, variabel larik dua dimensi dikaitkan dengan .lengthproperti, yang mengembalikan panjang larik baris. Misalnya, temperatures1.lengthmengembalikan 2. Setiap elemen baris juga merupakan variabel array dengan .lengthproperti, yang mengembalikan jumlah kolom untuk array kolom yang ditetapkan ke elemen baris. Misalnya, temperatures1[0].lengthmengembalikan 3.

Dengan adanya variabel array, Anda dapat mengakses elemen apa pun dalam array dua dimensi dengan menentukan ekspresi yang sesuai dengan sintaks berikut:

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 temperature2larik baris, elemennya harus diisi dengan referensi ke larik kolom baru. Contoh berikut menunjukkan, menetapkan 3 kolom ke baris pertama dan 2 kolom ke baris kedua:

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

Larik dua dimensi yang dihasilkan dikenal sebagai larik compang - camping . Inilah contoh kedua: