Tietorakenteet ja algoritmit Java-ohjelmassa, osa 2, esitteli erilaisia tekniikoita yksidimensionaalisten matriisien etsimiseksi ja lajittelemiseksi, jotka ovat yksinkertaisimpia matriiseja. Tässä opetusohjelmassa tutkitaan moniulotteisia taulukoita. Näytän sinulle kolme tapaa luoda moniulotteisia taulukoita, sitten opit käyttämään Matrix Multiplication -algoritmia moninkertaistamaan kaksiulotteisen taulukon elementtejä. Esittelen myös repaleiset taulukot ja opit, miksi ne ovat suosittuja big data -sovelluksissa. Lopuksi tarkastelemme kysymystä siitä, onko taulukko on tai ei ole Java-objekti.
Tämä artikkeli asettaa sinut osaan 4, joka esittelee hakemisen ja lajittelun yksinkertaisella linkitetyillä luetteloilla.
Moniulotteiset taulukot
A moniulotteinen taulukko liittää ryhmän kaikki elementit useisiin hakemistoihin. Yleisimmin käytetty moniulotteinen taulukko on kaksiulotteinen taulukko, tunnetaan myös nimellä a pöytä tai matriisi. Kaksiulotteinen taulukko yhdistää kunkin elementin kahteen hakemistoon.
Voimme käsitteellistää kaksiulotteisen taulukon suorakaiteen muotoisena ruudukkona elementteinä, jotka on jaettu riveihin ja sarakkeisiin. Käytämme (rivi sarake) merkintä elementin tunnistamiseksi, kuten kuvassa 1 on esitetty.
Koska kaksiulotteisia taulukoita käytetään niin yleisesti, keskityn niihin. Se, mitä opit kaksiulotteisista matriiseista, voidaan yleistää korkeampiulotteisiksi.
Kaksiulotteisten taulukoiden luominen
Kaksiulotteisen taulukon luomiseen Java-järjestelmään on kolme tekniikkaa:
- Alustusohjelman käyttäminen
- Avainsanan käyttö
Uusi - Avainsanan käyttö
Uusialustusohjelmalla
Alustimen käyttäminen kaksiulotteisen taulukon luomiseen
Vain alustusmenetelmällä kaksiulotteisen taulukon luomisessa on seuraava syntakse:
'{' [rowInitializer (',' rowInitializer)*] '}'rowInitializer sisältää seuraavan syntaksin:
'{' [lauseke (',' lauseke)*] '}'Tässä syntaksissa todetaan, että kaksiulotteinen taulukko on valinnainen, pilkuilla erotettu luettelo rivin alustusohjelmista, jotka näkyvät avoimen ja sulkeutuvan merkin välissä. Lisäksi jokainen rivin alustus on valinnainen, pilkuilla erotettu luettelo lausekkeista, jotka näkyvät avoimen ja suljetun merkin välissä. Kuten yksiulotteiset taulukot, kaikkien lausekkeiden on arvioitava yhteensopivia tyyppejä.
Tässä on esimerkki kaksiulotteisesta taulukosta:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }Tämä esimerkki luo taulukon, jossa on kaksi riviä ja kolme saraketta. Kuvassa 2 on käsitteellinen näkymä tästä taulukosta yhdessä muistinäkymän kanssa, joka osoittaa kuinka Java sijoittaa tämän (ja jokaisen) taulukon muistiin.
Kuvio 2 paljastaa, että Java edustaa kaksiulotteista taulukkoa yksiulotteisena riviryhmänä, jonka elementit viittaavat yksiulotteisiin sarakejoukkoihin. Rivi-indeksi tunnistaa sarakeryhmän; sarakeindeksi tunnistaa tietokohteen.
Avainsana vain uusi luominen
Avainsana Uusi allokoi muistin kaksiulotteiselle taulukolle ja palauttaa sen viitteen. Tällä lähestymistavalla on seuraava syntakse:
'Uusi' tyyppi '[' int_lauseke1 ']' '['int_lauseke2 ']'Tässä syntaksissa todetaan, että kaksiulotteinen taulukko on (positiivisen) alue int_lauseke1 rivielementit ja (positiivinen) int_lauseke2 sarakeelementit, jotka kaikki jakavat saman tyyppi. Lisäksi kaikki elementit nollataan. Tässä on esimerkki:
uusi kaksois [2] [3] // Luo kaksirivinen kolmen sarakkeen taulukko.Avainsanan uusi ja alustusohjelman luominen
Avainsana Uusi alustusmenetelmällä on seuraava syntakse:
'Uusi' tyyppi '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'missä rowInitializer sisältää seuraavan syntaksin:
'{' [lauseke (',' lauseke)*] '}'Tämä syntaksi yhdistää kaksi edellistä esimerkkiä. Koska elementtien lukumäärä voidaan määrittää pilkuilla erotetuissa lausekeluetteloissa, et anna int_expr kummankin hakasulppaparin välillä. Tässä on esimerkki:
uusi kaksinkertainen [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}}Kaksiulotteiset taulukot ja matriisimuuttujat
Itse asiassa vasta luotu kaksiulotteinen taulukko on hyödytön. Sen viite on määritettävä taulukon muuttuja yhteensopivaa tyyppiä joko suoraan tai menetelmäpuhelun kautta. Seuraavat syntaksit osoittavat, kuinka ilmoitat tämän muuttujan:
tyyppivar_name '[' ']' '[' ']' tyyppi '[' ']' '[' ']' var_nameKukin syntaksista ilmoittaa matriisimuuttujan, joka tallentaa viittauksen kaksiulotteiseen ryhmään. On suositeltavaa sijoittaa hakasulkeet jälkeen tyyppi. Harkitse seuraavia esimerkkejä:
kaksinkertaiset [] [] lämpötilat1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; kaksinkertaiset [] [] lämpötilat2 = uusi kaksinkertaiset [2] [3]; kaksinkertainen [] [] lämpötila3 = uusi kaksinkertainen [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}};Kuten yksiulotteiset matriisimuuttujat, myös kaksiulotteinen taulukon muuttuja liittyy a: han .pituus ominaisuus, joka palauttaa riviryhmän pituuden. Esimerkiksi, lämpötilat. pituus palauttaa 2. Jokainen rivielementti on myös matriisimuuttuja, jossa on a .pituus ominaisuus, joka palauttaa rivielementille määritetyn sarakejoukon sarakkeiden määrän. Esimerkiksi, lämpötilat1 [0] .pituus palauttaa 3.
Kun kyseessä on taulukon muuttuja, voit käyttää mitä tahansa kaksiulotteisen taulukon elementtiä määrittämällä lausekkeen, joka on seuraavan syntaksin mukainen:
array_var '[' rivi_hakemisto ']' '[' col_index ']'Molemmat indeksit ovat positiivisia ints jotka vaihtelevat 0: sta pienempään kuin vastaavasta palautettu arvo .pituus ominaisuudet. Harkitse seuraavia kahta esimerkkiä:
kaksinkertainen lämpötila = lämpötilat1 [0] [1]; // Hanki arvo. lämpötilat1 [0] [1] = 75,0; // Aseta arvo.Ensimmäinen esimerkki palauttaa ensimmäisen rivin toisen sarakkeen arvon (30.6). Toinen esimerkki korvaa tämän arvon 75.0.
Jos määrität negatiivisen indeksin tai indeksin, joka on suurempi tai yhtä suuri kuin taulukon muuttujien palauttama arvo .pituus omaisuuden, Java luo ja heittää ArrayIndexOutOfBoundsException esine.
Kaksiulotteisten taulukoiden kertominen
Yhden matriisin kertominen toisella matriisilla on yleinen toiminta tietokonegrafiikasta, taloustieteestä kuljetusalaan. Kehittäjät käyttävät yleensä Matrix Multiplication -algoritmia tähän toimintoon.
Kuinka matriisikertaus toimii? Olkoon A matriisin kanssa m rivit ja s sarakkeita. Olkoon B vastaavasti matriisi, jonka kanssa s rivit ja n sarakkeita. Kerro A: lla B: llä matriisin C tuottamiseksi m rivit ja n sarakkeita. Jokainen cij C-merkintä saadaan kertomalla kaikki A-merkinnät iitt rivi vastaavilla merkinnöillä B: ssä j sarake ja lisäämällä sitten tulokset. Kuva 3 havainnollistaa näitä toimintoja.
Vasemman matriisin sarakkeiden on oltava yhtä suuret oikean matriisin riveillä
Matriisikertaus edellyttää, että vasemman matriisin (A) sarakkeiden (p) määrä on yhtä suuri kuin oikean matriisin (B) rivien (p) lukumäärä. Muuten tämä algoritmi ei toimi.
Seuraava pseudokoodi ilmaisee matriisikertomuksen 2-rivinen-2-sarakkeessa ja 2-rivi-1-sarake-taulukkoyhteydessä. (Muistathan, että esitin pseudokoodin osassa 1.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == JULKAISTA INTEGER a [] [] = [10, 30] [20, 40] ILMOITA INTEGER b [] [] = [5, 7] ILMOITA INTEGER m = 2 // Vasemman matriisin rivien lukumäärä (a) ILMOITA INTEGERI p = 2 // Sarakkeiden lukumäärä vasemmassa matriisissa (a) // Rivien lukumäärä oikeassa matriisissa (b) ILMOITA INTEGERI n = 1 // Sarakkeiden lukumäärä oikealla matriisi (b) ILMOITA INTEGER c [m] [n] // c pitää 2 riviä 1 sarakkeella // Kaikki elementit alustetaan arvoon 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] SEURAAVA k SEURAAVA j SEURAAVA i LOPPUKolmen takia FOR silmukoita, Matriisikertomuksen aikakompleksisuus on O (n3), joka lausutaan "Big Oh of n "Matriisikertolasku tarjoaa kuutiosuorituskyvyn, joka tulee kalliiksi aikasuunnassa, kun suuret matriisit kerrotaan. Se tarjoaa tilaa monimutkaiseksi O (nm), joka lausutaan "Big Oh of n*m, "lisämatriisin tallentamiseksi n riviä m sarakkeita. Tästä tulee O (n2) neliömatriiseille.
Olen luonut MatMult Java-sovellus, jonka avulla voit kokeilla Matrix Multiplication -toimintoa. Listaus 1 esittää tämän sovelluksen lähdekoodin.
Listaus 1. Java-sovellus matriisikertomisen kokeilemiseen (MatMult.java)
public final class MatMult {public static void main (String [] args) {int [] [] a = {{10, 30}, {20, 40}}; int [] [] b = {{5}, {7}}; kaatopaikka (a); System.out.println (); kaatopaikka (b); System.out.println (); int [] [] c = kerro (a, b); kaatopaikka (c); } private static void dump (int [] [] x) {if (x == null) {System.err.println ("taulukko on tyhjä"); palata; } // Tyhjennä matriisin elementin arvot vakiotulosteeseen taulukkomaisessa // järjestyksessä. for (int i = 0; i <x.pituus; i ++) {for (int j = 0; j <x [0] .pituus; j ++) System.out.print (x [i] [j] + "" ); System.out.println (); }} yksityinen staattinen int [] [] kerrotaan (int [] [] a, int [] [] b) {// ====================== ================================================= // 1. a.length sisältää rivien määrän // // 2. a [0] .pituus (tai mikä tahansa muu [x] .pituus kelvolliselle x: lle) sisältää a's // sarakemäärän // // 3. b.pituus sisältää b: n rivimäärä // // 4. b [0] .pituus (tai mikä tahansa muu b [x] .pituus kelvolliselle x: lle) sisältää b: n // sarakemäärän // ============ ==================================================== ====== // Jos a: n sarakkeiden määrä! = B: n rivien määrä, vapauta jos (a [0] .pituus! = B.pituus) {System.err.println ("a: n sarakemäärä! = B: n rivien määrä "); return null; } // Jaa tulosmatriisi, jonka koko on yhtä suuri kuin a-rivien määrä kertaa b: n // sarakkeiden määrä int [] [] tulos = uusi int [a.pituus] []; for (int i = 0; i <tulos.pituus; i ++) tulos [i] = uusi int [b [0] .pituus]; // Suorita (int i = 0; i <a.pituus; i ++) kertolasku ja lisäys (int j = 0; j <b [0] .pituus; j ++) arvolle (int k = 0; k <a [0] .pituus; k ++) // tai k <b. Pituustulos [i] [j] + = a [i] [k] * b [k] [j]; // Palauta tulosmatriisin palautustulos; }}MatMult ilmoittaa matriisiparin ja kaataa niiden arvot vakiolähtöön. Sitten se kertoo molemmat matriisit ja kaataa tulosmatriisin vakiolähtöön.
Koosta Listaus 1 seuraavasti:
javac MatMult.javaSuorita tuloksena oleva sovellus seuraavasti:
java MatMultOta huomioon seuraava tulos:
10 30 20 40 5 7 260 380Esimerkki matriisikertomuksesta
Tutkitaan ongelmaa, joka ratkaistaan parhaiten matriisikertomalla. Tässä skenaariossa Floridan hedelmänviljelijä lataa pari puoliperävaunua 1250 laatikolla appelsiineja, 400 laatikkoa persikoita ja 250 laatikkoa greippiä. Kuvassa 4 on kaavio kunkin hedelmälajin laatikkokohtaisesta markkinahinnasta neljässä eri kaupungissa.
Ongelmamme on määrittää, mihin hedelmät tulisi lähettää ja myydä, jotta bruttotulo olisi mahdollisimman suuri. Tämän ongelman ratkaisemiseksi rekonstruoimme ensin kaavion kuviosta 4 neljän rivin ja kolmen sarakkeen hintamatriisina. Tästä voimme rakentaa kolmen rivin yhden sarakkeen määrämatriisin, joka näkyy alla:
== == | 1250 | | | | 400 | | | | 250 | == ==Molempien matriisien ollessa käsillä kerrotaan yksinkertaisesti hintamatriisi määrämatriisilla bruttotulomatriisin tuottamiseksi:
== == == == | 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 == == == ==Molempien puoliperävaunujen lähettäminen Los Angelesiin tuottaa suurimmat bruttotulot. Mutta kun otetaan huomioon etäisyys ja polttoainekustannukset, ehkä New York on parempi veto korkeimpien tulojen tuottamiseksi.
Ragged taulukot
Kun olet oppinut kaksiulotteisista matriiseista, saatat nyt miettiä, onko mahdollista määrittää yksiulotteisia sarakejoukkoja, joiden pituus on erilainen, riviryhmän elementteihin. Vastaus on kyllä. Harkitse näitä esimerkkejä:
kaksinkertaiset [] [] lämpötilat1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; kaksinkertainen [] [] lämpötila2 = uusi kaksinkertainen [2] []; kaksinkertainen [] [] lämpötila3 = uusi kaksinkertainen [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3}};Ensimmäinen ja kolmas esimerkki luovat kaksiulotteisen taulukon, jossa ensimmäinen rivi sisältää kolme saraketta ja toinen rivi sisältää kaksi saraketta. Toinen esimerkki luo taulukon, jossa on kaksi riviä ja määrittelemätön sarakemäärä.
Luomisen jälkeen lämpötila 2riviryhmän, sen elementit on täytettävä viittaamalla uusiin sarakejoukkoihin. Seuraava esimerkki osoittaa, että 3 saraketta osoitetaan ensimmäiselle riville ja 2 saraketta toiselle riville:
lämpötilat2 [0] = uusi kaksinkertainen [3]; lämpötilat2 [1] = uusi kaksinkertainen [2];Tuloksena oleva kaksiulotteinen taulukko tunnetaan nimellä repaleinen joukko. Tässä on toinen esimerkki:
