Programovanie

Dátové štruktúry a algoritmy v Jave, časť 3: Multidimenzionálne polia

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é ints, 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í teplota2riadkové 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:

$config[zx-auto] not found$config[zx-overlay] not found