Datastrukturer og algoritmer i Java, del 2, introducerede en række teknikker til søgning og sortering af endimensionelle arrays, som er de enkleste arrays. I denne vejledning udforsker du flerdimensionelle arrays. Jeg viser dig de tre måder at oprette flerdimensionelle arrays på, så lærer du, hvordan du bruger matrixmultiplikationsalgoritmen til at multiplicere elementer i et todimensionalt array. Jeg introducerer også ragged arrays, og du lærer, hvorfor de er populære til big data-applikationer. Endelig vil vi overveje spørgsmålet om, hvorvidt en matrix er eller er ikke et Java-objekt.
Denne artikel sætter dig op til del 4, som introducerer søgning og sortering med enkeltstående lister.
Flerdimensionelle arrays
EN flerdimensionelt array forbinder hvert element i arrayet med flere indekser. Det mest anvendte flerdimensionale array er to-dimensionelt array, også kendt som en bord eller matrix. Et todimensionelt array forbinder hvert af dets elementer med to indekser.
Vi kan konceptualisere et todimensionelt array som et rektangulært gitter af elementer opdelt i rækker og kolonner. Vi bruger (række, kolonne) notation for at identificere et element som vist i figur 1.
Fordi to-dimensionelle arrays er så almindeligt anvendte, vil jeg fokusere på dem. Det, du lærer om todimensionale arrays, kan generaliseres til højere-dimensionelle.
Oprettelse af to-dimensionelle arrays
Der er tre teknikker til oprettelse af et todimensionelt array i Java:
- Brug af initialisering
- Brug af nøgleordet
ny - Brug af nøgleordet
nymed en initialisering
Brug af initialisering til at oprette et todimensionelt array
Den eneste initialiseringsmetode til oprettelse af et todimensionelt array har følgende syntaks:
'{' [rækkeInitializer (',' rækkeInitializer)*] '}'rækkeInitializer har følgende syntaks:
'{' [ekspr (',' ekspr)*] '}'Denne syntaks angiver, at et todimensionelt array er en valgfri, komma-adskilt liste over rækkeinitialiseringer, der vises mellem åbne og tætte tegn. Desuden er hver rækkeinitialisering en valgfri, kommasepareret liste over udtryk, der vises mellem tegn med åben og tæt klemme. Ligesom endimensionelle arrays skal alle udtryk evalueres til kompatible typer.
Her er et eksempel på et todimensionelt array:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }Dette eksempel opretter en tabel med to rækker og tre kolonner. Figur 2 viser et konceptbillede af denne tabel sammen med en hukommelsesvisning, der viser, hvordan Java lægger denne (og hver) tabel i hukommelsen.
Figur 2 afslører, at Java repræsenterer et todimensionelt array som et endimensionelt rækkearray, hvis elementer henviser til endimensionelle kolonnearrays. Rækkeindekset identificerer kolonnearrayet; kolonneindekset identificerer dataelementet.
Nøgleord nyoprettelse
Nøgleordet ny tildeler hukommelse til et todimensionelt array og returnerer dens reference. Denne tilgang har følgende syntaks:
'ny' type '[' int_ekspr1 ']' '['int_expr2 ']'Denne syntaks angiver, at et todimensionelt array er et område med (positiv) int_ekspr1 rækkeelementer og (positive) int_expr2 kolonneelementer, der alle deler det samme type. Desuden er alle elementer nulstillet. Her er et eksempel:
ny dobbelt [2] [3] // Opret en tabel med to række efter tre kolonner.Nøgleord ny og initialisering oprettelse
Nøgleordet ny med en initialiseringsmetode har følgende syntaks:
'ny' type '[' ']' [' ']' '{' [rækkeInitializer (',' rækkeInitializer)*] '}'hvor rækkeInitializer har følgende syntaks:
'{' [ekspr (',' ekspr)*] '}'Denne syntaks blander de to foregående eksempler. Da antallet af elementer kan bestemmes ud fra de komma-adskilte lister med udtryk, giver du ikke et int_ekspr mellem begge par af firkantede parenteser. Her er et eksempel:
ny dobbelt [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}}To-dimensionelle arrays og arrayvariabler
I sig selv er et nyoprettet todimensionelt array ubrugeligt. Dens reference skal tildeles en array variabel af en kompatibel type, enten direkte eller via et metodeopkald. Følgende syntakser viser, hvordan du ville erklære denne variabel:
typevar_navn '[' ']' '[' ']' type '[' ']' '[' ']' var_navnHver syntaks erklærer en matrixvariabel, der gemmer en henvisning til et todimensionelt array. Det foretrækkes at placere de firkantede parenteser efter type. Overvej følgende eksempler:
dobbelt [] [] temperatur1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; dobbelt [] [] temperatur2 = ny dobbelt [2] [3]; dobbelt [] [] temperaturer3 = nyt dobbelt [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}};Ligesom endimensionelle matrixvariabler er en todimensional matrixvariabel forbundet med en .længde egenskab, som returnerer længden af række array. For eksempel, temperaturer 1. længde returnerer 2. Hvert rækkeelement er også en matrixvariabel med en .længde egenskab, som returnerer antallet af kolonner for det kolonnearray, der er tildelt rækkeelementet. For eksempel, temperaturer1 [0] .længde returnerer 3.
Med en matrixvariabel kan du få adgang til ethvert element i et todimensionelt array ved at angive et udtryk, der stemmer overens med følgende syntaks:
array_var '[' række_indeks ']' '[' col_index ']'Begge indekser er positive ints der varierer fra 0 til en mindre end den værdi, der returneres fra den respektive .længde ejendomme. Overvej de to næste eksempler:
dobbelt temp = temperaturer1 [0] [1]; // Få værdi. temperaturer1 [0] [1] = 75,0; // Indstil værdi.Det første eksempel returnerer værdien i anden kolonne i første række (30.6). Det andet eksempel erstatter denne værdi med 75.0.
Hvis du angiver et negativt indeks eller et indeks, der er større end eller lig med den værdi, der returneres af arrayvariablerne .længde egenskab, Java opretter og kaster en ArrayIndexOutOfBoundsException objekt.
Multiplicere to-dimensionelle arrays
Multiplikation af en matrix med en anden matrix er en almindelig operation inden for områder lige fra computergrafik til økonomi til transportbranchen. Udviklere bruger normalt matrixmultiplikationsalgoritmen til denne operation.
Hvordan fungerer matrixmultiplikation? Lad A repræsentere en matrix med m rækker og s kolonner. Lad B ligeledes repræsentere en matrix med s rækker og n kolonner. Multiplicer A med B for at producere en matrix C, med m rækker og n kolonner. Hver cij indtastning i C opnås ved at multiplicere alle poster i A. med række med tilsvarende poster i B'er jth kolonne og derefter tilføje resultaterne. Figur 3 illustrerer disse operationer.
Venstre matrix kolonner skal svare til højre matrix rækker
Matrixmultiplikation kræver, at antallet af kolonner (p) i den venstre matrix (A) svarer til antallet af rækker (p) i den højre matrix (B). Ellers fungerer denne algoritme ikke.
Følgende pseudokode udtrykker matrixmultiplikation i en 2-række-for-2-søjle og en 2-række-for-1-søjle tabelkontekst. (Husk at jeg introducerede pseudokode i del 1.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == ERKLÆR INTEGER a [] [] = [10, 30] [20, 40] ERKLÆR INTEGER b [] [] = [5, 7] ERKLÆR INTEGER m = 2 // Antal rækker i venstre matrix (a) ERKLÆR INTEGER p = 2 // Antal kolonner i venstre matrix (a) // Antal rækker i højre matrix (b) ERKLÆR INTEGER n = 1 // Antal kolonner i højre matrix (b) ERKLÆR INTEGER c [m] [n] // c holder 2 rækker med 1 kolonne // Alle elementer initialiseres til 0 FOR i = 0 TIL m - 1 FOR j = 0 TIL n - 1 FOR k = 0 TIL p - 1 c [i] [j] = c [i] [j] + a [i] [k] * b [k] [j] NÆSTE k NÆSTE j NÆSTE i SLUTPå grund af de tre TIL sløjfer, Matrix Multiplikation har en tidskompleksitet på O (n3), der udtales "Big Oh of n kuberet. "Matrixmultiplikation giver kubisk ydeevne, hvilket bliver dyrt tidsmæssigt, når store matricer multipliceres. Det giver en rumkompleksitet på O (nm), der udtales "Big Oh of n*m, "til lagring af en ekstra matrix på n rækker efter m kolonner. Dette bliver O (n2) til firkantede matricer.
Jeg har oprettet en MatMult Java-applikation, der giver dig mulighed for at eksperimentere med Matrix Multiplikation. Liste 1 viser applikationens kildekode.
Liste 1. En Java-applikation til eksperimentering med Matrix Multiplikation (MatMult.java)
offentlig endelig klasse 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 = gang (a, b); dump (c); } privat statisk tomrumsdump (int [] [] x) {if (x == null) {System.err.println ("array er null"); Vend tilbage; } // Dump matrixens elementværdier til standardoutputtet i en tabel // -rækkefølge. for (int i = 0; i <x.længde; i ++) {for (int j = 0; j <x [0]. længde; j ++) System.out.print (x [i] [j] + "" ); System.out.println (); }} privat statisk int [] [] gang (int [] [] a, int [] [] b) {// ======================== ================================================= // 1. a.length indeholder a's rækkeantal // // 2. a [0] .length (eller ethvert andet a [x] .length for en gyldig x) indeholder a's // column count // // 3. b.length indeholder b's rækkeantal // // 4. b [0] .længde (eller enhver anden b [x] .længde for et gyldigt x) indeholder b's // kolonneantal // ============= ===================================================== ====== // Hvis a's kolonne tæller! = B's rækkeantal, skal du redde, hvis (en [0] .længde! = B.længde) {System.err.println ("a's kolonneantal! = B's rækkeantal "); returnere null; } // Tildel resultatmatrix med en størrelse lig med a's rækkeoptælling gange b's // kolonnetælling int [] [] resultat = ny int [a.længde] []; for (int i = 0; i <resultat.længde; i ++) resultat [i] = ny int [b [0]. længde]; // Udfør multiplikation og tilføjelse for (int i = 0; i <a.længde; i ++) for (int j = 0; j <b [0]. Længde; j ++) for (int k = 0; k <a [0] .længde; k ++) // eller k <b.længderesultat [i] [j] + = a [i] [k] * b [k] [j]; // Returner resultatmatrixreturresultatet; }}MatMult erklærer et par matrixer og dumper deres værdier til standardoutput. Derefter multiplicerer begge matrixer og dumper resultatmatricen til standardoutput.
Kompilér liste 1 som følger:
javac MatMult.javaKør den resulterende applikation som følger:
java MatMultDu skal overholde følgende output:
10 30 20 40 5 7 260 380Eksempel på matrixmultiplikation
Lad os undersøge et problem, der bedst løses ved matrixmultiplikation. I dette scenarie indlæser en frugtavler i Florida et par sættevogne med 1.250 æsker appelsiner, 400 æsker ferskner og 250 æsker grapefrugt. Figur 4 viser et diagram over markedsprisen pr. Æske for hver slags frugt i fire forskellige byer.
Vores problem er at bestemme, hvor frugten skal sendes og sælges til maksimal bruttoindkomst. For at løse dette problem rekonstruerer vi først diagrammet fra figur 4 som en matrix med fire rækker med tre søjler. Ud fra dette kan vi konstruere en matrix med tre rækker efter en søjle, der vises nedenfor:
== == | 1250 | | | | 400 | | | | 250 | == ==Med begge matricer ved hånden multiplicerer vi simpelthen prismatricen med mængdematricen for at producere en bruttoindkomstmatrix:
== == == == | 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 == == == ==At sende begge sættevogne til Los Angeles giver den højeste bruttoindkomst. Men når afstand og brændstofomkostninger overvejes, er New York måske et bedre valg for at give den højeste indkomst.
Ragged arrays
Efter at have lært om todimensionale arrays, undrer du dig måske over, om det er muligt at tildele endimensionelle kolonnearrays med forskellige længder til elementer i en række array. Svaret er ja. Overvej disse eksempler:
dobbelt [] [] temperatur1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; dobbelt [] [] temperatur2 = nyt dobbelt [2] []; dobbelt [] [] temperaturer3 = nyt dobbelt [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3}};De første og tredje eksempler opretter et todimensionelt array, hvor den første række indeholder tre kolonner, og den anden række indeholder to kolonner. Det andet eksempel opretter en matrix med to rækker og et uspecificeret antal kolonner.
Efter oprettelse temperatur2række række, skal dens elementer udfyldes med referencer til nye kolonnearrays. Det følgende eksempel viser, at der tildeles 3 kolonner til den første række og 2 kolonner til den anden række:
temperaturer2 [0] = ny dobbelt [3]; temperaturer2 [1] = ny dobbelt [2];Den resulterende todimensionale matrix er kendt som en ragged array. Her er et andet eksempel:
