Javaのデータ構造とアルゴリズム、パート3:多次元配列

Javaのデータ構造とアルゴリズム、パート2では、最も単純な配列である1次元配列を検索およびソートするためのさまざまな手法を紹介しました。このチュートリアルでは、多次元配列について説明します。多次元配列を作成する3つの方法を紹介し、次に行列乗算アルゴリズムを使用して2次元配列の要素を乗算する方法を学習します。また、不規則な配列を紹介し、ビッグデータアプリケーションで人気がある理由を学びます。最後に、配列Javaオブジェクトであるかどうかの問題について検討します。 

この記事では、単一リンクリストを使用した検索と並べ替えを紹介するパート4の準備をします。

多次元配列

多次元アレイは、複数のインデックスを持つ配列内の各要素を関連付けます。最も一般的に使用される多次元配列は、テーブルまたは行列とも呼ばれる2次元配列です。2次元配列は、その各要素を2つのインデックスに関連付けます。

2次元配列は、行と列に分割された要素の長方形グリッドとして概念化できます。(row, column)図1に示すように、この表記を使用して要素を識別します。

2次元配列は非常に一般的に使用されているため、ここではそれらに焦点を当てます。2次元配列について学んだことは、より高次元の配列に一般化することができます。

2次元配列の作成

Javaで2次元配列を作成するには、次の3つの手法があります。

  • 初期化子の使用
  • キーワードを使用する new
  • newイニシャライザでキーワードを使用する

初期化子を使用して2次元配列を作成する

2次元配列を作成するための初期化子のみのアプローチには、次の構文があります。

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

rowInitializer 構文は次のとおりです。

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

この構文は、2次元配列が、中括弧で囲まれた文字と中括弧で囲まれた文字の間に表示される行初期化子のオプションのコンマ区切りリストであることを示しています。さらに、各行初期化子は、中括弧で囲まれた文字と中括弧で囲まれた文字の間に表示される式のオプションのコンマ区切りリストです。1次元配列と同様に、すべての式は互換性のある型に評価される必要があります。

2次元配列の例を次に示します。

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

この例では、2行3列のテーブルを作成します。図2は、このテーブルの概念図と、Javaがこの(およびすべての)テーブルをメモリ内にレイアウトする方法を示すメモリビューを示しています。

図2は、Javaが2次元配列を1次元の行配列として表し、その要素が1次元の列配列を参照していることを示しています。行インデックスは列配列を識別します。列インデックスはデータ項目を識別します。

キーワード新規のみ作成

キーワードnewは、2次元配列にメモリを割り当て、その参照を返します。このアプローチの構文は次のとおりです。

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

この構文は、2次元配列が、すべて同じを共有する(正の)int_expr1行要素と(正の)int_expr2列要素の領域であることを示していますtype。さらに、すべての要素がゼロになります。次に例を示します。

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

キーワードの新規作成と初期化子の作成

new初期化アプローチのキーワードの構文は次のとおりです。

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

ここでrowInitializer、構文は次のとおりです。

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

この構文は、前の2つの例をブレンドしています。要素の数は、コンマで区切られた式のリストから決定できるため、int_expr角かっこのペアの間に指定することはできません。次に例を示します。

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

2次元配列と配列変数

それ自体では、新しく作成された2次元配列は役に立ちません。その参照は、直接またはメソッド呼び出しを介して、互換性のあるタイプの配列変数に割り当てる必要があります。次の構文は、この変数を宣言する方法を示しています。

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

各構文は、2次元配列への参照を格納する配列変数を宣言します。の後に角かっこを配置することをお勧めしtypeます。次の例を検討してください。

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

1次元配列変数と同様に、2次元配列変数は.lengthプロパティに関連付けられ、行配列の長さを返します。たとえば、temperatures1.length2を返します。各行要素は、.lengthプロパティを持つ配列変数でもあり、行要素に割り当てられた列配列の列数を返します。たとえば、temperatures1[0].length3を返します。

配列変数を指定すると、次の構文に一致する式を指定することにより、2次元配列内の任意の要素にアクセスできます。

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.

temperature2の行配列を作成した後、その要素に新しい列配列への参照を入力する必要があります。次の例は、最初の行に3列、2番目の行に2列を割り当てることを示しています。

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

結果の2次元配列は、不規則配列と呼ばれます。2番目の例を次に示します。