Datastrukturer og algoritmer i Java, del 2, introduserte en rekke teknikker for å søke og sortere endimensjonale matriser, som er de enkleste matriser. I denne opplæringen vil du utforske flerdimensjonale matriser. Jeg viser deg de tre måtene å lage flerdimensjonale matriser, så lærer du hvordan du bruker matriksmultiplikasjonsalgoritmen til å multiplisere elementer i en todimensjonal matrise. Jeg vil også introdusere tøffe matriser, og du vil lære hvorfor de er populære for big data-applikasjoner. Til slutt vil vi vurdere spørsmålet om en matrise er eller er ikke et Java-objekt.
Denne artikkelen setter deg opp for del 4, som introduserer søk og sortering med enkeltkoblede lister.
Flerdimensjonale matriser
EN flerdimensjonalt utvalg knytter hvert element i matrisen til flere indekser. Den mest brukte flerdimensjonale matrisen er todimensjonalt array, også kjent som en bord eller matrise. En todimensjonal matrise knytter hvert av elementene til to indekser.
Vi kan konseptualisere en todimensjonal matrise som et rektangulært rutenett av elementer delt inn i rader og kolonner. Vi bruker (rad kolonne)
notasjon for å identifisere et element, som vist i figur 1.
Fordi todimensjonale matriser er så ofte brukt, vil jeg fokusere på dem. Det du lærer om todimensjonale matriser, kan generaliseres til høyere dimensjonale.
Opprette todimensjonale matriser
Det er tre teknikker for å lage et todimensjonalt utvalg i Java:
- Bruke en initialisering
- Bruke nøkkelordet
ny
- Bruke nøkkelordet
ny
med initialisering
Bruke en initialisering til å lage et todimensjonalt array
Den eneste initialiseringsmetoden for å lage en todimensjonal matrise har følgende syntaks:
'{' [rowInitializer (',' rowInitializer)*] '}'
rowInitializer
har følgende syntaks:
'{' [ekspr (',' ekspr)*] '}'
Denne syntaksen sier at en todimensjonal matrise er en valgfri, kommaadskilt liste over radinitialiserere som vises mellom tegn med åpen og nær klammeparentes. Videre er hver radinitialiser en valgfri kommadelt liste over uttrykk som vises mellom tegn med åpen og tett klammeparentes. I likhet med endimensjonale matriser, må alle uttrykk evalueres til kompatible typer.
Her er et eksempel på en todimensjonal matrise:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }
Dette eksemplet oppretter en tabell med to rader og tre kolonner. Figur 2 presenterer en konseptuell oversikt over denne tabellen sammen med en minnevisning som viser hvordan Java legger ut denne (og alle) tabellene i minnet.
Figur 2 avslører at Java representerer en todimensjonal matrise som en endimensjonal radmatrise der elementene refererer til endimensjonale kolonnearriser. Radindeksen identifiserer kolonnearrayen; kolonneindeksen identifiserer dataelementet.
Søkeord nyoppretting
Nøkkelordet ny
tildeler minne for et todimensjonalt array og returnerer referansen. Denne tilnærmingen har følgende syntaks:
'ny' type '[' int_expr1 ']' '['int_expr2 ']'
Denne syntaksen sier at en todimensjonal matrise er en region av (positiv) int_expr1
radelementer og (positive) int_expr2
kolonneelementer som alle deler det samme type
. Videre nullstilles alle elementene. Her er et eksempel:
ny dobbel [2] [3] // Opprett en to-rad-for-tre-kolonnetabell.
Nøkkelord opprettelse og initialisering
Nøkkelordet ny
med en initialiseringsmetode har følgende syntaks:
'ny' type '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'
hvor rowInitializer
har følgende syntaks:
'{' [ekspr (',' ekspr)*] '}'
Denne syntaksen blander de to foregående eksemplene. Fordi antall elementer kan bestemmes fra kommaseparerte lister med uttrykk, gir du ikke et int_ekspr
mellom hvert par firkantede parenteser. Her er et eksempel:
ny dobbel [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}}
To-dimensjonale matriser og arrayvariabler
I seg selv er et nyopprettet todimensjonalt array ubrukelig. Henvisningen må tilordnes en array variabel av en kompatibel type, enten direkte eller via en metodeanrop. Følgende syntakser viser hvordan du vil erklære denne variabelen:
typevar_name '[' ']' '[' ']' type '[' ']' '[' ']' var_name
Hver syntaks deklarerer en arrayvariabel som lagrer en referanse til et todimensjonalt array. Det er foretrukket å plassere firkantede parenteser etter type
. Tenk på følgende eksempler:
doble [] [] temperaturer1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; doble [] [] temperaturer2 = nye doble [2] [3]; doble [] [] temperaturer3 = nye doble [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}};
I likhet med endimensjonale arrayvariabler, er en todimensjonal arrayvariabel assosiert med a .lengde
eiendom, som returnerer lengden på radmatrisen. For eksempel, temperaturer1.lengde
returnerer 2. Hvert radelement er også en arrayvariabel med a .lengde
egenskap, som returnerer antall kolonner for kolonnearrayen som er tildelt radelementet. For eksempel, temperaturer1 [0] .lengde
returnerer 3.
Gitt en arrayvariabel, kan du få tilgang til ethvert element i en todimensjonal array ved å spesifisere et uttrykk som stemmer overens med følgende syntaks:
array_var '[' rad_indeks ']' '[' col_index ']'
Begge indeksene er positive int
s som varierer fra 0 til en mindre enn verdien som returneres fra den respektive .lengde
eiendommer. Tenk på de to neste eksemplene:
dobbelt temp = temperaturer1 [0] [1]; // Få verdi. temperaturer 1 [0] [1] = 75,0; // Sett verdi.
Det første eksemplet returnerer verdien i den andre kolonnen i første rad (30.6
). Det andre eksemplet erstatter denne verdien med 75.0
.
Hvis du spesifiserer en negativ indeks eller en indeks som er større enn eller lik verdien som returneres av arrayvariabelen .lengde
eiendom, Java oppretter og kaster en ArrayIndexOutOfBoundsException
gjenstand.
Multiplisere todimensjonale matriser
Å multiplisere en matrise med en annen matrise er en vanlig operasjon innen felt som strekker seg fra datagrafikk, til økonomi, til transportindustrien. Utviklere bruker vanligvis Matrix Multiplication-algoritmen for denne operasjonen.
Hvordan fungerer matriksmultiplikasjon? La A representere en matrise med m rader og s kolonner. På samme måte la B representere en matrise med s rader og n kolonner. Multipliser A med B for å produsere en matrise C, med m rader og n kolonner. Hver cij oppføring i C oppnås ved å multiplisere alle oppføringer i A. ith rad med tilsvarende oppføringer i B-er jth kolonne og deretter legge til resultatene. Figur 3 illustrerer disse operasjonene.
Venstre matrisekolonner må være lik høyrematrikserader
Matrisemultiplikasjon krever at antall kolonner (p) i venstre matrise (A) tilsvarer antall rader (p) i høyre matrise (B). Ellers fungerer ikke denne algoritmen.
Følgende pseudokode uttrykker matriksmultiplikasjon i en 2-rad-for-2-kolonne og en 2-rad-for-1-kolonnetabellkontekst. (Husk at jeg introduserte 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 // Antall rader i venstre matrise (a) ERKLÆR INTEGER p = 2 // Antall kolonner i venstre matrise (a) // Antall rader i høyre matrise (b) ERKL. INTEGER n = 1 // Antall kolonner i høyre matrise (b) ERKLÆR INTEGER c [m] [n] // c holder 2 rader med 1 kolonne // Alle elementene 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] NESTE k NESTE j NESTE i SLUTT
På grunn av de tre TIL
loop, Matrix Multiplikation har en tidskompleksitet på O (n3)
, som uttales "Big Oh of n "Matrisemultiplikasjon gir kubikkytelse, noe som blir dyrt tidsmessig når store matrikser multipliseres. Det gir en romkompleksitet på O (nm)
, som uttales "Big Oh of n*m, "for lagring av en ekstra matrise på n rader etter m kolonner. Dette blir O (n2)
for firkantede matrikser.
Jeg har opprettet en MatMult
Java-applikasjon som lar deg eksperimentere med Matrix Multiplikation. Oppføring 1 viser kildekoden til dette programmet.
Oppføring 1. En Java-applikasjon for å eksperimentere med Matrix Multiplication (MatMult.java)
offentlig sluttklasse 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 = multipliser (a, b); dump (c); } privat statisk ugyldig dump (int [] [] x) {if (x == null) {System.err.println ("array er null"); komme tilbake; } // Dump matriseens elementverdier til standardutdata i en tabell // rekkefølge. 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 (); }} privat statisk int [] [] multipliser (int [] [] a, int [] [] b) {// ======================== ================================================= // 1. a.length inneholder a's radtelling // // 2. a [0] .length (eller hvilken som helst annen a [x] .length for en gyldig x) inneholder a's // column count // // 3. b.length inneholder bs radtelling // // 4. b [0] .lengde (eller annen b [x] .lengde for et gyldig x) inneholder bs // kolonnetall // ============ ===================================================== ====== // // Hvis kolonnen teller! = Rens antall teller, kausjonerer hvis (a [0] .length! = B.length) {System.err.println ("a's column count! = B's row count "); return null; } // Tildel resultatmatrise med en størrelse som er lik antall ganger b's // kolonnetall int [] [] resultat = ny int [a.lengde] []; for (int i = 0; i <resultat.lengde; i ++) resultat [i] = ny int [b [0]. lengde]; // Utfør multiplikasjon og tillegg for (int i = 0; i <a.length; i ++) for (int j = 0; j <b [0] .length; j ++) for (int k = 0; k <a [0] .lengde; k ++) // eller k <b.lengderesultat [i] [j] + = a [i] [k] * b [k] [j]; // Returner resultatmatriseresultatresultatet; }}
MatMult
erklærer et par matriser og dumper verdiene sine til standardutdata. Deretter multipliserer begge matrikser og dumper resultatmatrisen til standard utgang.
Sammensett oppføring 1 som følger:
javac MatMult.java
Kjør den resulterende applikasjonen som følger:
java MatMult
Du bør følge følgende utdata:
10 30 20 40 5 7 260 380
Eksempel på matriksmultiplikasjon
La oss utforske et problem som best løses ved matriksmultiplikasjon. I dette scenariet laster en fruktavler i Florida et par semitrailere med 1250 bokser appelsiner, 400 bokser med fersken og 250 bokser grapefrukt. Figur 4 viser et diagram over markedsprisen per eske for hver type frukt, i fire forskjellige byer.
Problemet vårt er å bestemme hvor frukten skal sendes og selges for maksimal bruttoinntekt. For å løse dette problemet rekonstruerer vi først diagrammet fra figur 4 som en prisrute med fire rader med tre kolonner. Fra dette kan vi konstruere en tre-rad med en kolonne mengdematrise, som vises nedenfor:
== == | 1250 | | | | 400 | | | | 250 | == ==
Med begge matriser for hånd multipliserer vi bare prismatrisen med mengdematrisen for å produsere en bruttoinntektsmatrise:
== == == == | 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 == == == ==
Å sende begge semitrailere til Los Angeles gir den høyeste bruttoinntekten. Men når avstand og drivstoffkostnader vurderes, er kanskje New York en bedre innsats for å gi den høyeste inntekten.
Ragged arrays
Etter å ha lært om todimensjonale matriser, kan du nå lure på om det er mulig å tilordne endimensjonale kolonnearriser med forskjellige lengder til elementer i en radmatrise. Svaret er ja. Tenk på disse eksemplene:
doble [] [] temperaturer1 = {{20.5, 30.6, 28.3}, {-38.7, -18.3}}; doble [] [] temperaturer2 = nye doble [2] []; dobbel [] [] temperaturer3 = ny dobbel [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3}};
Det første og tredje eksemplet lager en todimensjonal matrise der den første raden inneholder tre kolonner og den andre raden inneholder to kolonner. Det andre eksemplet oppretter en matrise med to rader og et uspesifisert antall kolonner.
Etter å ha opprettet temperatur2
radrekke, må elementene fylles ut med referanser til nye kolonnearriser. Følgende eksempel viser, tilordner 3 kolonner til første rad og 2 kolonner til andre rad:
temperaturer2 [0] = ny dobbel [3]; temperaturer2 [1] = ny dobbel [2];
Den resulterende todimensjonale matrisen er kjent som en fillete array. Her er et annet eksempel: