Strukture podataka i algoritmi u Javi, 3. dio: Multidimenzionalni nizovi

Strukture podataka i algoritmi u Javi, 2. dio uveli su razne tehnike pretraživanja i sortiranja jednodimenzionalnih nizova, koji su najjednostavniji nizovi. U ovom vodiču istražit ćete višedimenzionalne nizove. Pokazat ću vam tri načina za stvaranje višedimenzionalnih nizova, a zatim ćete naučiti kako koristiti algoritam umnožavanja matrice za množenje elemenata u dvodimenzionalnom nizu. Također ću predstaviti razbarušene nizove i naučit ćete zašto su popularni za aplikacije velikih podataka. Na kraju, razmotrit ćemo pitanje je li niz Java objekt ili nije

Ovaj vam članak postavlja dio 4, koji uvodi pretraživanje i sortiranje s pojedinačno povezanim popisima.

Višedimenzionalni nizovi

Višedimenzionalno polje povezuje svaki element u nizu s više indeksa. Najčešće korišteni višedimenzionalni niz je dvodimenzionalni niz , poznat i kao tablica ili matrica . Dvodimenzionalni niz svaki svoj element povezuje s dva indeksa.

Dvodimenzionalni niz možemo konceptualizirati kao pravokutnu mrežu elemenata podijeljenih u retke i stupce. Oznaku koristimo (row, column)za identifikaciju elementa, kao što je prikazano na slici 1.

Budući da se dvodimenzionalni nizovi toliko često koriste, usredotočit ću se na njih. Ono što naučite o dvodimenzionalnim nizovima može se generalizirati na višedimenzionalne.

Stvaranje dvodimenzionalnih nizova

Postoje tri tehnike za stvaranje dvodimenzionalnog niza u Javi:

  • Korištenje inicijalizatora
  • Korištenje ključne riječi new
  • Korištenje ključne riječi news inicijalizatorom

Korištenje inicijalizatora za stvaranje dvodimenzionalnog niza

Pristup izrade dvodimenzionalnog niza samo za inicijalizatore ima sljedeću sintaksu:

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

rowInitializer ima sljedeću sintaksu:

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

Ova sintaksa navodi da je dvodimenzionalni niz neobavezan popis inicijalizatora redaka odvojenih zarezima koji se pojavljuju između znakova otvorene i zagrade. Nadalje, svaki inicijalizator reda neobavezan je popis izraza odvojenih zarezima koji se pojavljuju između znakova otvorene i zagrade. Poput jednodimenzionalnih nizova, svi izrazi moraju se procijeniti na kompatibilne tipove.

Evo primjera dvodimenzionalnog niza:

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

Ovaj primjer stvara tablicu s dva retka i tri stupca. Slika 2 predstavlja konceptualni prikaz ove tablice zajedno s prikazom memorije koji pokazuje kako Java postavlja ovu (i svaku) tablicu u memoriju.

Slika 2 otkriva da Java predstavlja dvodimenzionalni niz kao jednodimenzionalni niz reda čiji se elementi odnose na jednodimenzionalne nizove stupaca. Indeks reda identificira niz stupaca; indeks stupca identificira stavku podataka.

Ključna riječ stvaranje samo novo

Ključna riječ newdodjeljuje memoriju za dvodimenzionalni niz i vraća njegovu referencu. Ovaj pristup ima sljedeću sintaksu:

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

Ova sintaksa navodi da je dvodimenzionalni niz područje (pozitivnih) int_expr1elemenata retka i (pozitivnih) int_expr2elemenata stupaca koji imaju isto type. Nadalje, svi elementi su nulirani. Evo primjera:

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

Nova ključna riječ i stvaranje inicijalizatora

Ključna riječ news pristupom inicijalizatora ima sljedeću sintaksu:

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

gdje rowInitializerima sljedeću sintaksu:

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

Ova sintaksa kombinira prethodna dva primjera. Budući da se broj elemenata može odrediti iz popisa izraza odvojenih zarezom, ne navodite int_exprizmeđu niti jednog para uglastih zagrada. Evo primjera:

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

Dvodimenzionalni nizovi i varijable niza

Sam po sebi, novostvoreni dvodimenzionalni niz je beskoristan. Njegova se referenca mora dodijeliti varijabli polja kompatibilnog tipa, bilo izravno ili putem poziva metode. Sljedeće sintakse pokazuju kako biste deklarirali ovu varijablu:

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

Svaka sintaksa deklarira varijablu niza koja pohranjuje referencu na dvodimenzionalni niz. Poželjno je postaviti uglate zagrade nakon type. Razmotrite sljedeće primjere:

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

Poput jednodimenzionalnih varijabli niza, dvodimenzionalna varijabla niza povezana je sa .lengthsvojstvom, koje vraća duljinu niza redaka. Na primjer, temperatures1.lengthvraća 2. Svaki je element retka također varijabla niza sa .lengthsvojstvom, koja vraća broj stupaca za niz stupaca dodijeljen elementu retka. Na primjer, temperatures1[0].lengthvraća 3.

S obzirom na varijablu niza, možete pristupiti bilo kojem elementu u dvodimenzionalnom nizu navodeći izraz koji se slaže sa sljedećom sintaksom:

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

Oba indeksa su pozitivna ints koja se kreću od 0 do jedan manje od vrijednosti vraćene iz odgovarajućih .lengthsvojstava. Razmotrimo sljedeća dva primjera:

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

Prvi primjer vraća vrijednost u drugom stupcu prvog retka ( 30.6). Drugi primjer zamjenjuje ovu vrijednost sa 75.0.

Ako navedete negativni indeks ili indeks koji je veći ili jednak vrijednosti koju vraća .lengthsvojstvo varijable polja , Java stvara i baca ArrayIndexOutOfBoundsExceptionobjekt.

Množenje dvodimenzionalnih nizova

Množenje jedne matrice s drugom matricom uobičajena je operacija u područjima od računalne grafike, preko ekonomije do transportne industrije. Programeri obično koriste algoritam Matrix Multiplication za ovu operaciju.

Kako funkcionira množenje matrica? Neka A predstavlja matricu s m redaka i p stupaca. Slično tome, neka B predstavlja matricu s p redaka i n stupaca. Pomnožite A s B da biste dobili matricu C, s m redaka i n stupaca. Svaki cij unos u C dobiva se množenjem svih unosa u i-om retku A odgovarajućim unosima u j-tom stupcu B , a zatim dodavanjem rezultata. Slika 3 ilustrira ove operacije.

Stupci lijeve matrice moraju biti jednaki redovima desne matrice

Množenje matrice zahtijeva da broj stupaca (p) u lijevoj matrici (A) bude jednak broju redaka (p) u desnoj matrici (B). Inače, ovaj algoritam neće raditi.

Sljedeći pseudokod izražava množenje matrice u kontekstu tablice od 2 retka po 2 stupca i 2 redaka po 1 stupac. (Sjetite se da sam pseudokod uveo u 1. dijelu.)

// == == == == == == // | 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

Zbog tri FORpetlje, Matrix Multiplication ima vremensku složenost , koja se izgovara "Big Oh of n cubed". Množenje matrica nudi kubne performanse, što vremenski postaje skupo kad se množe velike matrice. Nudi složenost prostora , koja se izgovara "Big Oh od n * m ", za spremanje dodatne matrice od n redaka po m stupaca. To postaje za kvadratne matrice.O(n3)O(nm)O(n2)

Stvorio sam MatMultJava aplikaciju koja vam omogućuje eksperimentiranje s Matrix Multiplication. Popis 1 predstavlja izvorni kod ove aplikacije.

Popis 1. Java aplikacija za eksperimentiranje s umnožavanjem matrice (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; } }

MatMultdeklarira par matrica i odbacuje njihove vrijednosti na standardni izlaz. Zatim množi obje matrice i odbacuje matricu rezultata na standardni izlaz.

Sastavite popis 1 kako slijedi:

javac MatMult.java

Pokrenite rezultirajuću aplikaciju na sljedeći način:

java MatMult

Trebali biste promatrati sljedeći rezultat:

10 30 20 40 5 7 260 380

Primjer množenja matrica

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.

Nakon stvaranja temperature2niza redaka, njegovi se elementi moraju popuniti referencama na nove nizove stupaca. Sljedeći primjer pokazuje, dodijelivši 3 stupca prvom retku i 2 stupca drugom redu:

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

Dobiveni dvodimenzionalni niz poznat je kao razuđeni niz . Evo drugog primjera: