Podatkovne strukture in algoritmi v Javi so v 2. delu uvedli različne tehnike za iskanje in razvrščanje enodimenzionalnih nizov, ki so najpreprostejši nizi. V tej vadnici boste raziskali večdimenzionalne nize. Pokazal vam bom tri načine za ustvarjanje večdimenzionalnih nizov, nato pa se boste naučili, kako uporabljati algoritem Matrix Multiplication za množenje elementov v dvodimenzionalni matriki. Predstavil vam bom tudi raztrgane nize in izvedeli boste, zakaj so priljubljeni pri aplikacijah za velike podatke. Na koncu bomo preučili vprašanje, ali je matrika je ali ni objekt Java.
V tem članku ste pripravljeni na 4. del, ki uvaja iskanje in razvrščanje s posamično povezanimi seznami.
Večdimenzionalni nizi
A večdimenzionalno polje vsak element v matriki poveže z več indeksi. Najpogosteje uporabljena večdimenzionalna matrika je dvodimenzionalno polje, znan tudi kot a miza ali matriko. Dvodimenzionalno polje poveže vsakega od svojih elementov z dvema indeksoma.
Dvodimenzionalno matriko lahko konceptualiziramo kot pravokotno mrežo elementov, razdeljenih v vrstice in stolpce. Uporabljamo (vrstica, stolpec) zapis za identifikacijo elementa, kot je prikazano na sliki 1.
Ker se dvodimenzionalna polja tako pogosto uporabljajo, se bom osredotočil na njih. Kar izveš o dvodimenzionalnih nizih, je mogoče posplošiti na višjedimenzionalne.
Ustvarjanje dvodimenzionalnih nizov
Obstajajo tri tehnike za ustvarjanje dvodimenzionalnega polja v Javi:
- Uporaba inicializatorja
- Uporaba ključne besede
novo - Uporaba ključne besede
novoz inicializatorjem
Uporaba inicializatorja za ustvarjanje dvodimenzionalne matrike
Pristop samo za inicializacijo k ustvarjanju dvodimenzionalnega polja ima naslednjo sintakso:
'{' [rowInitializer (',' rowInitializer)*] '}'rowInitializer ima naslednjo sintakso:
'{' [ekspr (',' ekspr)*] '}'Ta sintaksa navaja, da je dvodimenzionalno polje neobvezen seznam inicializatorjev vrstic, ločenih z vejicami, ki se prikaže med odprtimi in zaklenjenimi znaki. Poleg tega je vsaka inicializacija vrstic neobvezen, z vejicami ločen seznam izrazov, ki se pojavijo med odprtimi in zaklenjenimi znaki. Tako kot enodimenzionalni nizi morajo tudi vsi izrazi veljati za združljive tipe.
Tu je primer dvodimenzionalne matrike:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }Ta primer ustvari tabelo z dvema vrsticama in tremi stolpci. Na sliki 2 je predstavljen konceptualni pogled te tabele skupaj s pomnilniškim prikazom, ki prikazuje, kako Java postavlja to (in vsako) tabelo v pomnilnik.
Slika 2 razkriva, da Java predstavlja dvodimenzionalno polje kot enodimenzionalno polje vrstic, katerega elementi se sklicujejo na enodimenzionalna polja stolpcev. Indeks vrstic identificira matriko stolpcev; indeks stolpca identificira podatkovno postavko.
Ključna beseda samo novo ustvarjanje
Ključna beseda novo dodeli pomnilnik za dvodimenzionalno polje in vrne njegovo referenco. Ta pristop ima naslednjo sintakso:
'novo' tip '[' int_expr1 ']' '['int_expr2 ']'Ta sintaksa navaja, da je dvodimenzionalno polje območje (pozitivno) int_expr1 elementi vrstic in (pozitivno) int_expr2 elementi stolpcev, ki si delijo isto tip. Poleg tega so vsi elementi ničlirani. Tu je primer:
new double [2] [3] // Ustvari tabelo z dvema vrsticama za tri stolpce.Ključna beseda novo in ustvarjanje inicializatorja
Ključna beseda novo z inicializacijskim pristopom ima naslednjo sintakso:
'novo' tip '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'kje rowInitializer ima naslednjo sintakso:
'{' [ekspr (',' ekspr)*] '}'Ta sintaksa združuje prejšnja dva primera. Ker je število elementov mogoče določiti na seznamih izrazov, ločenih z vejico, ne navedete int_expr med obema paroma oglatih oklepajev. Tu je primer:
novo dvojno [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}Dvodimenzionalna polja in spremenljivke matrike
Novo ustvarjeno dvodimenzionalno polje je samo po sebi neuporabno. Njegova referenca mora biti dodeljena datoteki spremenljivka polja združljive vrste, bodisi neposredno bodisi prek klica metode. Naslednje sintakse kažejo, kako bi deklarirali to spremenljivko:
tipvar_name '[' ']' '[' ']' tip '[' ']' '[' ']' var_nameVsaka sintaksa razglasi spremenljivko matrike, ki shrani sklic na dvodimenzionalno matriko. Oglate oklepaje je raje postaviti za tip. Upoštevajte naslednje primere:
dvojne [] [] temperature1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; dvojne [] [] temperature2 = nove dvojne [2] [3]; dvojne [] [] temperature3 = nove dvojne [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}};Tako kot enodimenzionalne spremenljivke polja je tudi dvodimenzionalna spremenljivka matrice povezana z .length lastnost, ki vrne dolžino polja vrstic. Na primer, temperature1.dolžina vrne 2. Vsak element vrstice je tudi spremenljivka polja z a .length lastnost, ki vrne število stolpcev za matriko stolpcev, dodeljeno elementu vrstice. Na primer, temperature1 [0] .dolžina vrne 3.
Glede na spremenljivko matrike lahko do katerega koli elementa v dvodimenzionalni matriki dostopate tako, da podate izraz, ki se ujema z naslednjo sintakso:
array_var '[' index_vrst ']' '[' col_index ']'Oba indeksa sta pozitivna ints, ki se gibljejo od 0 do ene manj od vrednosti, vrnjene iz ustreznega .length lastnosti. Poglejmo naslednja dva primera:
dvojna temperatura = temperature1 [0] [1]; // Pridobite vrednost. temperature1 [0] [1] = 75,0; // Nastavitev vrednosti.Prvi primer vrne vrednost v drugem stolpcu prve vrstice (30.6). Drugi primer nadomesti to vrednost z 75.0.
Če podate negativni indeks ali indeks, ki je večji ali enak vrednosti, ki jo vrne spremenljivka polja .length Java ustvari in vrže datoteko ArrayIndexOutOfBoundsException predmet.
Množenje dvodimenzionalnih nizov
Množenje ene matrike z drugo matriko je pogosta operacija na področjih, od računalniške grafike, ekonomije do transportne industrije. Razvijalci za to operacijo običajno uporabljajo algoritem matričnega množenja.
Kako deluje množenje matric? Naj A predstavlja matriko z m vrstice in str stolpci. Podobno naj B predstavlja matriko z str vrstice in n stolpci. Pomnožite A z B, da dobite matriko C z m vrstice in n stolpci. Vsak cij vnos v C dobimo tako, da pomnožimo vse vnose v A-jih i vrstico z ustreznimi vnosi v B-jih jth stolpec, nato dodajte rezultate. Slika 3 prikazuje te operacije.
Levi matrični stolpci morajo biti enaki desnim matričnim vrsticam
Množenje matrice zahteva, da je število stolpcev (p) v levi matrici (A) enako številu vrstic (p) v desni matrici (B). V nasprotnem primeru ta algoritem ne bo deloval.
Naslednja psevdokoda izraža množenje matrike v kontekstu tabele 2-vrstici-za-2-stolpca. (Spomnimo se, da sem v 1. delu uvedel psevdokodo.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == RAZGLASI INTEGER a [] [] = [10, 30] [20, 40] IZGLASI INTEGER b [] [] = [5, 7] RAZGLASI INTEGER m = 2 // Število vrstic v levi matrici (a) DECLARE INTEGER p = 2 // Število stolpcev v levi matrici (a) // Število vrstic v desni matrici (b) DECLARE INTEGER n = 1 // Število stolpcev v desni matrika (b) IZJAVA INTEGERA c [m] [n] // c vsebuje 2 vrstici z 1 stolpcem // Vsi elementi se inicializirajo na 0 FOR i = 0 DO 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] NASLEDNJA k NASLEDNJA j NASLEDNJA in KONECZaradi treh ZA zanke, Matrix Multiplication ima časovno zapletenost O (n3), ki se izgovarja "Big Oh of n "Matrix Multiplication ponuja kubično zmogljivost, ki postane časovno draga, ko se množijo velike matrice. Ponuja prostorsko zapletenost O (nm), ki se izgovarja "Big Oh of n*m, "za shranjevanje dodatne matrike n vrstic do m stolpci. To postane O (n2) za kvadratne matrike.
Ustvaril sem MatMult Aplikacija Java, ki vam omogoča eksperimentiranje z matričnim množenjem. Seznam 1 predstavlja izvorno kodo te aplikacije.
Seznam 1. Aplikacija Java za eksperimentiranje z matričnim množenjem (MatMult.java)
javni končni razred MatMult {public static void main (String [] args) {int [] [] a = {{10, 30}, {20, 40}}; int [] [] b = {{5}, {7}}; smetišče (a); System.out.println (); smetišče (b); System.out.println (); int [] [] c = pomnoži (a, b); odlagališče (c); } zasebno statično praznjenje praznine (int [] [] x) {if (x == null) {System.err.println ("matrika je nična"); vrnitev; } // V tabelarni // vrstni red izpiši vrednosti elementov matrike na standardni izhod. 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 (); }} zasebni statični int [] [] pomnoži (int [] [] a, int [] [] b) {// ====================== ================================================ // 1. a.length vsebuje število vrstic // // 2. a [0] .length (ali katero koli drugo [x] .length za veljaven x) vsebuje a // count stolpcev // // b.length vsebuje b-jevo število vrstic // // 4. b [0] .length (ali katero koli drugo b [x] .length za veljaven x) vsebuje b-jevo // število stolpcev // ============ ==================================================== ====== // Če šteje stolpec a! = Število vrstic b, rešite if (a [0] .length! = B.length) {System.err.println ("število stolpcev a! = Število vrstic b "); vrni null; } // Dodelimo matriko rezultatov z velikostjo, ki je enaka številu vrstic a krat krat b // štetje stolpcev int [] [] rezultat = nov int [a.length] []; for (int i = 0; i <result.length; i ++) result [i] = new int [b [0] .length]; // Izvedimo množenje in seštevanje za (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 ++) // ali k <b.length result [i] [j] + = a [i] [k] * b [k] [j]; // Vrne matriko rezultata vrne rezultat; }}MatMult izjavi par matric in odvrže njihove vrednosti na standardni izhod. Nato pomnoži obe matriki in matriko rezultatov odvrne na standardni izhod.
Sestavite seznam 1, kot sledi:
javac MatMult.javaNastalo aplikacijo zaženite na naslednji način:
java MatMultUpoštevati morate naslednje rezultate:
10 30 20 40 5 7 260 380Primer množenja matrik
Raziščimo problem, ki ga je najbolje rešiti z množenjem matrik. V tem primeru sadjar na Floridi napolni nekaj polpriklopnikov z 1.250 škatlami pomaranč, 400 škatel breskev in 250 škatlicami grenivke. Slika 4 prikazuje grafikon tržne cene na škatlo za vsako vrsto sadja v štirih različnih mestih.
Naša težava je določiti, kam je treba sadje odpremiti in prodati za največji bruto dohodek. Da bi rešili to težavo, najprej rekonstruiramo grafikon s slike 4 kot matriko cen v štirih vrsticah s tremi stolpci. Iz tega lahko sestavimo matriko količin v treh vrsticah z enim stolpcem, ki je prikazana spodaj:
== == | 1250 | | | | 400 | | | | 250 | == ==Z obema matricama preprosto pomnožimo matriko cen s matrico količin, da dobimo matriko bruto dohodka:
== == == == | 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 == == == ==Pošiljanje obeh polpriklopnikov v Los Angeles bo ustvarilo najvišji bruto dohodek. Toda če upoštevamo razdaljo in stroške goriva, je morda New York boljša stava za največji dohodek.
Raztrgana polja
Ko ste se naučili dvodimenzionalnih nizov, se lahko zdaj vprašate, ali je mogoče elementom vrsticnega niza dodeliti enodimenzionalna polja stolpcev z različno dolžino. Odgovor je pritrdilen. Upoštevajte te primere:
dvojne [] [] temperature1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; dvojne [] [] temperature2 = nove dvojne [2] []; dvojne [] [] temperature3 = nove dvojne [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3}};Prvi in tretji primer ustvarijo dvodimenzionalno matriko, kjer prva vrstica vsebuje tri stolpce, druga vrstica pa dva stolpca. Drugi primer ustvari matriko z dvema vrsticama in neopredeljenim številom stolpcev.
Po ustvarjanju temperatura2polje vrstice, njeni elementi morajo biti poseljeni s sklici na nove nize stolpcev. Naslednji primer prikazuje, da se prvi vrstici dodelijo 3 stolpci, drugi pa 2 stolpca:
temperature2 [0] = novo dvojno [3]; temperature2 [1] = nova dvojna [2];Nastalo dvodimenzionalno polje je znano kot raztrgano polje. Tu je drugi primer:
