Taulukko

ArrayList tarjoaa paljon ohjelmoijan elämää helpottavia valmiita metodeja ja toiminnallisuuksia. Näistä ehkäpä tärkein liittyy arvon lisäämiseen listalle: ohjelmoijan näkökulmasta listan koko ei ole rajoitettu. Todellisuudessa listat ovat olioita siinä missä muutkin oliot, ja listaa -- kuten muitakin olioita -- luodessa sille varataan rajattu tila muistista. Listan metodit ovat toteutettu siten, että rajatun tilan loppuessa metodi varaa suuremman tilan listan käyttöön.

ArrayListin helppokäyttöisyydesta huolimatta ohjelmissa on joskus tarvetta ArrayListin esi-isälle eli taulukolle.

Taulukko on olio, joka sisältää rajatun määrän numeroituja paikkoja arvoille. Taulukon pituus (tai koko) on siinä olevien paikkojen lukumäärä, eli kuinka monta arvoa taulukkoon voi laittaa. Taulukon arvoja kutsutaan taulukon alkioiksi.

Taulukon voi luoda kahdella eri tavalla. Tutustutaan ensin tapaan, jossa taulukon koko määritellään eksplisiittisesti taulukon luonnin yhteydessä. Kolme kokonaislukualkiota sisältävä taulukko-olio määritellään seuraavasti:

int[] luvut = new int[3];

Taulukkotyyppi määritellään hakasuluilla, jotka tulevat taulukon sisältämien alkioiden tyypin jälkeen (alkioidentyyppi[]). Olion luominen tapahtuu new-kutsulla, jota seuraa taulukon alkioiden tyyppi, hakasulut, sekä hakasulkujen sisään taulukon alkioiden lukumäärä.

Taulukon alkioon viittaus ja arvon asetus

Taulukon alkioihin viitataan taulukon indeksien perusteella. Alla olevassa esimerkissä luodaan kolmepaikkainen kokonaislukutaulukko, jonka jälkeen taulukon indekseihin 0 ja 2 asetetaan arvot. Tämän jälkeen arvot tulostetaan.

int[] luvut = new int[3];
luvut[0] = 2;
luvut[2] = 5;

System.out.println(luvut[0]);
System.out.println(luvut[2]);

2
5

Yksittäisen arvon asettaminen taulukon tiettyyn paikkaan tapahtuu siis kuten arvon asetus tavalliseen muuttujaan, mutta taulukkoon asetettaessa kerrotaan indeksi. Indeksi kerrotaan hakasulkeiden sisällä. Huomaat todennäköisesti myös että ArrayListin metodi get käyttäytyy hyvin samalla tavalla kuin taulukon tietystä indeksistä haku. Taulukon kohdalla vain syntaksi, eli merkintätapa, on erilainen.

Indeksi on kokonaisluku, jonka arvo on välillä [0, taulukon pituus - 1]. Esimerkiksi viiden alkion pituisessa taulukossa on indeksit 0, 1, 2, 3, ja 4.

Scanner lukija = new Scanner(System.in);

int[] luvut = new int[5];
luvut[0] = 42;
luvut[1] = 13;
luvut[2] = 12;
luvut[3] = 7;
luvut[4] = 1;

System.out.println("Mistä indeksistä haetaan? ");
int indeksi = Integer.parseInt(lukija.nextLine());

System.out.println(luvut[indeksi]);

1
3
5
7
9

Mitkä indeksit vaihdetaan?
2
4

1
3
9
7
5

1
3
5
7
9

Mitkä indeksit vaihdetaan?
0
1

3
1
5
7
9

Taulukon koko ja läpikäynti

Taulukko-olion koon saa selville taulukko-olioon liittyvän julkisen oliomuuttujan length avulla. Julkiseen oliomuuttujaan pääsee käsiksi kirjoittamalla olion nimi piste muuttujan nimi, eli esimerkiksi taulukko.length. Huomaa, että kyseessä ei ole metodikutsu, eli taulukko.length() ei toimi.

Taulukon alkioiden läpikäynti voidaan toteuttaa while-toistolauseen avulla.

int[] luvut = new int[4];
luvut[0] = 42;
luvut[1] = 13;
luvut[2] = 12;
luvut[3] = 7;

System.out.println("Taulukossa on " + luvut.length + " alkiota.");

int indeksi = 0;
while (indeksi < luvut.length) {
    System.out.println(luvut[indeksi]);
    indeksi++;
}

Taulukossa on 4 alkiota.
42
13
12
7

Yllä olevassa esimerkissä käydään indeksimuuttujan avulla läpi indeksit 0, 1, 2 ja 3, ja tulostetaan taulukon kussakin indeksissä olevan muuttujan arvo. Ensin siis tulostuu luvut[0], sitten luvut[1] jne. Taulukon läpikäynti loppuu kun muuttujan toistolauseen ehtolause indeksi < luvut.length on totta, eli kun indeksimuuttujan arvo on suurempi tai yhtäsuuri kuin taulukon pituus.

Mitä etsitään? 3
Luku 3 löytyy indeksistä 4.

Mitä etsitään? 7
Luku 7 löytyy indeksistä 7.

Mitä etsitään? 22
Lukua 22 ei löydy.

Jos indeksillä osoitetaan taulukon ohi, eli alkioon jota ei ole olemassa, niin saadaan virheilmoitus ArrayIndexOutOfBoundsException. Virhe ArrayIndexOutOfBoundsException kertoo että taulukossa ei ole haluttua indeksiä. Taulukon ohi, eli indeksiin joka on pienempi kuin 0 tai suurempi tai yhtäsuuri kuin taulukon koko ei saa viitata.

Seuraavassa esimerkissä on ohjelma, joka kysyy käyttäjältä lukujen määrän ja joukon lukuja. Tämän jälkeen ohjelma tulostaa luvut uudestaan samassa järjestyksessä. Käyttäjän antamat luvut tallennetaan taulukkoon.

System.out.print("Kuinka monta lukua? ");
int lukuja = Integer.parseInt(lukija.nextLine());

int[] luvut = new int[lukuja];

System.out.println("Anna luvut:");

int indeksi = 0;
while (indeksi < luvut.length) {
    luvut[indeksi] = Integer.parseInt(lukija.nextLine());
    indeksi++;
}


System.out.println("Luvut uudestaan:");

indeksi = 0;
while (indeksi < luvut.length) {
    System.out.println(luvut[indeksi]);
    indeksi++;
}

Eräs ohjelman suorituskerta voisi olla seuraavanlainen:

Kuinka monta lukua? 4
Anna luvut:
4
8
2
1
Luvut uudestaan:
4
8
2
1

Taulukon alkioiden tyyppi

Taulukko-olion esittely tapahtuu kertomalla ensin taulukko-olion sisältämien alkioiden tyyppi, jota seuraa hakasulut (alkiontyyppi[]). Taulukko-olion alkiot voivat siis olla käytännössä minkä tahansa tyyppisiä. Alla muutamia esimerkkejä:

String[] kuukaudet = new String[12];
Henkilo[] ministerit = new Henkilo[14];
double[] approksimaatiot = new double[100];

kuukaudet[0] = "Tammikuu";
ministerit[0] = new Henkilo("Miina Sillanpää");
approksimaatiot[0] = 3.14;

tulosta
1 3 5 7 9
siirra
tulosta
3 5 7 9 1
siirra
siirra
tulosta
7 9 1 3 5
lopeta

Taulukko metodin parametrina

Taulukkoja voidaan käyttää metodin parametrina aivan kuten kaikkia muitakin muuttujia. Koska taulukko on olio -- toisinsanoen viittaustyyppinen muuttuja -- taulukon arvo on viite taulukkoon liittyviin tietoihin. Kun taulukkoa käytetään metodin parametrina, metodin käyttöön kopioidaan viite taulukkoon.

public class Tulostaja {
    public static void listaaAlkiot(int[] kokonaislukuTaulukko) {
        System.out.println("taulukon alkiot ovat: ");

        int indeksi = 0;
        while (indeksi < kokonaislukuTaulukko.length) {
            int luku = kokonaislukuTaulukko[indeksi]
            System.out.print(luku + " ");
            indeksi++;
        }

        System.out.println("");
    }
}

int[] luvut = new int[3];
luvut[0] = 1;
luvut[1] = 2;
luvut[2] = 3;

new Tulostaja().listaaAlkiot(luvut);

1
2
3

Kuten olemme aiemmin jo huomanneet, parametrin nimi metodin sisällä voi olla aivan vapaasti valittu, nimen ei tarvitse missään tapauksessa olla sama kuin kutsuvassa. Edellä taulukkoa kutsutaan metodin sisällä nimellä kokonaislukuTaulukko, metodin kutsuja taas näkee saman taulukon luvut-nimisenä.

public class Main {
    public static void main(String[] args) {
        // Tässä voit testata metodia
        int[] taulukko = {5, 1, 3, 4, 2};
        System.out.println(new Summaaja().laskeTaulukonLukujenSumma(taulukko));
    }
}

15

public class Main {
    public static void main(String[] args) {
        // Tässä voit testata metodia
        int[] taulukko = {5, 1, 3, 4, 2};
        new Tulostin().tulostaTaulukkoTahtina(taulukko);
    }
}

*****
*
***
****
**

public class Main {
    public static void main(String[] args) {
        // Tässä voit testata metodia
        int[] taulukko = {5, 1, 3, 4, 2};
        new TaulukonTulostaja().tulostaTyylikkaasti(taulukko);
    }
}

5, 1, 3, 4, 2

Koska metodin käyttöön kopioidaan viite taulukkoon, kaikki metodissa tapahtuvat taulukon sisältöön vaikuttavat muutokset ovat olemassa myös metodin suorituksen jälkeen.

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // Tässä voit testata metodia
        int[] taulukko = {5, 1, 3, 4, 2};
        System.out.println(Arrays.toString(taulukko));
        new LukujenKasvattaja().kasvata(taulukko, 3);
        System.out.println(Arrays.toString(taulukko));
    }
}

[5, 1, 3, 4, 2]
[8, 4, 6, 7, 5]

Taulukko metodin paluuarvona

Koska metodit voivat palauttaa olioita, voivat ne palauttaa myös taulukkoja. Eräs merkkijonotaulukon palauttava metodi on seuraavannäköinen -- huomaa että taulukkoihin voi aivan hyvin siis laittaa myös olioita.

public class Taulukkotehdas {

    public String[] annaMerkkijonoTaulukko() {
        String[] opet = new String[3];

        opet[0] = "Bonus";
        opet[1] = "Ihq";
        opet[2] = "Lennon";

        return opet;
    }
}

String[] opettajat = new Taulukkotehdas().annaMerkkijonoTaulukko();

int indeksi = 0;
while (indeksi < opettajat.length) {
    System.out.println(opettajat[indeksi]);
    indeksi++;
}

public static void main(String[] args) {
    int[] alkuperainen = {1, 2, 3, 4};
    int[] kopio = new Taulukot().kopioi(alkuperainen);

    // muutetaan kopioa
    kopio[0] = 99;

    // tulostetaan molemmat
    System.out.println("alkup: " + Arrays.toString(alkuperainen));
    System.out.println("kopio: " + Arrays.toString(kopio));
}

alkup: [1, 2, 3, 4]
kopio: [99, 2, 3, 4]

public static void main(String[] args) {
    int[] alkuperainen = {1, 2, 3, 4};
    int[] kaannetty = new Taulukot().kaanna(alkuperainen);

    // tulostetaan molemmat
    System.out.println("alkup: " +Arrays.toString(alkuperainen));
    System.out.println("käännetty: " +Arrays.toString(kaannetty));
}

alkup: [1, 2, 3, 4]
käännetty: [4, 3, 2, 1]

Taulukko oliomuuttujana

Luokka voi sisältää muiden muuttujien lisäksi myös taulukon tai taulukoita oliomuuttujina. Alla oleva esimerkki kuvaa lottoriviä, johon voidaan lisätä numeroita. Jokaisessa lottorivissä on täsmälleen 7 lukua, jotka ovat väliltä 1-40 ja luku ei saa esiintyä rivissä kahdesti. Luokalla on myös toiminnallisuus

import java.util.Arrays;

public class Lottorivi {
    private int[] numerot;
    private int numeroita;

    public Lottorivi() {
        this.numerot = new int[7];
        this.numeroita = 0;
    }

    public void lisaa(int numero) {
        if (this.numeroita >= this.numerot.length) {
            System.out.println("Lottorivi on jo täysi!");
            return;
        }

        if (this.sisaltaa(numero)) {
            System.out.println("Numero on jo lottorivissä");
            return;
        }

        this.numerot[this.numeroita] = numero;
        this.numeroita++;
    }

    public boolean sisaltaa(int numero) {
        int indeksi = 0;
        while(indeksi < this.numeroita) {
            if (this.numerot[indeksi] == numero) {
                return true;
            }
        }

        return false;
    }

    public String toString() {
        return Arrays.toString(this.numerot);
    }
}

Pino p = new Pino();
p.lisaa("    *");
p.lisaa("*********");
p.lisaa(" *******");
p.lisaa("  *****");
p.lisaa("   ***");
p.lisaa("    *");

while (p.koko() > 0) {
    System.out.println(p.poista());
}

    *
   ***
  *****
 *******
*********
    *

Lyhyempi merkintätapa taulukon luomiseen

Merkkijono-olioiden lisäksi taulukko-olioiden luomiseen löytyy lyhyempi merkintätapa. Alla olevassa esimerkissä luodaan kolmepaikkainen kokonaislukutaulukko, johon asetetaan arvot 100, 1 ja 42.

int[] luvut = {100, 1, 42};

Taulukko-olio voidaan siis aiemmin näkemämme new-kutsun lisäksi alustaa myös lohkolla, jossa taulukkoon asetettavat arvot esitellään pilkulla eriteltyinä. Tämä toimii kaikille muuttujatyypeille: alla on esitelty ensin merkkijonoja sisältävä taulukko, jonka jälkeen esitellään liukulukuja sisältävä taulukko.

String[] merkkijonotaulukko = {"Matti L.", "Matti P.", "Matti V."};
double[] liukulukutaulukko = {1.20, 3.14, 100.0, 0.6666666667};

Lohkoalustusta käytettäessä taulukon koko on aina täsmälleen lohkossa määriteltyjen arvojen määrä. Lohkossa määritellyt arvot asetetaan taulukkoon järjestestyksessä siten, että ensimmäinen arvo asetetaan nollanteen indeksiin, toinen arvo ensimmäiseen indeksiin jne.

// indeksi       0   1    2    3   4   5     6     7
int[] luvut = {100,  1,  42,  23,  1,  1, 3200, 3201};

System.out.println(luvut[0]);  // tulostaa luvun taulukon indeksistä 0, eli luvun 100
System.out.println(luvut[2]);  // tulostaa luvun taulukon indeksistä 2, eli luvun 42

Kaksiulotteinen taulukko

Aiemmat taulukkoesimerkkimme ovat käsitelleet yksiulotteisia taulukoita, missä indeksi kertoo sijainnin yhdessä ulottuvuudessa. Taulukon voi luoda myös useampiulotteisena, jolloin taulukossa olevaa tietoa voi tarkastella useamman indeksin avulla. Tämä on kätevää esimerkiksi silloin, jos tieto on useampiulotteista kuten esimerkiksi koordinaatistossa.

Kaksiulotteinen taulukko, jossa on kaksi riviä ja kolme saraketta, luodaan seuraavasti:

int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];

Yllä luomme taulukon, jonka jokainen rivi viittaa taulukkoon, jossa on tietty määrä sarakkeita. Kaksiulotteisen taulukon läpikäynti onnistuu kahden sisäkkäisen while-toistolauseen avulla seuraavasti:

int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];

int y = 0;
while (y < kaksiulotteinenTaulukko.length) {

    int x = 0;
    while (x < kaksiulotteinenTaulukko[y].length) {
        int arvo = kaksiulotteinenTaulukko[y][x];
        System.out.println("arvo kohdassa (" + x + ", " + y + "): " + arvo);
        x++;
    }

    y++;
}

Ylläolevan ohjelman tulostus on seuraava.

arvo kohdassa (0, 0): 0
arvo kohdassa (1, 0): 0
arvo kohdassa (2, 0): 0
arvo kohdassa (0, 1): 0
arvo kohdassa (1, 1): 0
arvo kohdassa (2, 1): 0

Saatoit yllättyä. Selityksenä tulostukselle on se, että int-tyyppisten muuttujien oletusarvo on 0.

Voimme muuttaa taulukon arvoja kuten ennenkin. Alla asetamme kahteen kohtaan uudet arvot.

int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];

kaksiulotteinenTaulukko[0][1] = 4;
kaksiulotteinenTaulukko[1][1] = 1;
kaksiulotteinenTaulukko[1][0] = 8;


int y = 0;
while (y < kaksiulotteinenTaulukko.length) {

    int x = 0;
    while (x < kaksiulotteinenTaulukko[y].length) {
        int arvo = kaksiulotteinenTaulukko[y][x];
        System.out.println("arvo kohdassa (" + x + ", " + y + "): " + arvo);
        x++;
    }

    y++;
}

Nyt tulostus näyttää seuraavalta:

arvo kohdassa (0, 0): 0
arvo kohdassa (1, 0): 4
arvo kohdassa (2, 0): 0
arvo kohdassa (0, 1): 8
arvo kohdassa (1, 1): 1
arvo kohdassa (2, 1): 0

Kaksiulotteinen taulukko on oikeastaan matriisi. Matriiseja käytetään muunmuassa tietokonegrafiikassa, missä yksittäiset pikselit esitetään matriisin avulla.

Piirto-ohjelma

Tehtäväpohjaan on toteutettu graafinen sovellus, mikä sisältää kaksiulotteisen taulukon. Tehtävänäsi on muuttaa sovelluksen toimintaa siten, että kun käyttäjä painaa hiirtä sovelluksessa tai liikuttaa hiirtä kun nappi on pohjassa, ikkunaan piirretään.

Tee tätä varten kaksi asiaa: (1) muuta sovelluksessa olevan taulukon "piirrettava" arvoja sopivasti kun käyttäjä käyttää hiirtä, ja (2) piirrä komentoa piirturi(x, y, 2, 2) käyttäen ne alkiot, joiden arvo on 1. Käytä koordinaatteina x, y taulukon indeksejä.

Kun sovellus toimii, voit käyttää sitä vaikkapa seuraavanlaisen taideteoksen tekemiseen. Tehtävässä ei ole testejä.

Muita menetelmiä taulukon tulostamiseen

Käytimme esimerkeissä while-toistolausetta taulukon arvojen. Tulostamiseen voi käyttää myös edelliseltä viikolta tuttua virtaa sekä kohta tutuksi tulevaa for-toistolausetta.

Virta

Javan luokka Arrays tarjoaa metodin taulukon käsittelyyn virtana. Kutsumalla luokan metodia stream(taulukko), joka saa parametrinaan taulukon, luodaan käsiteltävä virta.

int[] luvut = {1, 8, 10, 3, 5};
Arrays.stream(luvut).forEach(luku -> System.out.println(luku));

1
8
10
3
5

int[] luvut = {1, 8, 10, 3, 5};
Arrays.stream(luvut)
    .filter(luku -> luku <= 5)
    .forEach(luku -> System.out.println(luku));

1
3
5

Sama onnistuu myös kaksi- ja useampiulotteisessa taulukossa. Tällöin ensimmäinen stream-kutsu luo yksiulotteisia taulukoita sisältävän syötevirran. Jokainen yksiulotteinen taulukko voidaan myös muuntaa arvoja sisältäväksi syötevirraksi.

int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];

Arrays.stream(kaksiulotteinenTaulukko)
    .forEach(taulukko -> {
        Arrays.stream(taulukko).forEach(alkio -> System.out.print(alkio + " "));
        System.out.println();
});

For-toistolause

Olemme toistaiseksi käyttäneet while-toistolausetta sekä virran forEach-komentoa. Ohjelmointikielistä löytyy yleensä myös for-toistolause, joka on kätevä erityisesti indeksoitavien joukkojen kuten taulukoiden käsittelyn yhteydessä. Seuraavassa tulostetaan for-toistolauseen avulla luvut 0, 1 ja 2:

for (int i = 0; i < 3; i++) {
    System.out.println(i);
}

Yllä oleva esimerkki toimii lähes samalla tavalla kuin alla oleva esimerkki. Ainoa ero on se, että alla muuttuja i on olemassa myös toistolauseen jälkeen.

int i = 0;  // toistossa käytettävän muuttujan alustus
while (i < 3) {  // toistoehto
    System.out.println(i);
    i++;   // toistossa käytettävän muuttujan päivitys
}

Toistolause for, kuten yllä esitelty for (int i = 0; i < 3; i++) sisältää kolme osaa: (1) muuttujien alustus; (2) toistoehto; ja (3) muuttujien päivitys.

• Ensimmäisessä osassa luodaan toistolauseessa käytettävät muuttujat. Yllä olevassa esimerkissä luodaan muuttuja i lauseella int i = 0. Ensimmäinen osa suoritetaan vain kerran, for-lauseen alussa.
• Toisessa osassa määritellään toistoehto, joka määrittelee mihin asti toistolauseen yhteydessä olevassa koodilohkossa olevaa koodia suoritetaan. Esimerkissämme toistoehto oli i < 3. Toistoehdon voimassaolo tarkastetaan ennen jokaista toistokertaa. Toistoehto toimii täsmälleen samoin kuin while-toistolauseen toistoehto.
• Kolmas osa, joka esimerkissämme on i++ suoritetaan kerran jokaisen koodilohkon suorituksen jälkeen.

Toistolause for on hieman while-toistolausetta selkeämpi tapa toteuttaa toistoja, joissa toistojen määrä perustuu esimerkiksi laskurin kasvatukseen. Taulukkojen läpikäynnissä tilanne on yleensä juuri tämä. Seuraavassa tulostetaan taulukon luvut sisältö for-toistolauseella.

int[] luvut = {1, 3, 5, 9, 17, 31, 57, 105};

for(int i = 3; i < 7; i++) {
    System.out.println(luvut[i]);
}

Toistolauseen muuttuja voi saada arvokseen muutakin kuin nollan, ja läpikäynti voi edetä esimerkiksi "ylhäältä alas". Taulukon indekseissä 6, 5, 4, ja 3 olevat alkiot voidaan tulostaa seuraavasti.

int[] luvut = {1, 3, 5, 9, 17, 31, 57, 105};

for(int i = 6; i > 2; i--) {
    System.out.println(luvut[i]);
}

Toistolause for toimii myös kaksi- ja useampiulotteisilla taulukoilla.

int rivit = 2;
int sarakkeet = 3;
int[][] kaksiulotteinenTaulukko = new int[rivit][sarakkeet];

kaksiulotteinenTaulukko[0][1] = 4;
kaksiulotteinenTaulukko[1][1] = 1;
kaksiulotteinenTaulukko[1][0] = 8;

for (int y = 0; y < kaksiulotteinenTaulukko.length; y++) {
    for (int x = 0; x < kaksiulotteinenTaulukko[y].length; x++) {
        int arvo = kaksiulotteinenTaulukko[y][x];
        System.out.println("arvo kohdassa (" + x + ", " + y + "): " + arvo);
    }
}

Tiedon hakeminen ja järjestäminen

Tiedon nopea hakeminen ja näyttäminen on oleellinen osa ohjelmistojen käytettävyyttä. Jos ohjelman käyttäjä joutuu odottamaan kymmeniä sekunteja kun ohjelma etsii käyttäjän haluamaa tietoa, saattaa ohjelman käyttäjä lopettaa ohjelman käyttämisen kokonaan. Vastaavasti televisio-ohjelmistoja selaava käyttäjä ei hyödy televisio-ohjelman tiedoista mitään jos tiedot latautuvat vasta ohjelman katsomisen jälkeen.

Laajemmin voidaan ajatella, että nopeasti tapahtuva tiedon hakeminen ja näyttäminen on oleellista oikeastaan lähes missä tahansa sovelluksessa. Tutustutaan seuraavaksi tiedon hakemiseen ja järjestämiseen liittyviin algoritmeihin. Vaikka esimerkit käyttävät taulukoita, algoritmit toimivat myös muilla tiedon tallentamiseen tarkoitetuilla tietorakenteilla kuten listoilla.

Peräkkäishaku

Peräkkäishaku on hakualgoritmi, joka etsii tietoa taulukosta käymällä taulukkoa läpi alkio alkiolta. Heti kun haettu alkio löytyy, sen indeksi palautetaan. Jos alkiota ei löydy, palautetaan tieto siitä ettei haettavaa alkiota löytynyt -- tämä kerrotaan tyypillisesti palauttamalla indeksin sijaan arvo -1.

public class Algoritmit {

    public int perakkaishaku(int[] taulukko, int haettava) {
        for (int i = 0; i < taulukko.length; i++) {
            if (taulukko[i] == haettava) {
                return i;
            }
        }

        return -1;
    }
}

Pahimmassa tapauksessa, eli tilanteessa missä alkiota ei lödy, algoritmi tekee taulukon koon verran vertailuja. Vaikkapa 10 miljoonaa arvoa sisältävässä taulukossa tämä tarkoittaa kymmentä miljoonaa vertailua. Jos tietoa haetaan useampia kertoja, kannattaa tehokkuutta yrittää parantaa.

Valintajärjestäminen

Jos tieto ei noudata minkäänlaista järjestystä tai sääntöä, on tiedon hakeminen tyypillisesti työlästä. Tarvitsemme siis järjestystä!

Ohjelmoijan yleissivistykseen kuuluu ainakin yhden järjestämisalgoritmin (eli tavan järjestää taulukko) tuntemus. Tutustutaan erääseen "klassiseen" järjestämisalgoritmiin, valintajärjestämiseen. Tutustuminen tapahtuu harjoitustehtävien avulla.

public int pienin(int[] taulukko) {
    // kirjoita koodia tähän
}

int[] luvut = {6, 5, 8, 7, 11};
System.out.println("Pienin: " + new Valintajarjestaminen().pienin(luvut));

Pienin: 5

public int pienimmanIndeksi(int[] taulukko) {
    // kirjoita koodia tähän
}

// indeksit:   0  1  2  3  4
int[] luvut = {6, 5, 8, 7, 11};
System.out.println("Pienimmän indeksi: " + new Valintajarjestaminen().pienimmanIndeksi(luvut));

Pienimmän indeksi: 1

public int pienimmanIndeksiAlkaen(int[] taulukko, int aloitusIndeksi) {
    // kirjoita koodia tähän
}

Valintajarjestaminen algoritmi = new Valintajarjestaminen();

// indeksit:    0  1  2  3   4
int[] luvut = {-1, 6, 9, 8, 12};
System.out.println(algoritmi.pienimmanIndeksiAlkaen(luvut, 0));
System.out.println(algoritmi.pienimmanIndeksiAlkaen(luvut, 1));
System.out.println(algoritmi.pienimmanIndeksiAlkaen(luvut, 2));

0
1
3

public void vaihda(int[] taulukko, int indeksi1, int indeksi2) {
    // kirjoita koodia tähän
}

int[] luvut = {3, 2, 5, 4, 8};

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

vaihda(luvut, 1, 0);
System.out.println(Arrays.toString(luvut));

vaihda(luvut, 0, 3);
System.out.println(Arrays.toString(luvut));

[3, 2, 5, 4, 8]
[2, 3, 5, 4, 8]
[4, 3, 5, 2, 8]

public void jarjesta(int[] taulukko) {
    
}

int[] luvut = {8, 3, 7, 9, 1, 2, 4};
new Valintajarjestaminen().jarjesta(luvut);

[8, 3, 7, 9, 1, 2, 4]
[1, 3, 7, 9, 8, 2, 4]
[1, 2, 7, 9, 8, 3, 4]
[1, 2, 3, 9, 8, 7, 4]
[1, 2, 3, 4, 8, 7, 9]
[1, 2, 3, 4, 7, 8, 9]
[1, 2, 3, 4, 7, 8, 9]

Puolitushaku (binäärihaku)

Kun tieto on järjestyksessä, hakeminen onnistuu paljon tehokkaammin.

Tutkitaan binäärihaun ideaa seuraavan järjestyksessä olevan taulukon avulla.

// indeksit   0   1   2   3    4   5    6   7   8   9  10
// luvut     -7  -3   3   7   11  15   17  21  24  28  30

Oletetaan että haluamme löytää luvun 17 indeksin. Hyödynnetään tietoa siitä että taulukon arvot ovat järjestyksessä. Sen sijaan, että kävisimme taulukon lukuja läpi taulukon alusta lähtien, tarkastelemme arvoa taulukon puolivälissä. Taulukon puolivälissä olevan alkion indeksi on isoin indeksi 10 jaettuna kahdella eli 5. Keskimmäinen alkio on merkattu seuraavaan tähdellä:

                                   *
// indeksit   0   1   2   3    4   5    6   7   8   9  10
// luvut     -7  -3   3   7   11  15   17  21  24  28  30

Puolessa välissä on luku 15, joka ei ollut hakemamme luku (eli luku 17). Koska taulukko on järjestyksessä (tässä suuruusjärjestyksessä), ei etsitty luku voi missään tapauksessa olla luvun 15 vasemmalla puolella. Voimme siis päätellä että kaikki indeksit, jotka ovat pienempiä tai yhtäsuuria kuin 5, eivät missään nimessä sisällä hakemaamme arvoa.

Alue, jolta etsimme haettavaa lukua voidaan nyt rajata lukuihin, jotka sijaitsevat indeksin 5 oikealla puolella, eli indekseihin välillä [6, 10] (6, 7, 8, 9, 10). Seuraavassa on merkitty harmaalla se osa taulukkoa jossa etsitty ei voi olla:

// indeksit    0   1   2   3   4    5    6   7   8   9  10
// luvut      -7  -3   3   7  11   15   17  21  24  28  30

Tutkitaan seuraavaksi jäljellä olevan etsintäalueen, eli indeksien 6-10 keskimmäistä indeksiä. Keskimmäinen indeksi löytyy laskemalla etsintäalueen pienimmän ja suurimman indeksin summan ja jakamalla se kahdella, eli (6+10)/2 = 16/2 = 8. Indeksi 8 on merkitty alle tähdellä.

                                                 *
// indeksit    0   1   2   3   4    5    6   7   8   9  10
// luvut      -7  -3   3   7  11   15   17  21  24  28  30

Indeksissä 8 oleva luku on 24, joka ei ollut hakemamme luku. Koska luvut taulukossa ovat suuruusjärjestyksessä, ei etsittävä luku voi missään nimessä olla luvun 24 oikealla puolella. Voimme siis päätellä että kaikki indeksit, jotka ovat suurempia tai yhtäsuuria kuin 8, eivät missään nimessä sisällä hakemaamme arvoa. Etsintäalue rajautuu taas, harmaat alueet on käsitelty:

// indeksit    0   1   2   3   4    5    6   7   8   9  10
// luvut      -7  -3   3   7  11   15   17  21  24  28  30

Etsintä jatkuu. Tutkitaan jäljellä olevan etsintäalueen, eli indeksien 6-7, keskimmäistä indeksiä. Keskimmäinen indeksi löytyy taas ottamalla etsintäalueen pienimmän ja suurimman indeksin summa ja jakamalla se kahdella, eli (6+7)/2 = 6,5, joka pyöristyy alaspäin luvuksi 6. Kohta on merkitty alle tähdellä.

                                         *
// indeksit    0   1   2   3   4    5    6   7   8   9  10
// luvut      -7  -3   3   7  11   15   17  21  24  28  30

Indeksissä 6 on luku 17, joka on sama kuin hakemamme luku. Voimme lopettaa haun ja ilmoittaa että etsitty luku on taulukossa. Jos luku ei olisi ollut taulukossa -- esimerkiksi jos haettava luku olisi ollut 16, etsintäalue olisi jäänyt lopulta tyhjäksi.

                                         *
// indeksit    0   1   2   3   4    5    6   7   8   9  10
// luvut      -7  -3   3   7  11   15   17  21  24  28  30

Jotta binäärihaun idea tulee sinulle tutuksi, simuloi kynällä ja paperilla miten binäärihaku toimii kun taulukkona on alla oleva taulukko ja haet lukua 33. Kokeile tämän jälkeen binäärihakua vielä siten, että etsit lukua 1.

// indeksit   0   1   2   3   4   5   6   7   8   9  10  11  12  13
// luvut     -5  -2   3   5   8  11  14  20  22  26  29  33  38  41

Valmiiden järjestämisalgoritmien hyödyntäminen

Java tarjoaa merkittävän määrän valmiita järjestysalgoritmeja. Taulukot voi järjestää (luonnolliseen järjestykseen) luokan Arrays tarjoamalla metodilla sort, ja listat voi järjestää (luonnolliseen järjestykseen) luokan Collections tarjoamalla metodilla sort.

int[] luvut = {8, 3, 7, 9, 1, 2, 4};
System.out.println(Arrays.toString(luvut));
Arrays.sort(luvut);
System.out.println(Arrays.toString(luvut));

[8, 3, 7, 9, 1, 2, 4]
[1, 2, 3, 4, 7, 8, 9]

ArrayList<Integer> luvut = new ArrayList<>();
luvut.add(8);
luvut.add(3);
luvut.add(7);
System.out.println(luvut);
Collections.sort(luvut);
System.out.println(luvut);

[8, 3, 7]
[3, 7, 8]

Valmiit järjestämisalgoritmit toimivat sekä alkeistyyppisille muuttujille, että joillekin viittaustyyppisille muuttujille kuten String. Omien luokkiemme järjestämistä varten joudumme antamaan Javalle hieman lisävinkkejä, sillä luokat eivät sisällä tietoa siitä, miten niistä luodut oliot pitäisi järjestää.

Omien olioiden järjestäminen

Omien olioiden järjestäminen onnistuu näppärästi virtojen avulla. Oletetaan, että käytössämme on seuraava luokka Henkilo.

public class Henkilo {

    private int syntymavuosi;
    private String nimi;

    public Henkilo(int syntymavuosi, String nimi) {
        this.syntymavuosi = syntymavuosi;
        this.nimi = nimi;
    }

    public String getNimi() {
        return nimi;
    }

    public int getSyntymavuosi() {
        return syntymavuosi;
    }
}

Listalle asetettujen henkilöiden järjestäminen onnistuu näppärästi virran tarjoaman metodin sorted avulla. Metodille määritellään miten mitä tahansa kahta listalla olevaa oliota tulee vertailla keskenään. Vertailun tulee palauttaa kokonaisluku -- negatiivinen kokonaisluku kertoo, että ensimmäinen vertailtavista tulee ennen toista vertailtavaa ja positiivinen kokonaisluku kertoo että toinen vertailtavista tulee ennen ensimmäistä vertailtavaa. Jos palautettava kokonaisluku on nolla, olioiden järjestys on sama.

ArrayList<Henkilo> henkilot = new ArrayList<>();
henkilot.add(new Henkilo("Ada Lovelace", 1815));
henkilot.add(new Henkilo("Irma Wyman", 1928));
henkilot.add(new Henkilo("Grace Hopper", 1906));
henkilot.add(new Henkilo("Mary Coombs", 1929));

henkilot.stream().sorted((h1, h2) -> {
    return h1.getSyntymavuosi() - h2.getSyntymavuosi();
}).forEach(h -> System.out.println(h.getNimi()));

Ada Lovelace
Grace Hopper
Irma Wyman
Mary Coombs

Yllä oleva vertailu vastaa järjestämisen tekevät algoritmin näkökulmasta seuraavaa vertailua. Palautettavan arvon suuruudella ei ole väliä.

// ...
henkilot.stream().sorted((h1, h2) -> {
    if (h1.getSyntymavuosi() > h2.getSyntymavuosi()) {
        return 1;
    }

    if (h1.getSyntymavuosi() < h2.getSyntymavuosi()) {
        return -1;
    }

    return 0;
}).forEach(h -> System.out.println(h.getNimi()));

Merkkijonoja vertailtaessa voimme käyttää String-luokan valmista compareTo-metodia. Metodi palauttaa sille annetun parametrina annetun merkkijonon sekä metodia kutsuvan merkkijonon järjestykstä kuvaavan kokonaisluvun.

ArrayList<Henkilo> henkilot = new ArrayList<>();
henkilot.add(new Henkilo("Ada Lovelace", 1815));
henkilot.add(new Henkilo("Irma Wyman", 1928));
henkilot.add(new Henkilo("Grace Hopper", 1906));
henkilot.add(new Henkilo("Mary Coombs", 1929));

henkilot.stream().sorted((h1, h2) -> {
    return h1.getNimi().compareTo(h2.getNimi());
}).forEach(h -> System.out.println(h.getNimi()));

Ada Lovelace
Grace Hopper
Irma Wyman
Mary Coombs

Adult literacy rate, population 15+ years, female (%),United Republic of Tanzania,2015,76.08978
Adult literacy rate, population 15+ years, female (%),Zimbabwe,2015,85.28513
Adult literacy rate, population 15+ years, male (%),Honduras,2014,87.39595
Adult literacy rate, population 15+ years, male (%),Honduras,2015,88.32135
Adult literacy rate, population 15+ years, male (%),Angola,2014,82.15105
  

Niger (2015), female, 11.01572
Mali (2015), female, 22.19578
Guinea (2015), female, 22.87104
Afghanistan (2015), female, 23.87385
Central African Republic (2015), female, 24.35549

ArrayList ja Hajautustaulu

ArrayList ja Hajautustaulu ovat ohjemoinnissa hyvin yleisesti käytettyjä tietorakenteita. Tarkastellaan tässä niiden todellista toteutusta -- alla rakennetaan askeleittain ensin ArrayListiä imitoiva tietorakenne Lista, jota hyödynnetään sitten tietorakenteen Hajautustaulu tekemisessä.

Geneerinen tyyppi

Olemme listoihin tutustumisesta lähtien kertoneet erilaisille tietorakenteille niiden sisältämän arvon tyypin. Esimerkiksi String-tyyppisiä olioita sisältävä lista on esitelty muodossa ArrayList<String>. Tässä on kuitenkin ihmetyttänyt se, että miten ihmeessä listat ja muutkin tietorakenteet voivat sisältää erityyppisiä oliota.

Geneerisyys (generics) liittyy olioita säilövien luokkien tapaan säilöä vapaavalintaisen tyyppisiä olioita. Vapaavalintaisuus perustuu luokkien määrittelyssä käytettyyn geneeriseen tyyppiparametriin, jonka avulla voidaan määritellä olion luontivaiheessa valittavia tyyppejä. Luokan geneerisyys määritellään antamalla luokan nimen jälkeen haluttu määrä luokan tyyppiparametreja pienempi kuin ja suurempi kuin -merkkien väliin. Toteutetaan oma geneerinen luokka Lokero, johon voi asettaa yhden minkälaisen tahansa olion.

public class Lokero<T> {
    private T alkio;

    public void asetaArvo(T alkio) {
        this.alkio = alkio;
    }

    public T haeArvo() {
        return alkio;
    }
}

Määrittely public class Lokero<T> kertoo että luokalle Lokero tulee antaa konstruktorissa tyyppiparametri. Konstruktorikutsun jälkeen kaikki olion sisäiset muuttujat tulevat olemaan kutsun yhteydessä annettua tyyppiä. Luodaan merkkijonon tallentava lokero.

Lokero<String> merkkijono = new Lokero<>();
merkkijono.asetaArvo(":)");

System.out.println(merkkijono.haeArvo());

:)

Yllä olevalla ohjelmalla merkkijono-nimisen Lokero-olion ajonaikainen toteutus on seuraavanlainen.

public class Lokero<String> {
    private String alkio;

    public void asetaArvo(String alkio) {
        this.alkio = alkio;
    }

    public String haeArvo() {
        return alkio;
    }
}

Tyyppiparametria vaihtamalla voidaan luoda myös muuntyyppisiä olioita tallentavia Lokero-olioita. Esimerkiksi kokonaisluvun saa tallennettua seuraavasti.

Lokero<Integer> luku = new Lokero<>();
luku.asetaArvo(5);

System.out.println(luku.haeArvo());

5

Yllä olevalla esimerkillä luku-nimisen Lokeron toteutus olisi ajonaikaisesti taas seuraavanlainen.

public class Lokero<Integer> {
    private Integer alkio;

    public void asetaArvo(Integer alkio) {
        this.alkio = alkio;
    }

    public Integer haeArvo() {
        return alkio;
    }
}

Samalla tavalla ohjelmoija voisi toteuttaa esimerkiksi luokan Pari, mihin voi laittaa kaksi halutun tyyppistä oliota.

public class Pari<T, K> {
    private T eka;
    private K toka;

    public void asetaArvot(T eka, K toka) {
        this.eka = eka;
        this.toka = toka;
    }

    public T haeEka() {
        return this.eka;
    }

    public K haeToka() {
        return this.toka;
    }
}

Huomattava osa Javan tietorakenteista mahdollistaa eri tyyppisten muuttujien käytön. Esimerkiksi ArrayList saa yhden tyyppiparametrin, HashMap kaksi.

List<String> merkkijonot = new ArrayList<>();
Map<String, String> avainArvoParit = new HashMap<>();

Jatkossa kun näet esimerkiksi tyypin ArrayList<String> tiedät että sen sisäisessä rakenteessa on käytetty geneeristä tyyppiparametria. Sama periaate löytyy esimerkiksi rajapinnassa Comparable.

Listarakenne

Tarkastellaan erästä tapaa Javan tarjoaman ArrayList-tietorakenteen toteuttamiseen. Javan ArrayList hyödyntää sisäisesti taulukkoa, mikä on määritelty generisen tyyppiseksi -- tämän takia listalle saa lisätä käytännössä minkä tyyppisiä arvoja tahansa. Lista tarjoaa useita metodeja, joista tämän esimerkin kannalta oleellisia ovat add eli lisääminen, contains eli olemassaolon tarkastaminen, remove eli poistaminen sekä get, eli tietystä indeksistä hakeminen.

ArrayList<String> merkkijonot = new ArrayList<>();
System.out.println(merkkijonot.contains("Hei!"));
merkkijonot.add("Hei!");
System.out.println(merkkijonot.contains("Hei!"));
merkkijonot.remove("Hei!");
System.out.println(merkkijonot.contains("Hei!"));

false
true
false

Listan luominen

Luodaan luokka Lista. Listarakenne sisältää geneerisen taulukon -- eli taulukon, jonka alkioiden tyyppi määräytyy ajonaikaisesti tyyppiparametreista. Asetetaan taulukon alkukooksi 10.

public class Lista<T> {
    private T[] arvot;

    public Lista() {
        this.arvot = (T[]) new Object[10];
    }
}

Lista kapseloi taulukon. Alkutilanteessa jokainen taulukon indeksi sisältää null-viitteen.

Arvojen lisääminen listalle

Lisätään luokalle metodi public void lisaa(T arvo), mikä mahdollistaa arvojen lisäämisen listalle. Luodaan luokalle tätä varten erillinen kokonaislukumuuttuja, joka pitää kirjaa taulukon ensimmäisestä tyhjästä paikasta.

public class Lista<T> {

    private T[] arvot;
    private int arvoja;

    public Lista() {
        this.arvot = (T[]) new Object[10];
        this.arvoja = 0;
    }

    public void lisaa(T arvo) {
        this.arvot[this.arvoja] = arvo;
        this.arvoja++;
    }
}

Nyt arvojen lisääminen listalle onnistuu -- tai, ainakin listan luominen ja metodin kutsuminen onnistuu -- emme vielä voi testata ovatko arvot todellisuudessa listalla.

Lista<String> lista = new Lista<>();
lista.lisaa("hei");
lista.lisaa("maailma");

Arvojen lisääminen listalle, osa 2

Edellä kuvatussa lisaa-metodissa on pieni ongelma. Ongelma ilmenee kun seuraava ohjelmakoodi suoritetaan.

Lista<String> lista = new Lista<>();
for (int i = 0; i < 11; i++) {
    lista.lisaa("hei");
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
	at tietorakenteita.Lista.lisaa(Lista.java:14)
	at tietorakenteita.Ohjelma.main(Ohjelma.java:8)

Listan koko ei kasva. Eräs ArrayList-luokan oleellisimmista toiminnallisuuksista on se, että sen koko kasvaa aina tarvittaessa -- ohjelmoijan ei siis tarvitse varoa listan täyttymistä.

Lisätään ohjelmaan listan koon kasvattamiseen liittyvä toiminnallisuus. Listan kokoa kasvatetaan aina jos täyteen listaan yritetään lisätä arvo. Kasvattaminen toteutetaan käytännössä siten, että luomme uuden taulukon, mihin vanhan taulukon arvot kopioidaan. Tämän jälkeen vanha taulukko jätetään heitteille, ja uudesta taulukosta tulee olion käyttämä taulukko.

Javan kuudennessa versiossa uuden taulukon koko lasketaan kaavalla vanhakoko * 3 / 2 + 1. Hyödynnetään samaa kaavaa omassa toteutuksessamme. Luodaan kasvattamista varten erillinen metodi kasvata, joka on vain luokan omien metodien käytössä (eli sillä on private-näkyvyys).

private void kasvata() {
    T[] uusi = (T[]) new Object[this.arvot.length * 3 / 2 + 1];
    for (int i = 0; i < this.arvot.length; i++) {
        uusi[i] = this.arvot[i];
    }
  
    this.arvot = uusi;
}

Toteutus luo uuden taulukon, jonka koko on noin 1.5-kertainen vanhaan taulukkoon verrattuna. Tämän jälkeen kaikki vanhan taulukon alkiot kopioidaan uuteen taulukkoon ja lopulta olion arvot-muuttujan -- eli taulukon -- arvoksi asetetaan uusi taulukko.

Muokataan vielä metodia lisaa siten, että taulukon kokoa kasvatetaan tarvittaessa.

public void lisaa(T arvo) {
    if(this.arvoja == this.arvot.length) {
        kasvata();
    }
        
    this.arvot[this.arvoja] = arvo;
    this.arvoja++;
}

Nyt arvoja voi lisätä listalle lähes rajattomasti.

Arvon olemassaolon tarkastaminen

Luodaan listalle seuraavaksi metodi public boolean sisaltaa(T arvo), minkä avulla voidaan tarkistaa onko alkio listalla. Hyödynnetään tässä tietoa siitä, että jokainen Javan olio -- riippumatta sen tyypistä -- perii Object-luokan (tai on Object-tyyppinen). Tämän takia jokaisella oliolla on metodi public boolean equals(Object object), jota voidaan käyttää yhtäsuuruuden tarkasteluun.

Luokan Lista muuttuja arvoja sisältää tiedon arvojen tämän hetkisestä lukumäärästä. Voimme siis toteuttaa sisaltaa-metodin siten, että tarkastelemme vain ne listan indeksit, joissa on arvoja.

public boolean sisaltaa(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (this.arvot[i].equals(arvo)) {
            return true;
        }
    }
  
    return false;
}

Edellä esitetty menetelmä olettaa, että käyttäjä ei lisää listalle null-viitettä. Jos haluamme, että käyttäjä saa lisätä listalle null-viitteen (ja null-viitteen olemassaoloa saa myös hakea), tulee ohjelmaa muokata hieman. Tällöin sisaltaa-metodin eräs mahdollinen toteutus olisi seuraava.

public boolean sisaltaa(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            return true;
        }
    }
  
    return false;
}

Yllä oleva esimerkki ei kuitenkaan toimi. Pohdi miksei ja mieti minkälaisella ratkaisulla saisit null-viitteiden käsittelyn toimimaan.

Ohjelmassa on nyt mahdollisuus listalla olevien alkioiden olemassaolon tarkasteluun.

Lista<String> lista = new Lista<>();
System.out.println(lista.sisaltaa("hei"));
lista.lisaa("hei");
System.out.println(lista.sisaltaa("hei"));

false
true

Arvon poistaminen

Toteuttamallemme listalle voi nyt lisätä arvoja, jonka lisäksi arvon olemassaolon voi tarkastaa. Toteutetaan vielä arvon poistaminen. Toteutetaan metodi public void poista(T arvo), joka poistaa listalta yhden arvo-arvoisen alkion.

Yksinkertainen toteutus olisi seuraava.

public void poista(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            this.arvot[i] = null;
            this.arvoja--;
            return true;
        }
    }
  
    return false;
}

Yllä oleva lähestymistapa on kuitenkin ongelmallinen, sillä se jättää listalle "tyhjiä" kohtia -- olettaen, että uudet arvot lisätään aina listan loppuun.

Ongelman voi ratkaista useammalla tavalla, joista yksi on siirtää jokaista poistettua arvoa seuraavaa arvoa vasemmalle. Lisätään tämä toiminnallisuus ohjelmaan.

public void poista(T arvo) {
    boolean loytyi = false;
    for (int i = 0; i < this.arvoja; i++) {
        if (loytyi) {
            this.arvot[i - 1] = this.arvot[i];
        } else if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            this.arvoja--;
            loytyi = true;
        }
    }
}

Emme ole kovin tyytyväisiä edelliseen ratkaisuun, sillä siinä tehdään monta asiaa samaan aikaan. Metodissa sekä etsitään alkiota että siirretään alkioita. Pilkotaan toiminnallisuus kahteen erilliseen metodiin: private int arvonIndeksi(T arvo), joka etsii parametrina annetun arvon indeksin, sekä private void siirraVasemmalle(int indeksista), joka siirtää annetusta indeksistä lähtien alkioita yhden vasemmalle.

Toteutetaan ensin metodi private int arvonIndeksi(T arvo), joka etsii annetun arvon indeksin. Metodi palauttaa negatiivisen luvun mikäli arvoa ei löydy.

private int arvonIndeksi(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            return i;
        }
    }

    return -1;
}

Toteutetaan tämän jälkeen metodi private void siirraVasemmalle(int indeksistaLahtien), joka siirtää arvoja annetusta indeksistä lähtien vasemmalle.

private void siirraVasemmalle(int indeksistaLahtien) {
    for (int i = indeksistaLahtien; i < this.arvoja - 1; i++) {
        this.arvot[i] = this.arvot[i + 1];
    }
}

Nyt metodi poista voidaan toteuttaa edellisten avulla hieman selkokielisemmäksi.

public void poista(T arvo) {
    int arvonIndeksi = arvonIndeksi(arvo);
    if (arvonIndeksi < 0) {
        return; // ei löydy
    }

    siirraVasemmalle(arvonIndeksi);
    this.arvoja--;
}

Luokassa lista on vieläkin vähän toistoa. Metodi sisaltaa on hyvin samankaltainen metodin arvonIndeksi kanssa. Muokataan vielä metodia sisaltaa siten, että se toteutetaan metodin arvonIndeksi avulla.

public boolean sisaltaa(T arvo) {
    return arvonIndeksi(arvo) >= 0;
}

Nyt käytössämme on lista, joka tarjoaa metodit lisaa, sisaltaa, ja poista. Lista myös kasvaa tarvittaessa. Listan toteutusta voisi toki vielä kehittää esimerkiksi lisäämällä toiminnallisuuden, mikä pienentää listan kokoa jos arvojen määrä pienenee hyvin pieneksi.

Lista<String> lista = new Lista<>();
System.out.println(lista.sisaltaa("hei"));
lista.lisaa("hei");
System.out.println(lista.sisaltaa("hei"));
lista.poista("hei");
System.out.println(lista.sisaltaa("hei"));

false
true
false

Kohdasta hakeminen

Lisätään listalle vielä metodi public T arvo(int indeksi), joka palauttaa listan tietyssä indeksissä sijaitsevan arvon. Mikäli ohjelmoija hakee arvoa listan ulkopuolelta, heitetään virhe IndexOutOfBoundsException.

public T arvo(int indeksi) {
    if (indeksi < 0 || indeksi >= this.arvoja) {
        throw new ArrayIndexOutOfBoundsException("Indeksi " + indeksi + " alueen [0, " + this.arvoja + "[ ulkopuolella.");
    }

    return this.arvot[indeksi];
}

Metodi ei ole sellaisenaan kovin hyödyllinen, sillä ohjelmoijalla ei ole tietoa arvojen indekseistä. Muutetaan vielä metodi arvonIndeksi(T arvo) kaikkien käytettäväksi, eli vaihdetaan sen näkyvyysmääre private muotoon public.

public int arvonIndeksi(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            return i;
        }
    }

    return -1;
}

Lista<String> lista = new Lista<>();
System.out.println(lista.sisaltaa("hei"));
lista.lisaa("hei");
System.out.println(lista.sisaltaa("hei"));
int indeksi = lista.arvonIndeksi("hei");
System.out.println(indeksi);
System.out.println(lista.arvo(indeksi));
lista.poista("hei");
System.out.println(lista.sisaltaa("hei"));

false
true
0
hei
false

Listan koko

Lisätään listalle vielä metodi listan koon tarkastamiseen. Listan koon saa selville muuttujasta arvoja.

public int koko() {
    return this.arvoja;
}

Nyt listan alkioiden läpikäynti onnistuu mm. for-lauseella.

Lista<String> lista = new Lista<>();
lista.lisaa("hei");
lista.lisaa("maailma");

for(int i = 0; i < lista.koko(); i++) {
    System.out.println(lista.arvo(i)); 
}

hei
maailma

Hajautustaulu

Hajautustaulu on toteutettu taulukkona, missä jokainen alkio sisältää listan. Listalle tallennetaan (avain,arvo)-pareja. Käyttäjä voi hakea hajautustaulusta arvoja avaimen perusteella, ja toisaalta käyttäjä voi lisätä hajautustauluun avain-arvo -pareja. Kukin avain voi esiintyä hajautustaulussa korkeintaan kerran.

Hajautustaulun toiminta perustuu avaimen hajautusarvoon. Kun hajautustauluun lisätään (avain,arvo)-pari, lasketaan avaimeen liittyvä hajautusarvo. Hajautusarvo määrää hajautustaulun sisäisen taulukon indeksin, missä olevaan listaan (avain,arvo)-pari lisätään.

Hahmotellaan hajautustaulun toimintaa.

Avain-arvo -pari

Luodaan ensin avain-arvo -paria kuvaava luokka Pari. Haluamme tehdä hajautustaulusta mahdollisimman yleiskäyttöisen, joten avaimen ja arvon tyyppi määrätään ajonaikaisesti. Pari sisältää avaimen ja arvon sekä niihin liittyvät get- ja set-metodit.

public class Pari<K, V> {

    private K avain;
    private V arvo;

    public Pari(K avain, V arvo) {
        this.avain = avain;
        this.arvo = arvo;
    }

    public K getAvain() {
        return avain;
    }

    public void setAvain(K avain) {
        this.avain = avain;
    }

    public V getArvo() {
        return arvo;
    }

    public void setArvo(V arvo) {
        this.arvo = arvo;
    }

}

Avain-arvo -parien luominen on suoraviivaista.

Pari<String, Integer> pari = new Pari<>("yksi", 1);
System.out.println(pari.getAvain() + " -> " + pari.getArvo());

yksi -> 1

Hajautustaulun luominen

Hajautustaulu sisältää taulukon listoja. Jokainen listan arvo on edellä kuvattu pari, joka sisältää avain-arvo -parin. Hajautustaululla on lisäksi tieto arvojen lukumäärästä.

public class Hajautustaulu<K, V> {

    private Lista<Pari<K, V>>[] arvot;
    private int arvoja;

    public Hajautustaulu() {
        this.arvot = new Lista[32];
        this.arvoja = 0;
    }
}

Arvon hakeminen

Toteutetaan ensin metodi public V hae(K avain), jota käytetään arvon hakemiseen avaimen perusteella. Metodissa lasketaan ensin avaimen hajautusarvo ja päätellään sen perusteella hajautustaulun sisäisen taulukon indeksi, mistä arvoja haetaan. Mikäli kyseisessä indeksissä ei ole listaa, ei indeksiin ole lisätty vielä yhtäkään avain-arvo -paria, eikä avaimelle ole tallennettu arvoa. Tällöin palautetaan null. Muussa tapauksessa taulukon indeksissä oleva lista käydään läpi, ja avaimen yhtäsuuruutta vertaillaan jokaiseen listan avain-arvo -parin avaimeen. Mikäli joku listalla olevista avaimista vastaa avainta, jonka perusteella arvoa haetaan, palautetaan kyseinen arvo. Muulloin avainta (ja siihen liittyvää arvoa) ei löydy, ja palautetaan arvo null.

public V hae(K avain) {
    int hajautusArvo = Math.abs(avain.hashCode() % this.arvot.length);
    if (this.arvot[hajautusArvo] == null) {
        return null;
    }
        
    Lista<Pari<K, V>> arvotIndeksissa = this.arvot[hajautusArvo];

    for (int i = 0; i < arvotIndeksissa.koko(); i++) {
        if (arvotIndeksissa.arvo(i).getAvain().equals(avain)) {
            return arvotIndeksissa.arvo(i).getArvo();
        }
    }
  
    return null;
}

Hajautustauluun lisääminen, osa 1

Toteutetaan hajautustauluun lisäämisen käytettävän metodin public void lisaa(K avain, V arvo) ensimmäinen versio. Ensimmäisessä versiossa hajautustaulun sisältämän taulukon kokoa ei kasvateta lisäyksen yhteydessä.

Metodi laskee ensin avaimelle hajautusarvon ja päättelee hajautusarvon perusteella hajautustaulun sisäisen taulukon indeksin. Jos taulukon kyseisessä indeksissä ei ole arvoa, taulukon indeksiin lisätään lista. Tämän jälkeen taulukon indeksissä oleva lista käydään läpi ja sieltä etsitään avain-arvo -paria, jonka avain vastaa lisättävän avain-arvo -parin avainta. Mikäli vastaava avain löytyy, päivitetään olemassaolevan avain-arvo -parin arvo vastaamaan uutta avainta. Muulloin listaan lisätään uusi avain-arvo -pari -- tällöin myös hajautustaulussa olevien arvojen lukumäärää kasvatetaan yhdellä.

public void lisaa(K avain, V arvo) {
    int hajautusArvo = Math.abs(avain.hashCode() % arvot.length);
    if (arvot[hajautusArvo] == null) {
        arvot[hajautusArvo] = new Lista<>();
    }

    Lista<Pari<K, V>> arvotIndeksissa = arvot[hajautusArvo];

    int indeksi = -1;
    for (int i = 0; i < arvotIndeksissa.koko(); i++) {
        if (arvotIndeksissa.arvo(i).getAvain().equals(avain)) {
            indeksi = i;
            break;
        }
    }

    if (indeksi < 0) {
        arvotIndeksissa.lisaa(new Pari<>(avain, arvo));
        this.arvoja++;
    } else {
        arvotIndeksissa.arvo(indeksi).setArvo(arvo);
    }
}

Metodi on melko monimutkainen. Pilkotaan se pienempiin osiin -- ensimmäisen osan vastuulla on avaimeen liittyvän listan hakeminen ja toisen osan vastuulla on avaimen indeksin etsiminen listalta.

private Lista<Pari<K, V>> haeAvaimeenLittyvaLista(K avain) {
    int hajautusArvo = Math.abs(avain.hashCode() % arvot.length);
    if (arvot[hajautusArvo] == null) {
        arvot[hajautusArvo] = new Lista<>();
    }

    return arvot[hajautusArvo];
}
  
private int haeAvaimenIndeksi(Lista<Pari<K, V>> lista, K avain) {
    for (int i = 0; i < lista.koko(); i++) {
        if (lista.arvo(i).getAvain().equals(avain)) {
            return i;
        }
    }

    return -1;
}

Nyt metodi public void lisaa(K avain, V arvo) voidaan toteuttaa hieman selkeämmin.

public void lisaa(K avain, V arvo) {
    Lista<Pari<K, V>> arvotIndeksissa = haeAvaimeenLittyvaLista(avain);
    int indeksi = haeAvaimenIndeksi(arvotIndeksissa, avain);

    if (indeksi < 0) {
        arvotIndeksissa.lisaa(new Pari<>(avain, arvo));
        this.arvoja++;
    } else {
        arvotIndeksissa.arvo(indeksi).setArvo(arvo);
    }
}

Hajautustauluun lisääminen, osa 2

Edellä kuvattu hajautustauluun lisääminen toimii osittain. Toiminnallisuuden suurin puute on se, että taulukon kokoa ei kasvateta kun arvojen määrä kasvaa liian suureksi. Lisätään ohjelmaan kasvatustoiminnallisuus, mikä tuplaa hajautustaulun sisäisen taulukon koon. Kasvatustoiminnallisuuden tulee myös sijoittaa jokainen hajautustaulussa olevan taulukon arvo uuteen taulukkoon.

Hahmotellaan kasvatustoiminnallisuuden alku. Kasvatustoiminnallisuudessa luodaan uusi taulukko, jonka koko on edelliseen verrattuna kaksinkertainen. Tämän jälkeen alkuperäinen taulukko käydään indeksi indeksiltä läpi ja olemassaolevat avain-arvo -parit kopioidaan uuteen taulukkoon. Lopulta alkuperäinen taulukko korvataan uudella taulukolla.

Alla on hahmoteltu metodin toimintaa. Kopiointia ei ole vielä toteutettu.

private void kasvata() {
    // luodaan uusi taulukko
    Lista<Pari<K, V>>[] uusi = new Lista[this.arvot.length * 2];

    for (int i = 0; i < this.arvot.length; i++) {
        // kopioidaan vanhan taulukon arvot uuteen

    }

    // korvataan vanha taulukko uudella
    this.arvot = uusi;

Hahmotellaan seuraavaksi metodia, joka kopioi alkuperäisen taulukon yhden indeksin sisältämän listan arvot uuteen taulukkoon. Kopioinnin yhteydessä jokaisen kopioitavan avain-arvo -parin sijainti taulukossa lasketaan uudelleen -- tämä tehdään, sillä taustalla olevan taulukon koko kasvaa ja avain-arvot -parit halutaan sijoittaa taulukkoon mahdollisimman tasaisesti.

private void kopioi(Lista<Pari<K, V>>[] uusi, int indeksista) {
    for (int i = 0; i < this.arvot[indeksista].koko(); i++) {
        Pari<K, V> arvo = this.arvot[indeksista].arvo(i);
  
        int hajautusarvo = Math.abs(arvo.getAvain().hashCode() % uusi.length);
        if(uusi[hajautusarvo] == null) {
            uusi[hajautusarvo] = new Lista<>();
        }
  
        uusi[hajautusarvo].lisaa(arvo);
    }
}

Nyt kopioi-metodia voidaan kutsua kasvata-metodista.

private void kasvata() {
    // luodaan uusi taulukko
    Lista<Pari<K, V>>[] uusi = new Lista[this.arvot.length * 2];

    for (int i = 0; i < this.arvot.length; i++) {
        // kopioidaan vanhan taulukon arvot uuteen
        kasvata(uusi, indeksista);
    }

    // korvataan vanha taulukko uudella
    this.arvot = uusi;

Metodissa on pieni virhe. Selvitä mistä virheessä on kyse ja korjaa se.

Lisätään lopuksi kasvatustoiminnallisuus osaksi lisäystoiminnallisuutta. Hajautustaulun kokoa kasvatetaan aina jos hajautustaulussa olevien avain-arvo -parien määrä on yli 75% taulukon koosta.

public void lisaa(K avain, V arvo) {
    Lista<Pari<K, V>> arvotIndeksissa = haeAvaimeenLittyvaLista(avain);
    int indeksi = haeAvaimenIndeksi(arvotIndeksissa, avain);

    if (indeksi < 0) {
        arvotIndeksissa.lisaa(new Pari<>(avain, arvo));
        this.arvoja++;
    } else {
        arvotIndeksissa.arvo(indeksi).setArvo(arvo);
    }

    if (1.0 * this.arvoja / this.arvot.length > 0.75) {
        kasvata();
    }
}

Poistaminen

Lisätään hajautustauluun vielä toiminnallisuus avain-arvo -parin poistamiseen avaimen perusteella. Poistotoiminnallisuus palauttaa null-arvon mikäli arvoa ei löydy, muuten metodi palauttaa poistettavaan avaimeen liittyvän arvon.

Voimme hyödyntää valmiiksi toteuttamiamme metodeja poistotoiminnallisuudessa. Selitä itsellesi (ääneen) alla olevan metodin konkreettinen toiminta.

public V poista(K avain) {
    Lista≪Pari<K, V>> arvotIndeksissa = haeAvaimeenLittyvaLista(avain);
    if (arvotIndeksissa == null || arvotIndeksissa.koko() == 0) {
        return null;
    }

    int indeksi = haeAvaimenIndeksi(arvotIndeksissa, avain);
    if (indeksi < 0) {
        return null;
    }

    Pari<K, V> pari = arvotIndeksissa.arvo(indeksi);
    arvotIndeksissa.poista(pari);
    return pari.getArvo();
}

Hakemisen tehokkuudesta

Tarkastellaan vielä hakemisen tehokkuutta listasta ja hajautustaulusta. Tehokkuusmittauksia voi tehdä metodin System.nanotime() palauttaman nanosekunteja kuvaavan arvon avulla. Ohjelma luo ensin miljoona alkiota hajautustauluun ja listaan, jonka jälkeen hajautustaulusta ja listasta etsitään tuhatta satunnaista arvoa. Noin 50% arvoista löytyy listalta ja hajautustaulusta.

Lista<String> lista = new Lista<>();
Hajautustaulu<String, String> taulu = new Hajautustaulu<>();

for (int i = 0; i < 1000000; i++) {
    lista.lisaa("" + i);
    taulu.lisaa("" + i, "" + i);
}

Lista<String> haettavat = new Lista<>();
Random arpoja = new Random();
for (int i = 0; i < 1000; i++) {
    haettavat.lisaa("" + arpoja.nextInt(2000000));
}

long listanHakuAloitus = System.nanoTime();
for (int i = 0; i < haettavat.koko(); i++) {
    lista.sisaltaa(haettavat.arvo(i));            
}
long listanHakuLopetus = System.nanoTime();
  
long hajautustaulunHakuAloitus = System.nanoTime();
for (int i = 0; i < haettavat.koko(); i++) {
    taulu.hae(haettavat.arvo(i));            
}
long hajautustaulunHakuLopetus = System.nanoTime();

  
long listanHaku = listanHakuLopetus - listanHakuAloitus;
System.out.println("Lista: haku kesti noin " + listanHaku / 1000000 + " millisekuntia (" +
    listanHaku + " nanosekuntia.)");
  
long hajautustaulunHaku = hajautustaulunHakuLopetus - hajautustaulunHakuAloitus;
System.out.println("Hajautustaulu: haku kesti noin " + hajautustaulunHaku / 1000000 +
    " millisekuntia (" + hajautustaulunHaku + " nanosekuntia.)");

Lista: haku kesti noin 6284 millisekuntia (6284420580 nanosekuntia.)
Hajautustaulu: haku kesti noin 0 millisekuntia (805106 nanosekuntia.)

Edellä kuvatut ja kursseilla käyttämämme listat ja hajautustaulut poikkeavat toki sisäiseltä toteutukselta hieman toisistaan. Ohjelmointikielten tarjoamissa tietorakenteissa on hieman enemmän erilaisia optimointeja -- näihinkin palataan myöhemmillä kursseilla. Tämän kurssin puitteissa riittää em. tietorakenteiden käyttöosaaminen sekä jonkintasoinen ymmärrys niiden tehokkuuseroista sekä käyttötapauksista.

Testivetoinen ohjelmistokehitys

Testivetoinen ohjelmistokehitys (Test-driven development) on ohjelmistokehitysprosessi, joka perustuu ohjelman rakentamiseen pienissä osissa. Testivetoisessa ohjelmistokehityksessä ohjelmoija kirjoittaa aina ensin testin. Testi ei mene läpi, sillä testin täyttävä toiminnallisuus puuttuu. Kun testi on kirjoitettu, ohjelmaan lisätään toiminnallisuus, joka täyttää testin vaatimukset. Testit suoritetaan uudestaan, jonka jälkeen -- jos kaikki testit menevät läpi -- lisätään uusi testi tai vaihtoehtoisesti -- jos testit eivät mene läpi -- korjataan aiemmin kirjoitettua ohjelmaa. Ohjelman sisäistä rakennetta korjataan eli refaktoroidaan tarvittaessa siten, että ohjelman toiminnallisuus pysyy samana mutta rakenne selkiytyy.

Rakenne koostuu viidestä askeleesta, joita toistetaan kunnes ohjelman toiminnallisuus on valmis.

• Kirjoita testi. Ohjelmoija päättää, mitä ohjelman toiminnallisuutta testataan, ja kirjoittaa toiminnallisuutta varten testin.
• Suorita testit ja tarkista menevätkö testit läpi. Kun uusi testi on kirjoitettu, testit suoritetaan. Jos testin suoritus päättyy hyväksyttyyn tilaan, testissä on todennäköisesti virhe ja se tulee korjata -- testin pitäisi testata vain toiminnallisuutta, jota ei ole vielä toteutettu.
• Kirjoita toiminnallisuus, joka täyttää testin vaatimukset. Ohjelmoija toteuttaa toiminnallisuuden, joka täyttää vain testin vaatimukset. Huomaa, että tässä ei toteuteta asioita, joita testi ei vaadi -- toiminnallisuutta lisätään vain vähän kerrallaan.
• Suorita testit. Jos testit eivät pääty hyväksyttyyn tilaan, kirjoitetussa toiminnallisuudessa on todennäköisesti virhe. Korjaa toiminnallisuus -- tai, jos toiminnallisuudessa ei ole virhettä -- korjaa viimeksi toteutettu testi.
• Korjaa ohjelman sisäistä rakennetta. Kun ohjelman koko kasvaa, sen sisäistä rakennetta korjataan tarvittaessa. Liian pitkät metodit pilkotaan useampaan osaan ja ohjelmasta eriytetään käsitteisiin liittyviä luokkia. Testejä ei muuteta, vaan niitä hyödynnetään ohjelman sisäiseen rakenteeseen tehtyjen muutosten oikeellisuuden varmistamisessa -- jos ohjelman rakenteeseen tehty muutos muuttaa ohjelman toiminnallisuutta, testit varoittavat siitä, ja ohjelmoija voi korjata tilanteen.

Testiluokka ja ensimmäinen testi

Tarkastellaan tätä prosessia tehtävien hallintaan tarkoitetun sovelluksen kannalta. Tehtävien hallintasovellukseen halutaan mahdollisuus tehtävien listaamiseen, lisäämiseen, tehdyksi merkkaamiseen sekä poistamiseen. Aloitetaan sovelluksen kehitys luomalla tyhjä testiluokka. Asetetaan testiluokan nimeksi TehtavienHallintaTest, ja lisätään se pakkaukseen tehtavat. Tällä hetkellä sovelluksessa ei ole vielä lainkaan toiminnallisuutta.

Luodaan ensimmäinen testi. Testissä määritellään luokka Tehtavienhallinta, ja oletetaan, että luokalla on metodi tehtavalista, joka palauttaa tehtävälistan. Testi tarkastaa, että alussa tehtävälista on tyhjä.

package tehtavat;

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class TehtavienhallintaTest {

    @Test
    public void tehtavalistaAlussaTyhja() {
        Tehtavienhallinta hallinta = new Tehtavienhallinta();
        assertEquals(0, hallinta.tehtavalista().size());
    }
}

Testin suorittaminen epäonnistuu, koska luokkaa Tehtavienhallinta ei ole määritelty.

Ensimmäisen testin vaatimusten täyttäminen

Toteutetaan seuraavaksi toiminnallisuus, joka täyttää testin. Luodaan luokka Tehtavienhallinta ja lisätään luokalle toiminnallisuus, joka täyttää testin vaatimukset. Luokka luodaan NetBeansissa kansioon Source Packages. Nyt projekti näyttää seuraavalta.

Toiminnallisuus on yksinkertainen. Luokalla Tehtavienhallinta on metodi tehtavalista, joka palauttaa tyhjän listan.

package tehtavat;

import java.util.ArrayList;
import java.util.List;

public class Tehtavienhallinta {

    public List<String> tehtavalista() {
        return new ArrayList<>();
    }
}

Testit menevät läpi. Luokan Tehtavienhallinta sisäinen rakenne on vielä niin pieni, ettei siinä ole juurikaan korjattavaa.

Toinen testi

Aloitamme testivetoiseen kehitykseen liittyvän syklin uudestaan. Seuraavaksi luomme uuden testin, jossa tarkastellaan tehtävien lisäämiseen liittyvää toiminnallisuutta. Testissä määritellään luokalle Tehtavienhallinta metodi lisää, joka lisää tehtävälistalle uuden tehtävän. Tehtävän lisäämisen onnistuminen tarkastetaan tehtavalista-metodin koon kasvamisen kautta.

package tehtavat;

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class TehtavienhallintaTest {

    @Test
    public void tehtavalistaAlussaTyhja() {
        Tehtavienhallinta hallinta = new Tehtavienhallinta();
        assertEquals(0, hallinta.tehtavalista().size());
    }

    @Test
    public void tehtavanLisaaminenKasvattaaListanKokoaYhdella() {
        Tehtavienhallinta hallinta = new Tehtavienhallinta();
        hallinta.lisaa("Kirjoita testi");
        assertEquals(1, hallinta.tehtavalista().size());
    }
}

Testit toimi lainkaan, sillä luokasta Tehtavienhallinta puuttuu lisaa-metodi.

Toisen testin vaatimusten täyttäminen

Lisätään luokkaan Tehtavienhallinta metodi lisaa, ja suoritetaan testit.

package tehtavat;

import java.util.ArrayList;
import java.util.List;

public class Tehtavienhallinta {

    public List<String> tehtavalista() {
        return new ArrayList<>();
    }

    public void lisaa(String tehtava) {

    }
}

Nyt testien ajamisesta saadaan seuraava ilmoitus.

Testsuite: tehtavat.TehtavienhallintaTest
Tests run: 2, Failures: 1, Errors: 0, Skipped: 0, Time elapsed: 0.053 sec

Testcase: tehtavanLisaaminenKasvattaaListanKokoaYhdella(tehtavat.TehtavienhallintaTest):	FAILED
expected:<1> but was:<0>
junit.framework.AssertionFailedError: expected:<1> but was:<0>
    at tehtavat.TehtavienhallintaTest.tehtavanLisaaminenKasvattaa...(TehtavienhallintaTest.java:18)

Testit eivät siis mene vieläkään läpi. Muokataan luokan tehtävänhallinta toiminnallisuutta siten, että luokalle luodaan oliomuuttujaksi tehtävät sisältävä lista. Muokataan metodin lisaa-toiminnallisuutta vain niin, että se läpäisee testin, mutta ei tee todellisuudessa haluttua asiaa.

package tehtavat;

import java.util.ArrayList;
import java.util.List;

public class Tehtavienhallinta {

    private List<String> tehtavat;

    public Tehtavienhallinta() {
	this.tehtavat = new ArrayList<>();
    }

    public List<String> tehtavalista() {
	return this.tehtavat;
    }

    public void lisaa(String tehtava) {
	this.tehtavat.add("Uusi");
    }
}

Testit menevät läpi, joten olemme tyytyväisiä ja voimme siirtyä seuraavaan askeleeseen.

Testsuite: tehtavat.TehtavienhallintaTest
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.056 sec

test-report:
test:
BUILD SUCCESSFUL (total time: 0 seconds)

Kolmas testi

Täydennetään testejä siten, että ne vaativat, että lisätyn tehtävän tulee olla listalla. JUnit-kirjaston tarjoama metodi assertTrue vaatii, että metodin palauttama arvo on true.

package tehtavat;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class TehtavienhallintaTest {

    @Test
    public void tehtavalistaAlussaTyhja() {
	Tehtavienhallinta hallinta = new Tehtavienhallinta();
	assertEquals(0, hallinta.tehtavalista().size());
    }

    @Test
    public void tehtavanLisaaminenKasvattaaListanKokoaYhdella() {
	Tehtavienhallinta hallinta = new Tehtavienhallinta();
	hallinta.lisaa("Kirjoita testi");
	assertEquals(1, hallinta.tehtavalista().size());
    }

    @Test
    public void lisattyTehtavaLoytyyTehtavalistalta() {
	Tehtavienhallinta hallinta = new Tehtavienhallinta();
	hallinta.lisaa("Kirjoita testi");
	assertTrue(hallinta.tehtavalista().contains("Kirjoita testi"));
    }
}

Testit eivät mene taaskaan läpi ja ohjelman toiminnallisuutta tulee muokata.

Kolmannen testin vaatimusten täyttäminen

Noheva ohjelmoija muokkaisi luokan Tehtavienhallinta toimintaa siten, että metodissa lisaa lisättäisiin listalle aina merkkijono "Kirjoita testi". Tämä johtaisi tilanteeseen, missä testit menisivät läpi, mutta toiminnallisuus sovellus ei vieläkään tarjoaisi toimivaa tehtävien lisäämistoiminnallisuutta. Muokataan luokkaa Tehtavienhallinta siten, että lisättävä tehtävä lisätään tehtävälistalle.

package tehtavat;

import java.util.ArrayList;
import java.util.List;

public class Tehtavienhallinta {

    private List<String> tehtavat;

    public Tehtavienhallinta() {
	this.tehtavat = new ArrayList<>();
    }

    public List<String> tehtavalista() {
	return this.tehtavat;
    }

    public void lisaa(String tehtava) {
	this.tehtavat.add(tehtava);
    }
}

Nyt testit menevät taas läpi.

Testien refaktorointi

Huomaamme, että testiluokassa on taas jonkinverran toistoa -- siirretään Tehtavienhallinta testiluokan oliomuuttujaksi, ja alustetaan se jokaisen testin alussa.

package tehtavat;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;

public class TehtavienhallintaTest {

    private Tehtavienhallinta hallinta;

    @Before
    public void alusta() {
	hallinta = new Tehtavienhallinta();
    }

    @Test
    public void tehtavalistaAlussaTyhja() {
	assertEquals(0, hallinta.tehtavalista().size());
    }

    @Test
    public void tehtavanLisaaminenKasvattaaListanKokoaYhdella() {
	hallinta.lisaa("Kirjoita testi");
	assertEquals(1, hallinta.tehtavalista().size());
    }

    @Test
    public void lisattyTehtavaLoytyyTehtavalistalta() {
	hallinta.lisaa("Kirjoita testi");
	assertTrue(hallinta.tehtavalista().contains("Kirjoita testi"));
    }
}

Neljäs testi

Lisätään seuraavaksi mahdollisuus tehtävän tehdyksi merkkaamiseen. Mutta! Mitä tarkoittaa tehdyksi merkkaaminen? Alunperin tavoitteena oli luoda ohjelma, joka mahdollistaa tehtävien listaamisen, listaamisen, tehdyksi merkkaamisen sekä poistamisen. Miten tarkastamme onko tehtävä tehty? Jos emme voi tietää onko tehtävä tehty vai ei, voisimme periaatteessa jättää koko toiminnallisuuden huomiotta. Voimme toisaalta päättää miten tehtän tehdyksi määrittely tapahtuu.

Määritellään ensin testi, joka mahdollistaa tehtävän tehdyksi merkkaamiseen.

// ...
@Test
public void tehtavanVoiMerkataTehdyksi() {
    hallinta.lisaa("Satunnainen tehtava");
    hallinta.merkkaaTehdyksi("Satunnainen tehtava");
}
// ..

Neljännen testin vaatimusten täyttäminen

Tehtavienhallintaan lisätään seuraavaksi metodi merkkaaTehdyksi. Metodin toiminnallisuus voi olla aluksi tyhjä, sillä testi vaatii vain kyseisen metodin olemassaolon.

Viides testi

Lisätään tämän jälkeen testi, jonka tehtävänä on tarkistaa onko parametrina annettu tehtävä tehty.

// ...
@Test
public void tehdyksiMerkattuOnTehty() {
    hallinta.lisaa("Uusi tehtava");
    hallinta.merkkaaTehdyksi("Uusi tehtava");
    assertTrue(hallinta.onTehty("Uusi tehtava"));
}
// ..

Viidennen testin vaatimusten täyttäminen

Nyt toiminnallisuutta varten tulee toteuttaa uusi metodi onTehty. Metodi voi aluksi palauttaa aina arvon true. Kokko luokan Tehtavienhallinta sisältö on nyt seuraava.

package tehtavat;

import java.util.ArrayList;
import java.util.List;

public class Tehtavienhallinta {

    private List<String> tehtavat;

    public Tehtavienhallinta() {
	this.tehtavat = new ArrayList<>();
    }

    public List<String> tehtavalista() {
	return this.tehtavat;
    }

    public void lisaa(String tehtava) {
	this.tehtavat.add(tehtava);
    }

    public void merkkaaTehdyksi(String tehtava) {

    }

    public boolean onTehty(String tehtava) {
	return true;
    }
}

Testit menevät taas läpi.

Kuudes testi

Seuraavaksi toteutettava testi on oleellinen tehtävän toiminnan kannalta. Olemme tähän mennessä tarkistaneet, että haluttu toiminnallisuus on olemassa, mutta emme ole juurikaan tarkastaneet epätoivotun toiminnan poissaoloa. Jos testejä kirjoitettaessa keskitytään halutun toiminnallisuuden olemassaoloon, testit saattavat jäädä ohjelman toiminnallisuutta hyvin vähän tarkastelevaksi.

Kirjoitetaan seuraavaksi testi, joka tarkastaa, että tekemättömäksi merkkaamaton testi ei ole tehty.

    // ...
    @Test
    public void tehdyksiMerkkaamatonEiOleTehty() {
	hallinta.lisaa("Uusi tehtava");
	hallinta.merkkaaTehdyksi("Uusi tehtava");
	assertFalse(hallinta.onTehty("Joku tehtava"));
    }
    // ..

Kuudennen testin vaatimusten täyttäminen

Joudumme nyt muokkaamaan luokan Tehtavienhallinta toiminnallisuutta hieman enemmän. Lisätään luokkaan erillinen lista tehtäville, jotka on merkattu tehdyiksi.

package tehtavat;

import java.util.ArrayList;
import java.util.List;

public class Tehtavienhallinta {

    private List<String> tehtavat;
    private List<String> tehdytTehtavat;

    public Tehtavienhallinta() {
	this.tehtavat = new ArrayList<>();
	this.tehdytTehtavat = new ArrayList<>();
    }

    public List<String> tehtavalista() {
	return this.tehtavat;
    }

    public void lisaa(String tehtava) {
	this.tehtavat.add(tehtava);
    }

    public void merkkaaTehdyksi(String tehtava) {
	this.tehdytTehtavat.add(tehtava);
    }

    public boolean onTehty(String tehtava) {
	return this.tehdytTehtavat.contains(tehtava);
    }
}

Testit menevät taas läpi. Sovelluksessa on muutamia muitakin kysymysmerkkejä. Pitäisikö tehtavalistauksessa palautetut tehtävät merkitä jollain tavalla tehdyksi? Voiko tehtävän, joka ei ole tehtävälistalla tosiaankin merkata tehdyksi?

Refaktorointi ja käsite "Tehtävä"

Tehdään ensimmäinen hieman laajempi ohjelman sisäisen rakenteen korjaus. Tehtävä on selkeästi käsite, joten sille kannattanee luoda oma erillinen luokka. Luodaan luokka Tehtava. Luokalla Tehtava on nimi sekä tieto siitä, onko tehtävä tehty.

package tehtavat;

public class Tehtava {

    private String nimi;
    private boolean tehty;

    public Tehtava(String nimi) {
	this.nimi = nimi;
	this.tehty = false;
    }

    public String getNimi() {
	return nimi;
    }

    public void setTehty(boolean tehty) {
	this.tehty = tehty;
    }

    public boolean onTehty() {
	return tehty;
    }

}

Muokataan tämän jälkeen luokan Tehtavienhallinta sisäistä rakennetta siten, että luokka tallentaa tehtävät merkkijonojen sijaan Tehtava-olioina. Huomaa, että luokan metodien määrittelyt eivät muutu, mutta niiden sisäinen toteutus muuttuu.

package tehtavat;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Tehtavienhallinta {

    private List<Tehtava> tehtavat;

    public Tehtavienhallinta() {
	this.tehtavat = new ArrayList<>();
    }

    public List<String> tehtavalista() {
        return this.tehtavat.stream()
            .map(t -> t.getNimi()).collect(Collectors.toList());
    }

    public void lisaa(String tehtava) {
	this.tehtavat.add(new Tehtava(tehtava));
    }

    public void merkkaaTehdyksi(String tehtava) {
        this.tehtavat.stream()
            .filter(t -> t.getNimi().equals(tehtava)).forEach(t -> {
                t.setTehty(true);
	    });
    }

    public boolean onTehty(String tehtava) {
	return this.tehtavat.stream()
	    .filter(t -> t.getNimi().equals(tehtava))
	    .filter(t -> t.onTehty()).count() > 0;
    }
}

Vaikka tehty muutos muutti luokan Tehtavienhallinta sisäistä toimintaa merkittävästi, testit toimivat yhä. Sykli jatkuisi samalla tavalla kunnes toivottu perustoiminnallisuus olisi paikallaan.

Sovelluksen käytettävyys

Yksikkötestaus on vain osa ohjelmistojen testaamiseen liittyvää työtä. Tärkein sovelluksen testaamisen liittyvä ihmisryhmä on sovelluksen käyttäjät. Käyttäjät toimivat ohjelman parissa ja huomaavat toiminnassa esiintyviä puutteita.

Sovelluksen käytettävyyteen liittyy useita erilaisia näkökulmia, joista osa on standardoitu. Käytettävyyden kannalta oleellisia ominaisuuksia ovat muunmuassa:

• Tavoitteiden saavuttaminen. Ohjelmiston käyttäjillä on tavoitteita, joita ohjelmiston avulla halutaan saavuttaa. Miten hyvin ohjelmisto auttaa käyttäjiä saavuttamaan tavoitteensa? Miten tehokkaasti käyttäjät saavuttavat tavoitteensa? Joutuvatko he käyttämään liikaa aikaa tavoitteiden saavuttamiseen? Voisiko tätä helpottaa sovelluksen suunnittelussa?
• Tyytyväisyys sovelluksen toimintaan. Miten tyytyväisiä käyttäjät ovat sovelluksen toimintaan? Onko sovelluksen käyttö sujuvaa?
• Ohjelmiston käytön oppiminen. Kuinka nopeasti ohjelmiston käyttö on opittavissa? Minkälaisia ohjeita sovelluksen käyttö vaatii? Tarjoaako ohjelmisto näitä ohjeita? Kuinka hyvin käyttäjä muistaa miten sovellusta käytetään?
• Virhealttius. Kuinka paljon käyttäjä tekee virheitä sovellusta käyttäessään? Voisiko virheiden määrää vähentää?

Käytettävyyden lisäksi sovelluksissa oleellista on myös saavutettavuus, millä tarkoitetaan erilaisten käyttäjäryhmien huomiointia sovelluksen rakentamisessa. Näitä käsitellään tarkemmin Human-Computer Interaction -teeman kursseilla (Ihmisen ja tietokoneen välinen vuorovaikutus).

Finito

2 0 2 0
0 0 0 1
0 1 0 0
0 0 0 0
> o

0 0 0 4
0 0 0 1
0 0 0 1
0 1 0 0
  

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

> o
0 0 0 1
0 0 0 0
0 0 0 0
0 1 0 0

> o
0 0 0 1
0 0 0 0
0 0 0 1
0 0 0 1

> a
0 0 0 0
0 0 0 0
1 0 0 2
0 0 0 1

> a
1 0 0 0
0 0 0 0
0 0 0 2
1 0 0 1

> v
1 0 0 0
0 0 0 0
2 0 0 0
2 1 0 0

> y
1 1 0 0
4 0 0 0
0 0 0 0
0 1 0 0

> v
2 0 0 0
4 0 0 0
0 0 0 0
1 0 1 0

> v
2 0 0 0
4 1 0 0
0 0 0 0
2 0 0 0

>
  

1 1 1 1
1 1 0 1
1 1 1 0
1 0 1 1

> o
0 0 0 4
0 0 1 2
0 0 1 2
0 0 1 2
  

1 0 0 1
0 1 0 1
2 2 4 0
0 1 0 0

> o
0 0 0 2
0 0 0 2
0 0 0 8
0 0 0 1
  

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

> o
0 0 0 1
0 0 0 0
0 0 0 1
0 0 0 0

> y
0 0 0 2
1 0 0 0
0 0 0 0
0 0 0 0

> v
2 0 1 0
1 0 0 0
0 0 0 0
0 0 0 0

> o
0 0 2 1
0 0 0 1
0 1 0 0
0 0 0 0

> y
0 1 2 2
0 0 0 0
0 0 0 0
0 0 1 0

> o
0 0 1 4
0 0 0 0
0 0 0 1
0 0 0 1

> x