Java의 데이터 구조 및 알고리즘, Part 3 : 다차원 배열

Java의 데이터 구조 및 알고리즘, Part 2에서는 가장 단순한 배열 인 1 차원 배열을 검색하고 정렬하는 다양한 기술을 소개했습니다. 이 자습서에서는 다차원 배열을 살펴 봅니다. 다차원 배열을 만드는 세 가지 방법을 보여주고 행렬 곱셈 알고리즘을 사용하여 2 차원 배열의 요소를 곱하는 방법을 배웁니다. 또한 비정형 어레이를 소개하고 빅 데이터 애플리케이션에 인기있는 이유를 배우게 될 것입니다. 마지막으로 배열 Java 객체 인지 아닌지에 대한 질문을 고려할 것 입니다. 

이 기사에서는 단일 링크 목록을 사용한 검색 및 정렬을 소개하는 Part 4에 대해 설명합니다.

다차원 배열

다차원 어레이는 여러 인덱스 어레이의 각각의 요소를 연관시킨다. 가장 일반적으로 사용되는 다차원 배열은 테이블 또는 행렬 이라고도 하는 2 차원 배열 입니다. 2 차원 배열은 각 요소를 두 개의 인덱스와 연결합니다.

2 차원 배열을 행과 열로 나누어 진 요소의 직사각형 격자로 개념화 할 수 있습니다. 우리는 사용 (row, column)그림 1과 같이 요소를 식별 표기를.

2 차원 배열이 매우 일반적으로 사용되기 때문에 이에 초점을 맞출 것입니다. 2 차원 배열에 대해 배운 내용은 고차원 배열로 일반화 할 수 있습니다.

2 차원 배열 만들기

Java에서 2 차원 배열을 만드는 세 가지 기술이 있습니다.

  • 이니셜 라이저 사용
  • 키워드 사용 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가 요소가 1 차원 열 배열을 참조하는 1 차원 행 배열로 2 차원 배열을 나타냄을 보여줍니다. 행 인덱스는 열 배열을 식별합니다. 열 인덱스는 데이터 항목을 식별합니다.

키워드 신규 전용 생성

키워드 new는 2 차원 배열에 메모리를 할당하고 참조를 반환합니다. 이 접근 방식에는 다음과 같은 구문이 있습니다.

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

이 구문은 2 차원 배열이 (양수) int_expr1행 요소와 int_expr2모두 동일한 type. 또한 모든 요소가 0이됩니다. 예를 들면 다음과 같습니다.

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

키워드 신규 및 이니셜 라이저 생성

new이니셜 라이저 접근 방식을 사용하는 키워드의 구문은 다음과 같습니다.

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

어디 rowInitializer구문은 다음과 같습니다

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

이 구문은 앞의 두 예를 혼합합니다. 요소 수는 쉼표로 구분 된 표현식 목록에서 확인할 수 있으므로 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행 배열의 길이를 반환 하는 속성 과 연결 됩니다. 예를 들어 2를 temperatures1.length반환합니다. 각 행 요소는 행 요소에 .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 개의 열을 지정하는 방법을 보여줍니다.

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

결과 2 차원 배열을 비정형 배열이라고 합니다. 다음은 두 번째 예입니다.