Dátové štruktúry a algoritmy v Jave, časť 2, predstavili rôzne techniky vyhľadávania a triedenia jednorozmerných polí, ktoré sú najjednoduchšími poľami. V tomto výučbe sa dozviete viacrozmerné polia. Ukážem vám tri spôsoby, ako vytvoriť multidimenzionálne polia, potom sa naučíte, ako používať algoritmus Matrix Multiplication na násobenie prvkov v dvojrozmernom poli. Taktiež predstavím členité polia a dozviete sa, prečo sú populárne pre aplikácie veľkých dát. Na záver zvážime otázku, či ide o pole je alebo nie je objekt Java.
Tento článok vás pripravuje na časť 4, ktorá predstavuje vyhľadávanie a triedenie pomocou jednotlivo prepojených zoznamov.
Multidimenzionálne polia
A multidimenzionálne pole priraďuje každý prvok v poli k viacerým indexom. Najbežnejšie používané viacrozmerné pole je dvojrozmerné pole, tiež známy ako a stôl alebo matrica. Dvojrozmerné pole spája každý z jeho prvkov s dvoma indexmi.
Dvojrozmerné pole môžeme konceptualizovať ako obdĺžnikovú mriežku prvkov rozdelenú na riadky a stĺpce. Používame (riadok stĺpec)
zápis na identifikáciu prvku, ako je znázornené na obrázku 1.
Pretože dvojrozmerné polia sú tak bežne používané, zameriam sa na ne. To, čo sa dozviete o dvojrozmerných poliach, sa dá zovšeobecniť na vyššie dimenzionálne polia.
Vytváranie dvojrozmerných polí
Existujú tri techniky na vytvorenie dvojrozmerného poľa v Jave:
- Pomocou inicializátora
- Pomocou kľúčového slova
Nový
- Pomocou kľúčového slova
Nový
s inicializátorom
Použitie inicializátora na vytvorenie dvojrozmerného poľa
Prístup iba pre inicializátor k vytvoreniu dvojrozmerného poľa má nasledujúcu syntax:
'{' [rowInitializer (',' rowInitializer)*] '}'
rowInitializer
má nasledujúcu syntax:
'{' [expr (',' expr)*] '}'
Táto syntax uvádza, že dvojrozmerné pole je voliteľný zoznam inicializátorov riadkov oddelených čiarkami, ktoré sa objavujú medzi znakmi otvorenej a zatvorenej zátvorky. Ďalej je každý inicializátor riadkov voliteľným zoznamom výrazov oddelených čiarkou, ktoré sa objavujú medzi znakmi otvorenej a zátvorky. Rovnako ako jednorozmerné polia, aj všetky výrazy sa musia vyhodnotiť na kompatibilné typy.
Tu je príklad dvojrozmerného poľa:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }
V tomto príklade sa vytvorí tabuľka s dvoma riadkami a tromi stĺpcami. Obrázok 2 predstavuje koncepčný pohľad na túto tabuľku spolu s pohľadom na pamäť, ktorý ukazuje, ako Java rozloží túto (a každú) tabuľku v pamäti.
Obrázok 2 ukazuje, že Java predstavuje dvojrozmerné pole ako jednorozmerné riadkové pole, ktorého prvky odkazujú na jednorozmerné polia stĺpcov. Index riadkov identifikuje pole stĺpcov; index stĺpca identifikuje údajovú položku.
Kľúčové slovo tvorba iba pre nové
Kľúčové slovo Nový
alokuje pamäť pre dvojrozmerné pole a vráti jeho referenciu. Tento prístup má nasledujúcu syntax:
'Nový' typu '[' int_expr1 ']' '['int_expr2 ']'
Táto syntax uvádza, že dvojrozmerné pole je oblasťou (kladného) int_expr1
riadkové prvky a (kladné) int_expr2
prvky stĺpca, ktoré zdieľajú všetky rovnako typu
. Ďalej sú všetky prvky vynulované. Tu je príklad:
nový double [2] [3] // Vytvorte tabuľku dva riadky po troch stĺpcoch.
Nové kľúčové slovo a tvorba inicializátora
Kľúčové slovo Nový
s prístupom inicializátora má nasledujúcu syntax:
'Nový' typu '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'
kde rowInitializer
má nasledujúcu syntax:
'{' [expr (',' expr)*] '}'
Táto syntax spája predchádzajúce dva príklady. Pretože počet prvkov je možné určiť zo zoznamov výrazov oddelených čiarkami, neposkytujete znak int_expr
medzi dvojicou hranatých zátvoriek. Tu je príklad:
nový double [] [] {{20.5, 30.6, 28.3}, {-38,7, -18,3, -16,2}}
Dvojrozmerné polia a premenné poľa
Samo o sebe je novovytvorené dvojrozmerné pole zbytočné. Jeho odkaz musí byť priradený k premenná poľa kompatibilného typu, a to buď priamo, alebo prostredníctvom metodického volania. Nasledujúce syntaxe ukazujú, ako by ste deklarovali túto premennú:
typuvar_name '[' ']' '[' ']' typu '[' ']' '[' ']' var_name
Každá syntax deklaruje premennú poľa, ktorá uchováva odkaz na dvojrozmerné pole. Je lepšie umiestniť hranaté zátvorky za typu
. Zvážte nasledujúce príklady:
dvojnásobok [] [] teploty1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; dvojnásobok [] [] teploty2 = nový dvojnásobok [2] [3]; dvojnásobok [] [] teploty3 = nový dvojnásobok [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}};
Rovnako ako premenné jednorozmerného poľa, aj premenná dvojrozmerného poľa je spojená s a .dĺžka
vlastnosť, ktorá vracia dĺžku riadkového poľa. Napríklad, teploty 1.dlžka
vráti 2. Každý riadkový prvok je tiež premennou poľa s a .dĺžka
vlastnosť, ktorá vráti počet stĺpcov pre pole stĺpcov priradených k prvku riadku. Napríklad, teploty1 [0] .dĺžka
vracia 3.
Vzhľadom na premennú poľa môžete získať prístup k ľubovoľnému prvku v dvojrozmernom poli zadaním výrazu, ktorý súhlasí s nasledujúcou syntaxou:
pole_var '[' riadok_index ']' '[' col_index ']'
Oba indexy sú kladné int
s, ktoré sú v rozsahu od 0 do jednej menej ako hodnota vrátená z príslušného .dĺžka
vlastnosti. Zvážte nasledujúce dva príklady:
dvojnásobná teplota = teploty1 [0] [1]; // Získajte hodnotu. teploty1 [0] [1] = 75,0; // Nastaviť hodnotu.
Prvý príklad vráti hodnotu v druhom stĺpci prvého riadku (30.6
). Druhý príklad nahrádza túto hodnotu znakom 75.0
.
Ak zadáte záporný index alebo index, ktorý je väčší alebo rovný hodnote vrátenej premennou poľa .dĺžka
majetku, Java vytvorí a hodí ArrayIndexOutOfBoundsException
objekt.
Násobenie dvojrozmerných polí
Násobenie jednej matice druhou maticou je bežná operácia v oblastiach od počítačovej grafiky, cez ekonomiku až po dopravný priemysel. Vývojári pre túto operáciu zvyčajne používajú algoritmus Matrix Multiplication.
Ako funguje násobenie matíc? Nech A predstavuje maticu s m riadky a p stĺpce. Podobne nech B predstavuje maticu s p riadky a n stĺpce. Vynásobte A číslom B a vytvorte maticu C s m riadky a n stĺpce. Každý cij položka v C sa získa vynásobením všetkých položiek v A i riadku zodpovedajúcimi položkami v B. jth stĺpec a potom pridajte výsledky. Obrázok 3 zobrazuje tieto operácie.
Stĺpce vľavo matice sa musia rovnať riadkom vpravo matice
Násobenie matíc vyžaduje, aby sa počet stĺpcov (p) v ľavej matici (A) rovnal počtu riadkov (p) v pravej matici (B). V opačnom prípade tento algoritmus nebude fungovať.
Nasledujúci pseudokód vyjadruje násobenie matíc v kontexte tabuľky 2-riadok po 2 a 2-riadok po 1 stĺpci. (Pripomeňme, že som v časti 1 uviedol pseudokód.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == VYHLASOVAŤ INTEGER a [] [] = [10, 30] [20, 40] VYHLASOVAŤ INTEGER b [] [] = [5, 7] VYHLADOVAŤ INTEGER m = 2 // Počet riadkov v ľavej matici (a) DECLARE INTEGER p = 2 // Počet stĺpcov v ľavej matici (a) // Počet riadkov v pravej matici (b) DECLARE INTEGER n = 1 // Počet stĺpcov vpravo matica (b) DECLARE INTEGER c [m] [n] // c obsahuje 2 riadky po 1 stĺpci // Všetky prvky sa inicializujú na 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] ĎALŠIE k ĎALŠIE j ĎALŠIE i KONIEC
Kvôli tým trom ZA
slučky, Matrix Multiplication má časovú zložitosť O (n3)
, ktorý sa vyslovuje „Big Oh of n „Matrix Multiplication ponúka kubický výkon, ktorý sa z času na čas stáva nákladným, keď sa násobia veľké matice. Ponúka priestorovú zložitosť O (nm)
, ktorý sa vyslovuje „Big Oh of n*m, "na uloženie ďalšej matice z n riadky podľa m stĺpce. Toto sa stáva O (n2)
pre štvorcové matice.
Vytvoril som MatMult
Aplikácia Java, ktorá vám umožní experimentovať s Matrix Multiplication. Výpis 1 predstavuje zdrojový kód tejto aplikácie.
Zoznam 1. Aplikácia Java na experimentovanie s Matrix Multiplication (MatMult.java)
public final class MatMult {public static void main (String [] args) {int [] [] a = {{10, 30}, {20, 40}}; int [] [] b = {{5}, {7}}; skládka (a); System.out.println (); skládka (b); System.out.println (); int [] [] c = vynásobiť (a, b); skládka (c); } výpis súkromného statického voidu (int [] [] x) {if (x == null) {System.err.println ("pole má hodnotu null"); návrat; } // Vypíše hodnoty prvkov matice na štandardný výstup v tabuľkovom // poradí. pre (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 [] [] vynásobiť (int [] [] a, int [] [] b) {// ======================= =============================================== // 1. a.length obsahuje počet riadkov a // // 2. a [0] .length (alebo akýkoľvek iný a [x] .length pre platné x) obsahuje a's // počet stĺpcov // // 3. b.length obsahuje počet riadkov b // // 4. 4. b [0] .length (alebo akýkoľvek iný b [x] .length pre platné x) obsahuje počet b stĺpcov // // ============= ================================================== ====== // Ak je počet stĺpcov a! "); návrat null; } // Priradiť výslednú maticu s veľkosťou rovnou počtu riadkov a počtu krát b // počet stĺpcov int [] [] result = new int [a.length] []; for (int i = 0; i <result.length; i ++) result [i] = new int [b [0] .length]; // Vykonajte násobenie a sčítanie pre (int i = 0; i <a.length; i ++) pre (int j = 0; j <b [0] .length; j ++) pre (int k = 0; k <a [0] .lenght; k ++) // alebo k <b.length výsledok [i] [j] + = a [i] [k] * b [k] [j]; // Vrátiť výslednú maticu return result; }}
MatMult
deklaruje dvojicu matíc a vypíše ich hodnoty na štandardný výstup. Potom znásobí obe matice a vypíše výslednú maticu na štandardný výstup.
Zostavte zoznam 1 takto:
javac MatMult.java
Výslednú aplikáciu spustite nasledujúcim spôsobom:
java MatMult
Mali by ste dodržiavať nasledujúci výstup:
10 30 20 40 5 7 260 380
Príklad násobenia matice
Poďme preskúmať problém, ktorý sa najlepšie vyrieši násobením matíc. V tomto scenári naloží pestovateľ ovocia na Floride niekoľko návesov s 1 250 škatuľkami pomarančov, 400 škatúľ broskýň a 250 škatúľ grapefruitu. Obrázok 4 zobrazuje graf trhovej ceny za krabicu pre každý druh ovocia v štyroch rôznych mestách.
Náš problém je určiť, kam by sa malo ovocie prepravovať a predávať s maximálnym hrubým príjmom. Aby sme tento problém vyriešili, najskôr rekonštruujeme graf z obrázka 4 ako cenovú maticu so štyrmi riadkami a tromi stĺpcami. Z toho môžeme zostaviť trojriadkovú maticu množstva s jedným stĺpcom, ktorá sa zobrazí nižšie:
== == | 1250 | | | | 400 | | | | 250 | == ==
S oboma maticami po ruke jednoducho vynásobíme cenovú maticu maticou množstva, aby sme vytvorili maticu hrubého príjmu:
== == == == | 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 == == == ==
Vyslanie oboch návesov do Los Angeles prinesie najvyšší hrubý príjem. Ale keď sa vezme do úvahy vzdialenosť a náklady na palivo, možno je New York lepšou stávkou na dosiahnutie najvyššieho príjmu.
Členité polia
Po oboznámení sa s dvojrozmernými poľami by vás teraz mohlo zaujímať, či je možné k prvkom poľa riadkov priradiť jednorozmerné stĺpcové polia s rôznymi dĺžkami. Odpoveď je áno. Zvážte tieto príklady:
dvojnásobok [] [] teploty1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; double [] [] teploty2 = nový double [2] []; dvojnásobok [] [] teploty3 = nový dvojnásobok [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3}};
Prvý a tretí príklad vytvárajú dvojrozmerné pole, kde prvý riadok obsahuje tri stĺpce a druhý riadok obsahuje dva stĺpce. Druhý príklad vytvára pole s dvoma riadkami a nešpecifikovaným počtom stĺpcov.
Po vytvorení teplota2
riadkové pole, jeho prvky musia byť vyplnené odkazmi na nové polia stĺpcov. Nasledujúci príklad demonštruje priradenie 3 stĺpcov k prvému riadku a 2 stĺpce k druhému riadku:
temperature2 [0] = nový dvojitý [3]; temperature2 [1] = nový dvojitý [2];
Výsledné dvojrozmerné pole je známe ako a členité pole. Tu je druhý príklad: