11. praktikum. Kogumid (Collections)

Teemad

Geneerilised liidesed ja klassid, List, Map, Stack, Comparable

Pärast selle praktikumi läbimist oskab üliõpilane kasutada geneerilisi tüüpe ja põhilisi andmestruktuure.

Kogumid

Kogumid on andmestruktuurid, mis on mõeldud mingi hulga objektide hoidmiseks. Erinevus "tavalistest" objektidest (nt. Auto, mille sees on Mootor) on selles, et kogumis sisalduvate objektide arv ei pea olema fikseeritud. Inglise keeles kasutatakse kogumite kohta erinevaid nimetusi: Collection, Aggregate, Container.  

On olemas erinevat liiki kogumeid, nt. massiiv (array), list (list), hulk (set), magasin (stack), kujutus (map), järjekord (queue). (Terminoloogia ei ole siin väga üheselt paigas. Erinevates käsitlustes võib leida erinevaid termineid samade asjade kohta (nt. Tallinnas öeldakse magasini asemel pinu.) Samuti võib sama termini kasutamises olla väiksemaid erinevusi.) Erinevat liiki kogumitel on ühiseid omadusi, aga on ka erinevusi, mistõttu erinevates situatsioonides kasutatakse erinevat liiki kogumeid. Erinevused võivad olla väga erinevates asjades: korduvate elementide lubamine, elementide muudetavus, elementide arvu muudetavus, lisamise, eemaldamise eripärad ...

Käesolev praktikum keskendub Java võimalustele kogumitega seotult. Kuna tegemist on väga mitmetahulise temaatikaga, siis paraku saab siin vaid teatud osa käsitleda. Mitmed andmestruktuurid on Javas kasutusel olnud juba esimestest versioonides peale. Viimastes versioonides on püütud kogumeid süstemaatiliselt käsitleda ja asjassepuutuv koondada ühte raamistikku - Java Collections Framework. Hea ülevaade on Java veebilehestikus. 

Java Collections Framework on ülesehitatud liidestest, klassidest (ka abstraktsetest). Liidestes määratakse teatud kogumiliigi (nt. list või järjekord) jaoks vajalikud meetodid, mis siis konkreetsetes klassides realiseeritakse. Liidestes Collection ja Map on universaalsemad meetodid, alamliidestes tuuakse juurde spetsiifilisemad. Põhiliideste hierarhia on toodud joonisel. (Tegelikult on liideseid märksa rohkem.)

Two interface trees, one starting with Collection and including Set, SortedSet, List, and Queue, and the other starting with Map and including SortedMap.

Geneerilised tüübid

Kogumeid läheb vaja erinevat tüüpi objektide hoidmiseks. Põhimõtteliselt võiks neid kõiki käsitleda Object-tüüpi elementidena. Tavaliselt on siiski kogumis teatud tüüpi elemendid ja kasulik on võimalikult vara (näiteks kompileerimise ajal) teada saada, kui sinna midagi muud püütakse panna. Siin oleks abiks see, kui saaks määrata, millisele tüübile antud kogum mõeldud on. Seda ideed viivadki ellu geneerilised liidesed ja klassid, kus tüübimuutuja(te) abil saame vajalikud määramised teha. Näiteks List<Integer> on mõeldud täisarvudele ja List<String> sõnedele.

Geneerilised tüübid (e geneerikud) on Javas alates versioonist 1.5 (väljalase aastal 2004). Nii kohtab ka koodi, kus kogumi tüüpi (nt. List) on kasutatud ilma täpsustava tüübiparameetrita. Taolisi tüüpe nimetatakse tooreteks (raw). Nende kasutamise korral on programmeerija ülesanne pidada meeles, mis tüüpi objektid kogumis on, Java arvates on sel juhul elementide tüüp Object.

Hea ülevaade geneerikutest on Java veebilehestikus.


Massiiv

Massiiv on mõnes mõttes kõige olulisem kogumitüüp - paljud teised kogumid on realiseeritud kasutades massiivi. Massiivi kasutamine on mugav juhul, kui elementide arv on massiivi loomisel teada ja see ei muutu. Kuna massiivi elemendid hoitakse arvuti mälus järjest, siis massiivi suurendamiseks on tarvis leida uus ja suurem vaba mälukoht ning vana massiivi elemendid sinna "ümber kolida".

Käesolevas praktikumis me otseselt massiiviga ei tegele, oleme ju seda varem teinud.

List (ArrayList, LinkedList)

Listis on elemendid teatud järjestuses. Põhilise erinevusena massiivist saab listi pikkust programmi töö käigus vabalt muuta, elemente saab erinevatesse kohtadesse lisada ja neid eemaldada. Listile omased operatsioonid on määratud liideses java.util.List. Konkreetse listi loomisel tuleb kasutada mõnd klassi, mis selle liidese realiseerib (nt. ArrayList, LinkedList).

Näide: 

import java.util.List;
import java.util.ArrayList;
...
List<Integer> list = new ArrayList<Integer>();

Põhilised toimingud, mida saab listiga teha:

NB! erinevalt massiividest, ei saa listid (ega ka teised allpoolmainitud andmestruktuurid) sisaldada Java algtüüpi elemente (nt. int, boolean, char), nende asemel tuleb kasutada vastavaid mähisklasse (nt. Integer, Boolean, Character).

Näide - listi koostamine

import java.util.List;
import java.util.ArrayList;
...
List<Integer> list1 = new ArrayList<Integer>(); 
list1.add(1); 
list1.add(2);
list1.add(3);

alternatiivsed variandid sama tulemuse jaoks:



import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
...
List<Integer> list2 = new ArrayList<Integer>();
list2.addAll(Arrays.asList(1,2,3));
// veel lühem
List<Integer> list3 = Arrays.asList(1,2,3);
// eelnevad read juba vihjasid, et massiivi saab konvertida listiks
Integer[] massiiv = new Integer[3];
massiiv[0] = 1;
massiiv[1] = 2;
massiiv[2] = 3;
List<Integer> list4 = Arrays.asList(massiiv);
// listi konvertimine massiiviks on veidi peenem töö
Integer[] massiiv2 = list4.toArray(new Integer[list4.size()]);
 

Näide - listi ümberpööramine

Järgnev on näide geneerilisest meetodist: 

public static <T> List<T> reverse(List<T> list) { 
    List<T> tulemus = new ArrayList<T>(); 

    for (int i = list.size()-1; i >= 0; i--) {
        tulemus.add(list.get(i));
    } 

    return tulemus; 
}

Alustame selle meetodi signatuuri uurimist vasakult:

Kui kasutame seda meetodit järgmiselt:


List<Integer> intList = Arrays.asList(1,2,3);
System.out.println(reverse(intList));
 

siis T asendatakse meetodis igal pool Integer-iga.

Liidese List realisatsioonid

ArrayList on enamasti kõige efektiivsem viis listide realiseerimiseks - elementide hoidmiseks kasutatakse massiivi.

LinkedList hoiab oma elemente mälus eraldi, kasutades listi kooshoidmiseks viitasid. LinkedList on efektiivne, kui on tarvis tihti lisada andmeid listi etteotsa või keskele (või kui on vaja elemente sealt eemaldada). Samas elemendi võtmine indeksi järgi on aeglasem kui ArrayList-i puhul.


// näide listi keskele elemendi lisamisest
// NB! töötab ka ArrayList-iga
List<Integer> list2 = new LinkedList<Integer>();
list2.addAll(Arrays.asList(1,2,3));
list2.add(2, 54); // '54' saab 3. elemendiks (indeksiga 2)
 

Vector on peaaegu sama kui ArrayList, erinevused tulevad välja mitmelõimeliste programmide puhul. Ühelõimeliste programmide puhul soovitatakse kasutada ArrayListi.

Magasin

Magasin (stack) on listil põhinev andmestruktuur, mille põhimeetoditeks on pop ja push. Meetod push(x) lisab elemendi x listi lõppu (magasini tippu). Meetod pop() eemaldab magasini tipuelemendi (listi viimase elemendi) ja tagastab selle.

Javas on taolise funktsionaalsuse jaoks olemas ka klass Stack, aga soovitatakse kasutada hoopis liidest Deque (, mis on Queue alamliides) ja realisatsioonina klasse ArrayDeque (või LinkedList). Juhime tähelepanu, et LinkedList realiseerib nii liidest List kui ka Deque. Deque on Stack-ist pisut universaalsem - lubab lisada ka listi etteotsa.

Järgnev näitekood prindib "321"


import java.util.Deque;
import java.util.ArrayDeque;
...
Deque<Integer> magasin = new ArrayDeque<Integer>();
magasin.push(1);
magasin.push(2);
magasin.push(3);
System.out.print(magasin.pop());
System.out.print(magasin.pop());
System.out.print(magasin.pop());
 

Viimasena magasini pandud elemendid pääsevad välja kõige esimesena, seetõttu kasutatakse selle andmestruktuuri kohta ka nimetust LIFO (last-in-first-out).

Järjekord (Queue)

Järjekorra (queue) all mõeldakse (enamasti) järjestatud elementide kogumit, kusjuures elemente lisatakse (add või offer) alati järjendi lõppu ja neid eemaldatakse (remove või poll) järjendi algusest. Siit tuleb ka nimetus FIFO (first-in-first-out).


// tegemata tööde nimekiri, liidese realisatsiooniks on seekord LinkedList
Queue<StringBuffer> tegemataTööd = new LinkedList<StringBuffer>();
...
tegemataTööd.add(new StringBuffer("Valmistu kontrolltööks"));
...
System.out.println(tegemataTööd.remove());
 

Java liides Queue on veidi üldisem kui FIFO - realiseeriv klass otsustab, kuhu lisatud element satub. Nt. eelisjärjekorra puhul järjestatakse järjendi elemendid igal lisamisel uuesti.

Liides Comparable

Liidesest Comparable oli juttu ka 6. praktikumis. Sealsetes näidetes kasutati Comparable'it raw-tüübina - st. ei täpsustatud, millist tüüpi objektidega on võrdlemine lubatud. Tulemus oli see, et võrrelda võis kõikide objektidega (tüüp Object).

Alates Java 1.5-st saab seda liidest kasutada ka geneerilisena. Muudetud näide 6. praktikumist oleks järgmine:

class Isik implements Comparable<Isik> {

    private String nimi; // isendiväli isiku nime jaoks
    private double pikkus; // isendiväli isiku pikkuse jaoks

    Isik(String isikuNimi, double isikuPikkus) {
        nimi = isikuNimi;
        pikkus = isikuPikkus;
    }

    double getPikkus() {
        return pikkus;
    }

    public int compareTo(Isik isik) {
        if (this.getPikkus() > isik.getPikkus()) {
            return 1;
        } else if (this.getPikkus() < isik.getPikkus()) {
            return -1;
        } else {
            return 0;
        }
    }

    public String toString() {
        return nimi + " (pikkusega " + pikkus + ") ";
    }

}

Muudatused:

NB! See, et võrrelda saab vaid teiste Isik-utega, on antud juhul vaba valik, tüübiparameetriks võib anda suvalise tüübi (kasvõi Object, sel juhul oleks programmi tähendus sama nagu algsel, raw-tüübiga programmil)

Ülesanne 1

Kujutus (Map)

Kujutus sisaldab endas kaheosalisi kirjeid, mille esimest komponenti nimetatakse võtmeks ja teist väärtuseks. Ühes kujutuses saab sama võtmega olla vaid üks kirje. Kujutust kasutatakse siis, kui mingi identifikaatori järgi on vaja kiiresti leida üles sellele vastav info. Kujutuse (liidese Map) realisatsiooniks on parim valik enamasti HashMap.

Järgnevas näites kasutatakse HashMapi telefoniraamatu imiteerimiseks:


import java.util.Map;
import java.util.HashMap;
...
Map<String, Integer> telefoniraamat = new HashMap<String, Integer>();
telefoniraamat.put("Peeter Peet", 5562356);
telefoniraamat.put("Mari Maasikas", 53438956);
System.out.println("Mari number on " + telefoniraamat.get("Mari Maasikas"));
 

Paneme tähele, et seekord on mängus kaks tüübiparameetrit, üks võtme jaoks (String) ja teine väärtuse jaoks (Integer).

Kui 'get'-iga küsitakse mingit elementi, mida kujutuses ei leidu, siis tagastatakse null.

Kujutuse kohta võidakse öelda veel sõnastik (dictionary on Pythoni vastav andmestruktuur) või paisktabel (hashtable).

Ülesanne 2

Kasutades kujutust, kirjutada programm, mis loeb sisse mingi tekstifaili ning leiab failis olevate sõnade esinemiste arvud ja kuvab need lõpuks ekraanile. 

Iga sõna puhul kontrollida, kas see juba võtmena kujutuses. Kui ei ole, siis lisada koos väärtusega 1. Kui on, siis jätta väärtus meelde ja lisada sõna koos ühe võrra suurema väärtusega. (Juba olemasoleva võtmega kirje lisamisel väärtus asendatakse.) 


Ülesanne 3

Järgnev ülesanne on mõeldud eelkõige magasini ja kujutuse kasutamise harjutamiseks. Avaldise väärtustamise punkt võib tunduda esmapilgul keeruline, aga lahendus on tegelikult üpris lihtne.