Структури на данни и алгоритми в Java, Част 3: Многомерни масиви

Структури на данни и алгоритми в Java, част 2 въведе разнообразни техники за търсене и сортиране на едномерни масиви, които са най-простите масиви. В този урок ще изследвате многомерни масиви. Ще ви покажа трите начина за създаване на многомерни масиви, след което ще научите как да използвате алгоритъма за умножение на матрица за умножаване на елементи в двуизмерен масив. Ще въведа и парцаливи масиви и ще научите защо са популярни за приложенията за големи данни. Накрая ще разгледаме въпроса дали даден масив е или не Java обект. 

Тази статия ви настройва за част 4, която въвежда търсене и сортиране с еднократно свързани списъци.

Многомерни масиви

А многомерен масив свързва всеки елемент в масива с множество индекси. Най-често използваният многомерен масив е двумерният масив , известен също като таблица или матрица . Двуизмерен масив свързва всеки от елементите му с два индекса.

Можем да концептуализираме двуизмерен масив като правоъгълна мрежа от елементи, разделени на редове и колони. Използваме (row, column)нотацията, за да идентифицираме елемент, както е показано на фигура 1.

Тъй като двуизмерните масиви са толкова често използвани, ще се спра на тях. Това, което научавате за двумерните масиви, може да бъде обобщено за по-високоизмерни.

Създаване на двумерни масиви

Има три техники за създаване на двумерен масив в Java:

  • Използване на инициализатор
  • Използване на ключовата дума new
  • Използване на ключовата дума newс инициализатор

Използване на инициализатор за създаване на двуизмерен масив

Подходът само за инициализация за създаване на двумерен масив има следния синтаксис:

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

rowInitializer има следния синтаксис:

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

Този синтаксис гласи, че двумерният масив е незадължителен, разделен със запетая списък с инициализатори на редове, които се появяват между отворени и затворени скоби. Освен това, всеки инициализатор на редове е незадължителен, разделен със запетая списък с изрази, появяващи се между отворени и затворени скоби. Подобно на едномерните масиви, всички изрази трябва да се оценяват на съвместими типове.

Ето пример за двумерен масив:

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

Този пример създава таблица с два реда и три колони. Фигура 2 представя концептуален изглед на тази таблица, заедно с изглед на паметта, който показва как Java излага тази (и всяка) таблица в паметта.

Фигура 2 разкрива, че Java представлява двумерен масив като едномерен редовен масив, чиито елементи се отнасят към едномерни масиви на колони. Индексът на реда идентифицира масива на колоната; индексът на колоната идентифицира елемента от данни.

Ключова дума само ново създаване

Ключовата дума newразпределя памет за двуизмерен масив и връща неговата препратка. Този подход има следния синтаксис:

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

Този синтаксис гласи, че двуизмерен масив е област от (положителни) 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)*] '}'

Този синтаксис съчетава предишните два примера. Тъй като броят на елементите може да бъде определен от разделени със запетая списъци с изрази, не предоставяте int_exprмежду двете двойки квадратни скоби. Ето пример:

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

Двумерни масиви и променливи на масива

Само по себе си новосъздаденият двумерен масив е безполезен. Препратката му трябва да бъде присвоена на променлива от масив от съвместим тип, директно или чрез извикване на метод. Следните синтаксиси показват как бихте декларирали тази променлива:

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

Всеки синтаксис декларира променлива на масив, която съхранява препратка към двуизмерен масив. За предпочитане е квадратните скоби да се поставят след 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 } };

Подобно на едномерните променливи на масива, двумерната променлива на масива е свързана със .lengthсвойство, което връща дължината на масива от редове. Например temperatures1.lengthвръща 2. Всеки елемент на ред също е променлива на масив със .lengthсвойство, което връща броя на колоните за масива от колони, присвоени на елемента на реда. Например temperatures1[0].lengthвръща 3.

Като се има предвид променлива на масив, можете да получите достъп до всеки елемент в двуизмерен масив, като посочите израз, който се съгласува със следния синтаксис:

array_var '[' row_index ']' '[' col_index ']'

И двата индекса са положителни ints, които варират от 0 до един по-малко от стойността, върната от съответните .lengthсвойства. Помислете за следващите два примера:

double temp = temperatures1[0][1]; // Get value. temperatures1[0][1] = 75.0; // Set value.

Първият пример връща стойността във втората колона на първия ред ( 30.6). Вторият пример заменя тази стойност с 75.0.

Ако посочите отрицателен индекс или индекс, който е по-голям или равен на стойността, върната от .lengthсвойството на променливата на масива , Java създава и хвърля ArrayIndexOutOfBoundsExceptionобект.

Умножаване на двумерни масиви

Умножаването на една матрица с друга матрица е често срещана операция в области, вариращи от компютърна графика, икономика и транспортна индустрия. Разработчиците обикновено използват алгоритъма за умножение на матрица за тази операция.

Как работи умножението на матрицата? Нека A представлява матрица с m редове и p колони. По същия начин нека B представлява матрица с p редове и n колони. Умножете A по B, за да се получи матрица C, с m редове и n колони. Всеки cij запис в C се получава чрез умножаване на всички записи в i-тия ред на A по съответните записи в j-тата колона на B , след което се добавят резултатите. Фигура 3 илюстрира тези операции.

Колоните от лявата матрица трябва да са равни на редовете от дясната матрица

Умножението на матрицата изисква броят на колоните (p) в лявата матрица (A) да е равен на броя редове (p) в дясната матрица (B). В противен случай този алгоритъм няма да работи.

Следващият псевдокод изразява умножение на матрица в контекст на таблица 2-на-2-колона и 2-ред-на-1 колона. (Спомнете си, че въведох псевдокод в част 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

Поради трите FORцикъла Matrix Multiplication има времева сложност , която се произнася "Big Oh of n cubed". Matrix Multiplication предлага кубична производителност, която става скъпа във времето, когато се умножават големи матрици. Той предлага пространствена сложност на , която се произнася "Big Oh of n * m ", за съхраняване на допълнителна матрица от n редове по m колони. Това става за квадратни матрици.O(n3)O(nm)O(n2)

Създадох MatMultприложение на Java, което ви позволява да експериментирате с Matrix Multiplication. Листинг 1 представя изходния код на това приложение.

Листинг 1. Java приложение за експериментиране с умножение на матрица (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декларира двойка матрици и изхвърля техните стойности към стандартния изход. След това умножава двете матрици и извежда матрицата на резултатите към стандартния изход.

Съставете списък 1, както следва:

javac MatMult.java

Стартирайте полученото приложение, както следва:

java MatMult

Трябва да наблюдавате следния изход:

10 30 20 40 5 7 260 380

Пример за умножение на матрица

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

Полученият двуизмерен масив е известен като окъсан масив . Ето втори пример: