Datové struktury a algoritmy v Javě, část 2, představily řadu technik pro vyhledávání a třídění jednorozměrných polí, což jsou nejjednodušší pole. V tomto kurzu prozkoumáte vícerozměrná pole. Ukážu vám tři způsoby, jak vytvořit vícerozměrná pole, poté se naučíte, jak používat algoritmus Matrix Multiplication k množení prvků v dvourozměrném poli. Také představím otrhaná pole a dozvíte se, proč jsou populární pro aplikace s velkými daty. Nakonec zvážíme otázku, zda pole je nebo není objekt Java.
Tento článek vás seznámí s částí 4, která zavádí vyhledávání a třídění pomocí jednotlivě propojených seznamů.
Vícedimenzionální pole
A vícerozměrné pole přidruží každý prvek v poli k více indexům. Nejběžněji používaným vícerozměrným polem je dvourozměrné pole, také známý jako a stůl nebo matice. Dvourozměrné pole přidruží každý ze svých prvků ke dvěma indexům.
Můžeme konceptualizovat dvourozměrné pole jako obdélníkovou mřížku prvků rozdělených do řádků a sloupců. Používáme (řádek sloupec) zápis k identifikaci prvku, jak je znázorněno na obrázku 1.
Protože jsou dvourozměrná pole tak běžně používána, zaměřím se na ně. To, co se dozvíte o dvourozměrných polích, lze zobecnit na ty vyšší.
Vytváření dvourozměrných polí
Existují tři techniky pro vytvoření dvourozměrného pole v Javě:
- Pomocí inicializátoru
- Pomocí klíčového slova
Nový - Pomocí klíčového slova
Novýs inicializátorem
Použití inicializátoru k vytvoření dvourozměrného pole
Přístup pouze k inicializaci k vytvoření dvourozměrného pole má následující syntaxi:
'{' [rowInitializer (',' rowInitializer)*] '}'rowInitializer má následující syntaxi:
'{' [expr (',' expr)*] '}'Tato syntaxe uvádí, že dvourozměrné pole je volitelný seznam inicializátorů řádků oddělených čárkami, které se objevují mezi znaky otevřené a zavřené závorky. Kromě toho je každý inicializátor řádků volitelným seznamem výrazů oddělených čárkami, které se objevují mezi znaky otevřené a zavřené závorky. Stejně jako jednorozměrná pole musí být všechny výrazy vyhodnoceny na kompatibilní typy.
Zde je příklad dvourozměrného pole:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }Tento příklad vytvoří tabulku se dvěma řádky a třemi sloupci. Obrázek 2 představuje koncepční pohled na tuto tabulku spolu se zobrazením paměti, které ukazuje, jak Java vyloží tuto (a všechny) tabulky v paměti.
Obrázek 2 ukazuje, že Java představuje dvourozměrné pole jako jednorozměrné pole řádků, jehož prvky odkazují na jednorozměrná pole sloupců. Index řádků identifikuje pole sloupců; index sloupce identifikuje datovou položku.
Vytvoření pouze nového klíčového slova
Klíčové slovo Nový přidělí paměť pro dvourozměrné pole a vrátí jeho odkaz. Tento přístup má následující syntaxi:
'Nový' typ '[' int_expr1 ']' '['int_expr2 ']'Tato syntaxe uvádí, že dvourozměrné pole je oblast (pozitivní) int_expr1 řádkové prvky a (kladné) int_expr2 prvky sloupců, které sdílejí všechny stejné typ. Kromě toho jsou všechny prvky vynulovány. Zde je příklad:
nový double [2] [3] // Vytvořte tabulku dvou řádků po třech sloupcích.Vytvoření nového klíčového slova a inicializátoru
Klíčové slovo Nový s přístupem inicializátoru má následující syntaxi:
'Nový' typ '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'kde rowInitializer má následující syntaxi:
'{' [expr (',' expr)*] '}'Tato syntaxe spojuje předchozí dva příklady. Protože počet prvků lze určit ze seznamů výrazů oddělených čárkami, neposkytujete int_expr mezi dvojicí hranatých závorek. Zde je příklad:
nový double [] [] {{20.5, 30.6, 28.3}, {-38,7, -18,3, -16,2}}Dvourozměrná pole a proměnné pole
Samo o sobě je nově vytvořené dvourozměrné pole zbytečné. Jeho odkaz musí být přiřazen k proměnná pole kompatibilního typu, buď přímo, nebo prostřednictvím volání metody. Následující syntaxe ukazují, jak byste deklarovali tuto proměnnou:
typvar_name '[' ']' '[' ']' typ '[' ']' '[' ']' var_nameKaždá syntaxe deklaruje proměnnou pole, která ukládá odkaz na dvourozměrné pole. Upřednostňuje se umístit hranaté závorky za typ. Zvažte následující příklady:
double [] [] teploty1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; double [] [] temperature2 = nový double [2] [3]; double [] [] teploty3 = nový double [] [] {{20.5, 30.6, 28.3}, {-38,7, -18,3, -16,2}};Stejně jako proměnné jednorozměrného pole je proměnná dvourozměrného pole spojena s a .délka vlastnost, která vrací délku řady řádků. Například, teploty 1. délka vrací 2. Každý prvek řádku je také proměnnou pole s a .délka vlastnost, která vrací počet sloupců pro pole sloupců přiřazené k prvku řádku. Například, teploty1 [0] .délka vrátí 3.
Vzhledem k proměnné pole můžete přistupovat k jakémukoli prvku v dvourozměrném poli zadáním výrazu, který souhlasí s následující syntaxí:
pole_var '[' řádek_index ']' '[' col_index ']'Oba indexy jsou kladné ints, které se pohybují od 0 do jedné menší než hodnota vrácená z příslušných .délka vlastnosti. Zvažte další dva příklady:
dvojnásobná teplota = teploty1 [0] [1]; // Získejte hodnotu. teploty1 [0] [1] = 75,0; // Nastavit hodnotu.První příklad vrací hodnotu ve druhém sloupci prvního řádku (30.6). Druhý příklad nahradí tuto hodnotu 75.0.
Pokud zadáte záporný index nebo index, který je větší nebo roven hodnotě vrácené proměnnou pole .délka vlastnost, Java vytvoří a hodí ArrayIndexOutOfBoundsException objekt.
Násobení dvourozměrných polí
Násobení jedné matice jinou maticí je běžná operace v oblastech od počítačové grafiky, přes ekonomiku až po dopravní průmysl. Vývojáři pro tuto operaci obvykle používají algoritmus Matrix Multiplication.
Jak funguje násobení matic? Nechť A představuje matici s m řádky a p sloupce. Podobně nechť B představuje matici s p řádky a n sloupce. Vynásobte A číslem B a vytvořte matici C s m řádky a n sloupce. Každý cij položka v C se získá vynásobením všech položek v A i řádek odpovídajícími položkami v B. jth sloupec a poté přidejte výsledky. Obrázek 3 ilustruje tyto operace.
Sloupce levé matice se musí rovnat řádkům pravé matice
Násobení matic vyžaduje, aby se počet sloupců (p) v levé matici (A) rovnal počtu řádků (p) v pravé matici (B). Jinak tento algoritmus nebude fungovat.
Následující pseudokód vyjadřuje Matrix Multiplication v kontextu 2-řádků po 2 sloupcích a 2 řádků po 1 sloupcích. (Připomeňme, že jsem v části 1 zavedl pseudokód.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == DECLARE INTEGER a [] [] = [10, 30] [20, 40] DECLARE INTEGER b [] [] = [5, 7] DECLARE INTEGER m = 2 // Počet řádků v levé matici (a) DECLARE INTEGER p = 2 // Počet sloupců v levé matici (a) // Počet řádků v pravé matici (b) DECLARE INTEGER n = 1 // Počet sloupců v pravé matice (b) DECLARE INTEGER c [m] [n] // c obsahuje 2 řádky po 1 sloupci // Všechny prvky se 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] DALŠÍ k DALŠÍ j DALŠÍ i KONECKvůli těm třem PRO smyčky, Matrix Multiplication má časovou složitost Ó(n3), který se vyslovuje „Big Oh of n krychle. "Maticové násobení nabízí kubický výkon, který je časově nákladný, když se násobí velké matice. Nabízí prostorovou složitost Ó(nm), který se vyslovuje „Big Oh of n*m, "pro uložení další matice n řádky podle m sloupce. Toto se stává Ó(n2) pro čtvercové matice.
Vytvořil jsem MatMult Java aplikace, která vám umožní experimentovat s Matrix Multiplication. Výpis 1 představuje zdrojový kód této aplikace.
Výpis 1. Java aplikace pro experimentování 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}}; výpis (a); System.out.println (); skládka (b); System.out.println (); int [] [] c = násobení (a, b); výpis (c); } výpis soukromé statické void (int [] [] x) {if (x == null) {System.err.println ("pole je null"); vrátit se; } // Vypíše hodnoty prvků matice na standardní výstup v tabulkovém // pořadí. 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 (); }} soukromý statický int [] [] násobit (int [] [] a, int [] [] b) {// ======================= =============================================== // 1. a.length obsahuje počet řádků a // // 2. a [0] .length (nebo jakýkoli jiný a [x] .length pro platné x) obsahuje a's // počet sloupců // // 3. b.length obsahuje počet řádků b // // 4. b [0] .length (nebo jakýkoli jiný b [x] .length pro platné x) obsahuje počet b sloupců // // ============= ================================================== ====== // Pokud je počet sloupců a!! = Počet řádků b, zachraňte záchranu if (a [0] .length! = B.length) {System.err.println („Počet sloupců a! "); vrátit null; } // Přiřaďte výslednou matici s velikostí rovnou počtu řádků a počet krát b // počet sloupců int [] [] result = new int [a.length] []; for (int i = 0; i <result.length; i ++) result [i] = new int [b [0] .length]; // Proveďte násobení a sčítání pro (int i = 0; i <a.length; i ++) pro (int j = 0; j <b [0] .length; j ++) pro (int k = 0; k <a [0] .length; k ++) // nebo k <b.length výsledek [i] [j] + = a [i] [k] * b [k] [j]; // Vrátit výslednou matici vrátit výsledek; }}MatMult deklaruje dvojici matic a vypíše jejich hodnoty na standardní výstup. Poté znásobí obě matice a vypíše výslednou matici na standardní výstup.
Kompilace výpisu 1 následovně:
javac MatMult.javaVýslednou aplikaci spusťte následovně:
java MatMultMěli byste dodržovat následující výstup:
10 30 20 40 5 7 260 380Příklad násobení matic
Prozkoumejme problém, který se nejlépe vyřeší násobením matic. V tomto scénáři naloží pěstitel ovoce na Floridě několik návěsů s 1250 krabicemi pomerančů, 400 krabic broskví a 250 krabic grapefruitu. Obrázek 4 ukazuje graf tržní ceny za krabici pro každý druh ovoce ve čtyřech různých městech.
Naším problémem je určit, kam by mělo být ovoce odesláno a prodáno pro maximální hrubý příjem. Abychom tento problém vyřešili, nejprve rekonstruujeme graf z obrázku 4 jako cenovou matici se čtyřmi řádky a třemi sloupci. Z toho můžeme sestrojit třířadou matici s jedním sloupcem kvantity, která se objeví níže:
== == | 1250 | | | | 400 | | | | 250 | == ==S oběma maticemi po ruce jednoduše vynásobíme cenovou matici kvantitativní maticí, abychom vytvořili matici hrubého pří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 == == == ==Odeslání obou návěsů do Los Angeles přinese nejvyšší hrubý příjem. Ale když vezmeme v úvahu vzdálenost a náklady na pohonné hmoty, možná je New York lepší sázka na získání nejvyššího příjmu.
Členité pole
Když jste se dozvěděli o dvourozměrných polích, možná vás zajímá, zda je možné přiřadit jednorozměrná sloupcová pole s různými délkami prvkům řady řádků. Odpověď je ano. Zvažte tyto příklady:
double [] [] teploty1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; double [] [] temperature2 = nový double [2] []; double [] [] teploty3 = nový double [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3}};První a třetí příklad vytvoří dvourozměrné pole, kde první řádek obsahuje tři sloupce a druhý řádek obsahuje dva sloupce. Druhý příklad vytvoří pole se dvěma řádky a neurčeným počtem sloupců.
Po vytvoření teplota2řádkové pole, jeho prvky musí být vyplněny odkazy na nová pole sloupců. Následující příklad ukazuje, přiřazení 3 sloupců k první řadě a 2 sloupce k druhé řadě:
temperature2 [0] = nový dvojitý [3]; temperature2 [1] = nový dvojitý [2];Výsledné dvourozměrné pole je známé jako členité pole. Zde je druhý příklad:
