Polia a "poľové" algoritmy

<< "Inicializačné metódy" (konštruktory) | Obsah | Dvojrozmerné polia >>

Doposiaľ vždy, keď sme chceli pracovať s nejakým objektom, musela existovať premenná, ktorá tento objekt referencovala. Problém však vzniká v prípade, že potrebujeme pracovať s veľmi veľa objektami (napr. 100 korytnačiek). Je jasné, že vytvorene 100 premenných referencujúcich objekty triedy Turtle nie je práve ideálne riešenie. Analogicky, ak chceme realizovať nejaký výpočet, hodnoty uchovávame v premenných. Avšak, ak je dát veľa, použitie jednoduchých premenných (či už lokálnych alebo inštančných) neprichádza do úvahy. Riešením vyššie spomenutých problémov sú polia.

Polia sú špeciálne Java objekty, ktoré nám umožňujú uchovať veľa premenných rovnakého typu "pod jednou strechou". Každý "poľový" objekt sa skladá z dopredu určeného počtu políčok. Jednotlivé políčka sú usporiadané za sebou a očíslované. Číslovanie (indexovanie), tak ako to býva v Jave zvykom, začína od čísla 0. Každé políčko funguje ako samostatná premenná, t.j. uchováva hodnotu alebo referenciu v závislosti od typu políčok poľa.

Deklarácia premennej referencujúcej pole. Keďže polia sú objekty, na to, aby sme s nimi mohli aktívne pracovať, potrebujeme premennú referenčného typu, ktorá by referencovala "poľové" objekty. Premennú, ktorá referencuje polia ("poľové objekty") s políčkami typy Typ, deklarujeme takto:

Typ[] premennaReferencujucaPole;

Za Typ môžeme dosadiť ľubovoľný doposiaľ používaný typ premennej:

Turtle[] poleReferenciiNaKorytnacky;

String[] poleReferenciiNaRetazce;

int[] poleCisel;

Vo vyššie uvedenom príklade premenná poleReferenciiNaKorytnacky je premennou referenčného typu, ktorá je schopná referencovať polia ("poľové" objekty), ktorých políčka sú typu Turtle - to jest, každé políčko referencovaného poľa uchováva referenciu ("rodné číslo") na nejaký objekt triedy Turtle. Premenná poleCisel v tomto príklade je schopná referencovať pole ("poľový" objekt), ktorého každé políčko uchováva nejaké celé číslo (hodnotu typu int).

Vytvorenie poľa. Povedzme si ešte, ako pole ("poľový" objekt) vytvoríme. Ak chceme vytvoriť pole, ktoré bude mať n políčok typu TypPolicka, tak použijeme príkaz:

new TypPolicka[n];

V nasledujúcom príklade sa najprv vytvorí premenná korytnacky, ktorá je schopná referencovať polia s políčkami typu Turtle. Následne sa príkazom new vytvorí pole ("poľový" objekt), ktorý bude mať 10 políčok. Každé z týchto políčok bude schopné uchovávať referenciu na nejaký objekt triedy Turtle. Nakoniec sa referencia na vytvorené pole (objekt) uloží do premennej korytnacky:

Turtle[] korytnacky = new Turtle[10];

Políčka vytvoreného poľa fungujú ako klasické premenné. Aký je teda ich obsah po vytvorení poľa ? Pamätajme si, že políčka poľa sú automaticky inicializované "defaultnými" hodnotami (v závislosti od typu políčok), presne tak, ako je to u inštančných (objektových) premenných. V predchádzajúcom príklade budú políčka vytvoreného poľa inicializované hodnotami null, keďže typ Turtle je referenčným typom (políčka poľa sú referenčného typu).

Prístup k políčkam (prvkom) poľa. Po vytvorení poľa chceme prirodzenie s políčkami poľa pracovať. Na prístup ku konkrétnemu políčku poľa používame hranaté zátvorky [], medzi ktoré pridáme index políčka (jeho poradové číslo):

// Vytvoríme pole na 10 referencií na korytnačie objekty

Turtle[] korytnacky = new Turtle[10];

// Klasická referenčná premenná referencujúca jeden objekt korytnačky

Turtle korytnacka = new Turtle();

// Vyrobíme jednu korytnačku a necháme ju referencovať políčkom poľa na indexe 0

korytnacky[0] = new Turtle();

// Políčko na indexe 6 (siedme políčko poľa) necháme referencovať tú korytnačku,

// ktorá je referencovaná z premennej korytnacka

korytnacky[6] = korytnacka;

// Políčko na indexe 3 (4. políčko) referencuje tú korytnačku, 

// ktorú referencovalo políčko s indexom 0 (1. políčko)

korytnacky[3] = korytnacky[0]

// Povieme korytnačke, ktorá je referencovaná z políčka na indexe 3, aby vykonala metódu step

korytnacky[3].step(10);

Medzi [] môžeme napísať nielen konkrétnu hodnotu (celočíselný literál), ale aj ľubovoľný aritmetický výraz, ktorého výsledkom je celé číslo. Toto číslo sa použije ako index na prístup ku konkrétnemu políčku poľa. Keďže polia sú objekty, uvedomme si, že zápis korytnacky[3] v skutočnosti znamená: políčko na indexe 3 (4. políčko) poľa referencovaného z premennej korytnacky. (Pre lepšiu ilustráciu viď slidy k prednáške.)

Ilustračný obrázok podľa http://java.sun.com/docs/books/tutorial/java/nutsandbolts/arrays.html

Počet prvkov (políčok) poľa. Spomeňme si, že v prípade reťazcov (objektov triedy String) sme vedeli počet znakov v reťazci zistiť pomocou metódy length(). V prípade polí, ale niečo také nefunguje. Namiesto volania metódy nám Java ponúka špeciálnu konštrukciu .length (pozor, nie je to metóda a preto žiadne okrúhle zátvorky), pomocou ktorej vieme zistiť počet prvkov poľa.

Nasledujúci príklad spočíta, v koľkých políčkach je uložená hodnota null:

Turtle[] korytnacky = ...;

int pocetNullov = 0;

for (int i=0; i<korytnacky.length; i++)

        if (korytnacky[i] == null)

                pocetNullov++;

Pamätajme si tiež, že počet políčok poľa (hovoríme aj dĺžku poľa) po jeho vytvorení už nemôžeme zmeniť.

Pole po vytvorení: Po vytvorení poľa je v políčkach poľa uložená tzv. "defaultná" hodnota podľa typu políčok poľa. Pamätajme, že ak typom políčok poľa je referenčný typ, tak po vytvorení poľa je v každom políčku hodnota null. Inými slovami, žiadne políčko neobsahuje ako svoju hodnotu "rodné číslo" objektu. Ak chceme mať v poli referencie na konkrétne objekty, musíme ich najprv vytvoriť resp. referencie na ne odniekiaľ získať. To je zrejmé, pretože ak je políčko poľa referenčného typu, obsahuje len referenciu ("rodné číslo") na nejaký objekt. Ak však je políčko poľa primitívneho typu (int, double, ...) obsahuje políčko poľa priamo hodnotu. "Defaultné" hodnoty pre tieto typy možno nájsť v prechádzajúcej prednáške. Pripomeňme, že po vytvorení poľa (cez new) sú v tomto prípade jednotlivé políčka poľa vyplnené touto "defaultnou" hodnotou.

Fragment programu zachycujúci prácu s poľom - vytvorenie a naplnenie poľa celých čísel:

int[] poleIntov = new int[100];

for (int i=0; i<poleIntov.length; i++)

        poleIntov[i] = 10 + 5 * i;

Inicializácia polí

V niektorých situáciach by sa celkom hodilo, keby vytvorené pole bolo rovno aj inicializované nejakými (pre naše potreby) rozumnými hodnotami (nie "defaultnými"). Java samozrejme aj na tento problém ponúka riešenie:

int[] cisla = {3, 4, 1, 5, 4, 8};

Tento zápis je totožný s týmito riadkami zdrojového kódu:

int[] cisla = new int[6];

cisla[0] = 3;

cisla[1] = 4;

cisla[2] = 1;

cisla[3] = 5;

cisla[4] = 4;

cisla[5] = 8;

Ako môžeme vidieť, vytvorenie pola a nastavenie hodnôt pre políčka môžeme skombinovať do jedného príkazu. Za znak = pridáme do kučeravých zátvoriek {} čiarkami oddelenú postupnosť hodnôt pre jednotlivé políčka. Navyše v tomto zozname hodnôt okrem literálov môžeme uviesť aj (aritmetické alebo logické) výrazy.

Príklady:

char[] znaky = {'a', 'r', 'x', 't', 'a'};

String[] retazce = {"Ahoj", "Java", "PAZ1a"};

int x = 1;

int[] cisla = {x, x+1, x+2};

Užitočné metódy na prácu s (jednorozmerným) poľom

Keďže práca s poľami je pri programovaní dosť častá, Java má už mnoho užitočných metód naprogramovaných (sú jej súčasťou).

Ak chceme vypísať obsah poľa zvyčajne použijeme for-cyklus, v ktorom vypíšeme prvky poľa "po jednom". Pomocou metódy Arrays.toString vieme nechať si vyrobiť reťazec, ktorý bude obsahovať čiarkami oddelený zoznam hodnôt v poli.

Príklad:

int[] pole = ...;

String s = Arrays.toString(pole);

System.out.println(s);

// alebo skrátene

System.out.println(Arrays.toString(pole));

Ďalšou častou činnosťou je kopírovanie obsahu políčok z jedného poľa do druhého poľa. Tu nám vie pomôcť metóda System.arraycopy. Táto metóda má 5 parametrov, v poradí:

referencia na pole, ktorého obsah políčok ideme kopírovať
index v poli, od ktorého ideme obsah políčok kopírovať
referencia na pole, do ktorého ideme obsah políčok kopírovať
index v poli, od ktorého ideme kopírované prvky ukladať
počet kopírovaných prvkov

Pozrime sa na túto metódu v príklade:

int[] p1 = {1, 2, 3, 4, 5, 6}

int[] p2 = new int[5];

System.arraycopy(p1, 3, p2, 1, 2);

// po skončení bude v p2 obsah: {0, 4, 5, 0, 0}

Rôzne metódy (algoritmy) pracujúce s poľom sa môžu zdať na prvý pohľad veľmi zložité. V skutočnosti ide len o obmeny niekoľkých stratégii.

Zistenie, či všetky prvky poľa majú nejakú vlastnosť

Typickým problémom, ktorý sa často rieši, je overenie toho, či všetky prvky poľa (hodnoty alebo objekty referencované z políčok poľa) majú nejakú vlastnosť. Príkladmi vlastností môžu byť tieto:

hodnota prvku je väčšia ako 100
hodnota predchádzajúceho prvku v poli je menšia alebo rovná ako hodnota daného prvku
referencovaná korytnačka je vo vzdialenosti menej ako 50 od nejakého význačného bodu
hodnota na aktuálnom políčku sa ešte ani raz nevyskytla v políčkach s menším indexom ("naľavo")

Základná stratégia na riešenie tohto problému je táto:

na začiatku veríme, že všetky prvky majú skúmanú vlastnosť ("sú dobré")
prechádzame všetky prvky poľa
- ak aktuálne políčko poľa nemá skúmanú vlastnosť ("je zlé"), tak vieme dať ihneď odpoveď, že nie je pravdou to, že všetky políčka poľa majú skúmanú vlasnosť. V tomto prípade poznáme odpoveď a teda nemá zmysel skúmať ďalšie prvky poľa
ak sme prešli všetky prvky poľa a nenašli sme "zlý" prvok, tak vieme, že všetky prvky "sú dobré" a teda majú skúmanú vlastnosť

Túto stratégiu v Jave vieme vyjadriť nasledujúcim "pseudokódom". V ňom predpokladáme, že maVlastnost je niečo, čo nám povie, či políčko poľa má alebo nemá (boolean) skúmanú vlastnosť:

boolean vsetkyOK = true;

for (int i=0; i<pole.length; i++)

        if (!maVlastnost(pole[i])) {

                vsetkyOK = false;

                break; // nemusí byť, ale je to trochu časovo efektívnejšie

        }

// po skončení cyklu máme v premennej vsetkyOK informáciu, či všetky prvky poľa majú skúmanú vlastnosť

V prípade, že zisťovanie robíme v samostatnej metóde, môžeme použiť tento variant:

public boolean test(...) {

        for (int i=0; i<pole.length; i++)

                if (!maVlastnost(pole[i])) 

                        return false;

        return true;

}

Pozrime sa, ako by vyzerala aplikovanie tejto stratégie v prípade, že chceme zistiť či všetky prvky majú hodnotu väčšiu alebo rovnú ako zadaná dolná hraničná hodnota hranica:

public boolean vsetkyVacsieAko(int[] pole, int hranica) {

        for (int i=0; i<pole.length; i++)

                if (pole[i] < hranica) 

                        return false;

        return true; 

}

Túto stratégiu vieme použiť dokonca aj v prípade, keď nás nezaujíma, či všetky prvky poľa majú nejakú vlastnosť, ale či všetky neusporiadané dvojice (alebo aj k-tice) rôznych prvkov majú nejakú vlastnosť:

public boolean test(...) {

        // pre dvojice

        for (int i=0; i<pole.length; i++)

               for (int j=i+1; j<pole.length; j++)

                       if (!maVlastnost(pole[i], pole[j])) 

                               return false;

        return true;

}

Samozrejme, ak by to nebolo v samostatnej metóde, použijeme variant s break-om a boolean premennou.

Počet prvkov poľa s nejakou vlastnosťou

Problém zistenia počtu prvkov poľa s nejakou vlastnosťou je veľmi podobný predchádzajúcemu problému. Na riešenie tohto problému využívame podobnú stratégiu. Namiesto boolean premennej použijeme počítadlo, v ktorom si budeme počítať, koľko prvkov so skúmanou vlastnosťou sme stretli pri prechode prvkami poľa. Pozrime sa na "schému" riešiacu tento problém:

int pocitadlo = 0;

for (int i=0; i<pole.length; i++)

        if (maVlastnost(pole[i]))

            pocitadlo++;

// po skončení cyklu máme v premennej pocitadlo informáciu, koľko prvkov poľa má skúmanú vlastnosť

Pozrime sa na príklad metódy, ktorá spočíta, koľko korytnačiek je bližšie k zadanému bodu ako 100:

private Turtle[] korytnacky = ...;

public int pocetBlizkychKorytnaciek(double x, double y) {

        int pocitadlo = 0;

        for (int i=0; i<this.korytnacky.length; i++)

                if (this.korytnacky[i].distanceTo(x, y) <= 100)

                        pocitadlo++;

        return pocitadlo;

}

Analogicky tento mechanizmus vieme použiť aj na spočítanie počtu dvojíc (k-tíc), ktoré majú nejakú vlastnosť.

Naj prvok poľa

Ďalším častým riešeným problémom je nájdenie "naj" prvku poľa, resp. zistenie jeho hodnoty. Pod pojmom "naj" prvok poľa myslíme taký prvok poľa, ktorý je spomedzi všetkých prvkov poľa nejakým spôsobom najlepší. Pár príkladov najlepšieho prvku poľa:

prvok s najmenšou hodnotou (minimálny prvok v poli)
prvok s najväčšou hodnotou (maximálny prvok v poli)
prvok s najčastejšie sa opakujúcou hodnotou (najčastejšia hodnota v poli)
korytnačka, ktorá má najmenšiu x-ovú súradnicu (najľavejšia korytnačka)
korytnačka, ktorá je najbližsie (najďalej) k nejakému bodu

Základná stratégia na riešenie tohto problému je táto (metafora: zápas):

v každom okamihu si pamätáme doposiaľ najlepší nájdený prvok (kandidáta na celkovo najlepší prvok)
na začiatku si ako doposiaľ najlepší nájdený prvok vyberieme prvý prvok poľa
postupne prechádzame všetky prvky poľa (metafora: doposiaľ nájdený najlepší prvok vyzýva všetky ostatné prvky poľa, ktoré ešte nebojovali v žiadnom "zápase")
- v každom kroku porovnávame kvalitu doposiaľ nájdeného najlepšieho prvku s kvalitou aktuálneho prvku
  - ak je aktuálny prvok lepší, tak od tohto momentu bude on tým doposiaľ nájdeným najlepším prvkom (metafora: aktuálny držiteľ titulu prehral a titul získava ten, kto ho porazil)
prvok, ktorý je na konci prechodu všetkými prvkami vybraný ako doposiaľ nájdený najlepší prvok je aj celkovo najlepší prvok

V nasledujúcom predpokladajme, že jeLepsiAko(A, B) nám povie, či A je lepší ako B (A > B). Algoritmus na nájdenie najlepšieho prvku poľa môžeme v Jave vyjadriť takto:

// v idxNaj si budeme pamätať index doposiaľ najlepšieho nájdeného prvku poľa

int idxNaj = 0;

for (int i=1; i<pole.length; i++) 

        if (jeLepsiAko(pole[i], pole[idxNaj]))

                idxNaj = i;

// po skončení máme v idxNaj index najlepšieho prvku poľa

Ilustrujme si túto schému na probléme nájdenia najväčšej hodnoty v poli:

public double maximalnaHodnota(double[] pole) {

        int idxNaj = 0;

        for (int i=1; i<pole.length; i++)

                if (pole[i] > pole[idxNaj])

                        idxNaj = i;

        return pole[idxNaj];

}

Ilustrujme si tento mechanizmus ešte na nájdení korytnačky, ktorá má najmenšiu y-vú súradnicu:

private Turtle[] korytnacky = ...;

public Turtle najvyssiaKorytnacka() {

        int idxNaj = 0;

        for (int i=1; i<this.korytnacky.length; i++)

                if (this.korytnacky[i].getY() < this.korytnacky[idxNaj].getY())

                        idxNaj = i;

        return this.korytnacky[idxNaj];

}

Rovnako ako všetky skôr spomenuté "finty", aj táto úspešne funguje v prípade, kedy chceme nájsť nejakú najlepšiu dvojicu (alebo k-ticu) rôznych prvkov.

int idxNaj1 = 0;

int idxNaj2 = 1;

for (int i=0; i<pole.length; i++)

        for (int j=i+1; j<pole.length; j++)

                if (kvalita(i, j) > kvalita(idxNaj1, idxNaj2)) {

                       idxNaj1 = i;

                       idxNaj2 = j; 

                }

<< "Inicializačné metódy" (konštruktory) | Obsah | Dvojrozmerné polia >>