Tehtävät
Kuudennen osion tavoitteet

Osan jälkeen osaat lukea merkkijonomuodossa olevaa tietoa tiedostoista ja verkosta. Osaat käsitellä yksi- ja useampiulotteisia taulukoita, ja ymmärrät miten taulukot käyttävät tilaa tietokoneen muistissa. Indeksien käyttö on myös tullut yhä tutummaksi, ja osaat muitakin toistolauseita kuin while-toistolauseen. Tunnet myös ainakin yhden järjestämisalgoritmin ja hakualgoritmin, sekä tiedät miten Javan omia järjestämiseen tarkoitettuja apuvälineitä käytetään.

Huom! Jos teet Helsingin yliopiston Ohjelmoinnin perusteet -kurssia tai aikataulutettua MOOCia, tee toinen konekoe ennen tämän osion aloittamista.

Tiedon lukeminen

Merkittävä osa ohjelmistoista perustuu tavalla tai toisella tiedon käsittelyyn. Musiikin toistoon tarkoitetut ohjelmistot käsittelevät musiikkitiedostoja, kuvankäsittelyohjelmat käsittelevät kuvatiedostoja, ja verkossa ja mobiililaitteissa toimivat sovellukset kuten Facebook ja WhatsApp käsittelevät muunmuassa tietokantoihin tallennettuja henkilötietoja. Kaikissa näistä sovelluksista on yhteistä tiedon lukeminen sekä sen käsittely tavalla tai toisella.

Tutustutaan seuraavaksi erilaisiin tapoihin tiedon lukemiseen. Ensin käsittelemme jo tutuksi tullutta näppäimistöltä lukemista osana tekstikäyttöliittymää, jonka jälkeen tutustumme tiedon lukemiseen tiedostosta. Tämän jälkeen käsittelemme lyhyesti myös tiedon hakemista verkkoyhteyden. Tiedon lukeminen tietokannoista sekä tiedon lukeminen ja käsittely osana graafista käyttöliittymää tulee kurssilla tutuksi myöhemmin.

Lukeminen näppäimistöltä

Olemme käyttäneet Scanner-luokkaa näppäimistöllä kirjoitetun syötteen lukemiseen kurssin alusta lähtien. Tyypillinen tiedon lukemiseen käytetty runko on ollut while-true -toistolause, missä lukeminen lopetetaan tietynlaiseen käyttäjän kirjoittamaan merkkiin.

// luodaan Scanner-olio, joka lukee näppäimistösyötettä
Scanner lukija = new Scanner(System.in);

// jatketaan syötteen lukemista kunnes käyttäjä syöttää
// rivin "loppu"
while (true) {
    String rivi = lukija.nextLine();

    if (rivi.equals("loppu")) {
        break;
    }

    // lisää luettu rivi myöhempää käsittelyä varten
    // tai käsittele rivi
}

// käsittele myöhempää käsittelyä varten lisätyt rivit

Yllä olevassa esimerkissä Scanner-luokan konstruktorille annetaan parametrina järjestelmän syöte (System.in). Tekstikäyttöliittymissä käyttäjän kirjoittama tieto ohjataan syötevirtaan rivi kerrallaan, eli tieto lähetetään käsiteltäväksi aina kun käyttäjä painaa rivinvaihtoa.

Lukeminen tiedostosta

Tiedostot ovat tietokoneella sijaitsevia tietokokoelmia, jotka voivat sisältää vaikkapa tekstiä, kuvia, musiikkia tai niiden yhdistelmiä. Tiedoston tallennusmuoto määrittelee tiedoston sisällön sekä tavan tiedon lukemiseen. Esimerkiksi PDF-tiedostoja luetaan PDF-tiedostojen lukemiseen soveltuvalla ohjelmalla, ja musiikkitiedostoja luetaan musiikkitiedostojen lukemiseen soveltuvalla ohjelmalla. Jokainen näistä ohjelmista on ihmisen luoma, ja ohjelman luoja tai luojat -- eli ohjelmoijat -- ovat osana työtään myös määritelleet tiedoston tallennusmuodon.

Tiedoston lukeminen tapahtuu Javan valmiin Files-apukirjaston avulla. Apukirjaston tarjoaman metodin lines avulla tiedostosta voidaan luoda syötevirta, jonka käsittely onnistuu edellisessä osiossa tutuiksi tulleilla menetelmillä. Metodi lines saa patametrikseen polun, joka luodaan apukirjaston Paths tarjoamalla metodilla get, jolle annetaan parametrina tiedostopolkua kuvaava merkkijono.

Alla olevassa esimerkissä luetaan tiedoston "tiedosto.txt" kaikki rivit, jotka lisätään ArrayList-listaan. Tiedostoja lukiessa voidaan kohdata virhetilanne, joten tiedoston lukeminen vaatii erillisen "yrittämisen" (try) sekä mahdollisen virheen kiinnioton (catch). Palaamme virhetilanteiden käsittelyyn tarkemmin myöhemmin kurssin aikana.

ArrayList<String> rivit = new ArrayList<>();

try {
    Files.lines(Paths.get("tiedosto.txt")).forEach(rivi -> rivit.add(rivi));
} catch (Exception e) {
  System.out.println("Virhe: " + e.getMessage());
}

// tee jotain luetuilla riveillä

Jos tiedosto löytyy ja sen lukeminen onnistuu, tulee ohjelman suorituksen lopussa tiedoston "tiedosto.txt" rivit olemaan listamuuttujassa rivit. Jos taas tiedostoa ei löydy, tai sen lukeminen epäonnistuu, ilmoitetaan tästä virheviestillä. Alla eräs mahdollisuus:

Virhe: tiedosto.txt (No such file or directory)

Edellä mainitun lähestymistavan lisäksi tiedoston lukemiseen voi käyttää myös tutuksi tullutta Scanner-luokkaa. Scanner-luokan konstruktorille voi antaa parametrina myös tiedosto-olion, jolloin Scanner-oliota käytetään kyseisen tiedoston sisällön lukemiseen. Lukeminen tapahtuu while-toistolauseella, jota jatketaan niin pitkään kuin Scanner-olion käsittelemässä tiedostossa on vielä lukemattomia rivejä jäljellä.

ArrayList<String> rivit = new ArrayList<>();

// luodaan lukija tiedoston lukemista varten
try (Scanner lukija = new Scanner(new File("tiedosto.txt"))) {

  // luetaan kaikki tiedoston rivit
  while (lukija.hasNextLine()) {
    rivit.add(lukija.nextLine());
  }
} catch (Exception e) {
  System.out.println("Virhe: " + e.getMessage());
}

// tee jotain luetuilla riveillä

Tehtäväpohjassa tulee kaksi tekstitiedostoa: nimet.txt ja toiset-nimet.txt. Kirjoita ohjelma, joka kysyy ensin käyttäjältä luettavan tiedoston nimeä, jonka jälkeen käyttäjältä kysytään etsittävää merkkijonoa. Tämän jälkeen ohjelma lukee tiedoston ja etsii tiedostosta haluttua merkkijonoa.

Jos merkkijono löytyy, ohjelman tulee tulostaa "Löytyi!". Jos merkkijonoa ei löydy, ohjelman tulee tulostaa "Ei löytynyt.". Jos tiedoston lukeminen epäonnistuu (lukeminen päätyy virhetilanteeseen), ohjelman tulee tulostaa viesti "Tiedoston lukeminen epäonnistui.".

Minkä niminen tiedosto luetaan? 
nimet.txt
Mitä etsitään?
Antti
Ei löytynyt.
Minkä niminen tiedosto luetaan? 
nimet.txt
Mitä etsitään?
ada
Löytyi!
Minkä niminen tiedosto luetaan? 
olematon.txt
Mitä etsitään?
testi
Tiedoston olematon.txt lukeminen epäonnistui.

Tehtäväpohjassa on valmiina toiminnallisuus vieraslistaohjelmaan, missä käyttäjän syöttämien nimien olemassaolo tarkistetaan vieraslistalta.

Ohjelmasta puuttuu kuitenkin toiminnallisuus vieraslistan lukemiseen. Muokkaa ohjelmaa siten, että vieraslistan nimet luetaan tiedostosta.

Minkä niminen tiedosto luetaan?
vieraslista.txt

Syötä nimiä, tyhjä rivi lopettaa.
Chuck Norris
Nimi ei ole listalla.
Jack Baluer
Nimi ei ole listalla.
Jack Bauer
Nimi on listalla.
Jack Bower
Nimi on listalla.

Kiitos!

Huom! Tehtäväpohjassa on mukana kaksi tiedostoa, nimet.txt ja toiset-nimet.txt, joiden sisällöt ovat seuravat. Älä muuta näiden tiedostojen sisältöä!

nimet.txt:

ada
arto
leena
testi

toiset-nimet.txt:

leo
jarmo
alicia

Toteuta ohjelma, joka lukee käyttäjältä tiedoston nimen sekä hyväksyttävien lukujen ala- ja ylärajan. Tämän jälkeen ohjelma lukee tiedoston sisältämät luvut (jokainen luku on omalla rivillään) ja ottaa huomioon vain ne luvut, jotka ovat annetulla lukuvälillä. Lopulta ohjelma tulostaa annetulla lukuvälillä olleiden lukujen lukumäärän.

Tiedosto? mittaukset-1.txt
Alaraja? 15
Yläraja? 20
Lukuja: 2
Tiedosto? mittaukset-1.txt
Alaraja? 0
Yläraja? 300
Lukuja: 4

Huom! Tehtäväpohjassa on mukana kaksi tiedostoa, mittaukset-1.txt ja mittaukset-2.txt, joiden sisällöt ovat seuravat. Älä muuta näiden tiedostojen sisältöä.

mittaukset-1.txt:

300
9
20
15

mittaukset-2.txt:

123
-5
12
67
-300
1902

Lukeminen verkkoyhteyden yli

Lähes kaikki verkkosivut, kuten tämäkin oppimateriaali, voidaan lukea tekstimuodossa ohjelmallista käsittelyä varten. Scanner-oliolle voi antaa konstruktorin parametrina oikeastaan lähes minkälaisen syötevirran tahansa. Alla olevassa esimerkissä luodaan URL-olio annetusta web-osoitteesta, pyydetään siihen liittyvää tietovirtaa, ja annetaan se juuri luotavalle Scanner-oliolle luettavaksi.

ArrayList<String> rivit = new ArrayList<>();

// luodaan lukija web-osoitteen lukemista varten
try (Scanner lukija = new Scanner(new URL("http://www.cs.helsinki.fi/home/").openStream())) {

  // luetaan osoitteesta http://www.cs.helsinki.fi/home/
  // saatava vastaus 
  while (lukija.hasNextLine()) {
    rivit.add(lukija.nextLine());
  }
} catch (Exception e) {
  System.out.println("Virhe: " + e.getMessage());
}

// tehdään jotain vastauksella

Web-selain on oikeastaan ohjelma siinä missä muutkin ohjelmat. Toisin kuin yllä toteutettu sivun sisällön lataaja, web-selaimeen on toteutettu toiminnallisuus vastauksena tulevan HTML-muotoisen lähdekoodin tulkisemiseen ja graafisessa käyttöliittymässä näyttämiseen.

Osoitteessa http://www.icndb.com/api/ sijaitsee web-sovellus, joka tarjoaa Chuck Norris -vitsejä kaikkien vapaaseen käyttöön.

Sovellus tarjoaa muunmuassa mahdollisuuden satunnaisten vitsien hakemiseen (osoite http://api.icndb.com/jokes/random) sekä vitsien hakemiseen niihin liittyvillä numeerisilla tunnuksilla (osoite http://api.icndb.com/jokes/tunnus, missä tunnus on kokonaisluku).

Toteuta sovellus, joka tarjoaa kolme toimintoa. Jos käyttäjä kirjoittaa "lopeta", ohjelman suoritus lopetetaan. Jos käyttäjä kirjoittaa "satunnainen", ohjelma tulostaa icndb-palvelusta noudetun satunnaisen chuck norris vitsin. Jos käyttäjä kirjoittaa "vitsi numero", missä numero on kokonaisluku, ohjelma tulostaa icndb-palvelusta noudetun tietyn vitsin.

Huom! Tässä tehtävässä riittää tulostaa palvelun palauttama merkkijono kokonaisuudessaan. Merkkijono voi olla esimerkiksi muotoa { "type": "success", "value": { "id": 341, "joke": "Chuck Norris sleeps with a pillow under his gun.", "categories": [] } }.

Ohjelmassa ei ole testejä, eli testit eivät ota kantaa sovelluksen rakenteeseen tai tulostuksen ulkoasuun. Palauta sovellus kun se on mielestäsi valmis.

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]);

Tehtäväpohjaan on toteutettu valmiiksi ohjelma, missä luodaan taulukko sekä tulostetaan taulukon arvot kahteen kertaan. Muokkaa ohjelmaa siten, että sen jälkeen kun taulukon arvot on tulostettu ensimmäiseen kertaan, käyttäjältä kysytään kahta indeksiä, joiden osoittamat arvot vaihdetaan taulukossa päittäin. Tämän jälkeen alkiot tulee vaihtaa päittäin ja taulukon arvot tulostaa toiseen kertaan.

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

Voit olettaa, että käyttäjän syöttämät indeksit löytyvät taulukosta.

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.

Tehtäväpohjassa on valmiina taulukko, joka sisältää lukuja. Täydennä ohjelmaa siten, että käyttäjältä kysyttyä lukua etsitään taulukosta. Jos luku löytyy taulukosta, ohjelma kertoo luvun indeksin. Jos lukua taas ei löydy taulukosta, ohjelma kertoo ettei lukua löydy.

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;

Tietokoneella voi olla samaan aikaan käynnissä useita ohjelmia, mutta todellisuudessa kaikkien käynnissä olevien ohjelmien lähdekoodia ei suoriteta samaan aikaan. Tietokoneen käyttöjärjestelmä vaihtaa suoritettavaa ohjelmaa jatkuvasti, minkä kautta käyttäjälle tulee illuusio siitä, että ohjelmat olisivat samaan aikaan käynnissä.

Round-robin -algoritmia käytetään tietokoneen ohjelmien aikatauluttamiseen.

Algoritmin toimintaperiaate on yksinkertainen. Ohjelmista luodaan jono, ja ensimmäisenä jonossa olevaa ohjelmaa suoritetaan hetki, jonka jälkeen suoritettavana ollut ohjelma siirretään jonon perälle. Tämän jälkeen seuraava jonossa ollut ohjelma -- nyt jonon ensimmäinen -- päätyy suoritettavaksi, jonka jälkeen se siirretään jonon perälle jne.

Tehtäväpohjassa on viisi lukua sisältävä taulukko sekä ohjelmarunko niiden käsittelyyn. Ohjelmarunko tuntee tällä hetkellä kaksi komentoa: "lopeta" lopettaa ohjelman suorituksen ja "tulosta" tulostaa taulukon arvot.

Lisää ohjelmaan komento "siirra", joka siirtää ensimmäisenä taulukossa olevan arvon taulukon perälle sekä kaikkia muita taulukon arvoja yhden paikan eteenpäin.

tulosta    
1 3 5 7 9
siirra    
tulosta    
3 5 7 9 1
siirra    
siirra
tulosta    
7 9 1 3 5
lopeta    
Indekseistä ja muistin rakenteesta

Jokaisen ohjelmoijan on hyvä ymmärtää hieman tietokoneohjelman käytössä olevan muistin rakenteesta. Jokainen muuttuja -- on se sitten alkeistyyppinen tai viittaustyyppinen muuttuja -- tallennetaan muistiin. Jokaisella muuttujalla on myös koko, eli tietty määrä bittejä (nollia ja ykkösiä), jonka muuttuja vie muistista. Muuttujan arvo esitetään myös bitteinä.

Taulukko-olion arvo on viite eli oikeastaan tieto muistipaikasta, missä olion tiedot ovat. Sanomalla taulukko[0] viitataan taulukon ensimmäiseen alkioon. Lausekkeen taulukko[0] voi lukea muodossa "mene taulukon alkuun ja siirry eteenpäin 0 kertaa taulukon sisältämän muuttujan koko -- anna siitä kohdasta eteenpäin muuttujan koon verran tietoa". Vastaavasti taulukko[2] voidaan lukea muodossa "mene taulukon alkuun ja siirry eteenpäin 2 kertaa taulukon sisältämän muuttujan koko -- anna siitä kohdasta eteenpäin muuttujan koon verran tietoa".

Javassa int-tyyppinen muuttuja on 32-bitin kokoinen ja se voi esittää korkeintaan 232-1 kokoista lukua. Kun luodaan int-taulukko, jossa on esimerkiksi 4 paikkaa, muistista varataan kokonaislukuja varten 4*32 bittiä. Sanomalla int-tyyppiselle taulukolle taulukko[2], luetaan 32 bittiä alkaen kohdasta taulukon alku + 2 * 32 bittiä.

Osa ohjelmointikielistä pyrkii varmistamaan, ettei ohjelmoija mene "väärälle alueelle". Jos Java ei aiheuttaisi virhettä sanoessamme taulukko[-1], saisimme tietoomme ohjelman muistissa juuri ennen taulukkoa olevan tiedon. Kukaan ei tällöin myöskään estäisi kirjoittamasta ohjelmaa, joka lukisi kaiken ohjelman muistissa olevan tiedon ja lähettäisi sen eteenpäin.

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ä.

Täydennä luokassa Summaaja olevaa metodia public int laskeTaulukonLukujenSumma(int[] taulukko) siten, että se laskee ja palauttaa sille parametrina annetussa taulukossa olevien lukujen summan.

Voit kokeilla lukujen summan laskemista esimerkiksi seuraavalla esimerkkikoodilla.

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

Täydennä luokassa Tulostin olevaa metodia public void tulostaTaulukkoTahtina(int[] taulukko), siten, että se tulostaa jokaista taulukossa olevaa lukua vastaavan pituisen rivin tähtiä.

Voit kokeilla tulostusta esimerkiksi seuraavalla esimerkkikoodilla.

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);
    }
}
*****
*
***
****
**

Eli koska taulukon nollannessa paikassa on luku 5, tulee ensimmäiselle riville 5 tähteä. Seuraavalla 1 tähti jne.

Täydennä luokan TaulukonTulostaja metodia public void tulostaTyylikkaasti(int[] taulukko) siten, että metodi tulostaa parametrina saamansa taulukon luvut tyylikkäästi. Lukujen väliin tulee pilkku ja välilyönti. Viimeisen luvun jälkeen ei pilkkua tule.

Voit kokeilla tulostusta esimerkiksi seuraavalla esimerkkikoodilla.

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.

Täydennä luokassa LukujenKasvattaja olevaa metodia public void kasvata(int[] taulukko, int paljonko) siten, että se kasvatta jokaista parametrina saadun taulukon alkiota toisena parametrina saadun luvun arvolla.

Voit kokeilla kasvatusta esimerkiksi seuraavalla esimerkkikoodilla.

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++;
}

Kopiointi

Tee luokkaan Taulukot metodi public int[] kopioi(int[] taulukko) joka luo kopion parametrina saadusta taulukosta. Vihje: koska metodin on luotava taulukosta kopio, tulee metodin sisällä luoda uusi taulukko ja kopioida vanhan taulukon sisältö uudelle taulukolle alkio alkiolta.

Seuraavassa esimerkki metodin käytöstä (koodissa myös Arrays-luokan tarjoama kätevä apuväline taulukon sisällön tulostamiseen):

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));
}

Kuten tulostuksesta huomaa, ei kopioon tehty muutos vaikuta alkuperäiseen:

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

Kääntäminen

Tee luokkaan Taulukot metodi public int[] kaanna(int[] taulukko), joka luo käänteisessä järjestyksessä olevan kopion parametrinaan saamastaan taulukosta.

Eli jos parametrina on taulukko jossa esim. luvut 5, 6, 7 palauttaa metodi uuden taulukon jonka sisältönä luvut 7, 6, 5. Parametrina oleva taulukko ei saa muuttua.

Seuraavassa esimerkki metodin käytöstä:

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));
}

Tulostuksesta pitäisi selvitä, että alkuperäinen taulukko on muuttumaton:

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 on tietorakenne, joka tarjoaa oleellisesti kaksi toimintoa. Pinoon voidaan lisätä tietoa ja siitä voidaan ottaa tietoa. Pinoon lisääminen lisää alkion aina pinon päälle, ja ottaminen poistaa ja palauttaa pinon päällimmäisen arvon.

Pino-tietorakenne on lähes valmiiksi toteutettuna tehtäväpohjassa mukana tulevaan luokkaan Pino. Siinä on kuitenkin pieni pulma: pinon koko on rajattu. Muokkaa pinon metodia public void kasvata() siten, että sitä kutsuttaessa pinon kapasiteetti kasvaa viidellä. Tee siis niin, että luot uuden taulukon, jossa on 5 paikkaa enemmän kuin vanhassa ja kopioit vanhan taulukon arvot uuteen. Vaihda tämän jälkeen käytössä oleva taulukko kopioon.

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.

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ä.

Game of Life on neljää yksinkertaista sääntöä seuraava soluautomaatti:

  1. Jos elävän solun naapureina on alle kaksi elävää solua, se kuolee alikansoituksen takia.
  2. Jos elävän solun naapureina on kaksi tai kolme elävää solua, se jää henkiin.
  3. Jos elävän solun naapureina on yli kolme elävää solua, se kuolee ylikansoituksen takia.
  4. Jos kuolleen solun naapureina on tasan kolme elävää solua, se syntyy eli muuttuu eläväksi.

Peli ei sisällä minkäänlaisia liikkumissääntöjä, mutta se silti luo tilanteita, missä erilaiset hahmot liikkuvat ruudulla. Katso pelin keksineen John Conwayn mietteitä pelistä sekä sääntöjen selitys.

Tässä tehtävässä toteutetaan oleellisilta osin Game of Life-pelin säännöt. Toteutusta varten tehtäväpohjassa on luokka GameOfLife, joka sisältää kaksiulotteisen taulukon, sekä luokka GameOfLifeSovellus, jota voidaan käyttää pelin visualisointiin.

Elossa olevien naapurien lukumäärä

Täydennä luokassa GameOfLife olevaa metodia public int elossaOleviaNaapureita(int[][] taulukko, int x, int y) siten, että se laskee annetun x, y -koordinaatin elossa olevien naapureiden lukumäärän. Naapuri on elossa jos sen arvo on 1.

Naapureita ovat kaikki ne alkiot, jotka ovat kulman tai sivun kautta yhteydessä alkioon.

Huomaa, että metodin tulee varoa ArrayIndexOutOfBounds-virhettä. Indeksissä -1 ei esimerkiksi voi olla ketään. Vastaavasti taulukon leveyden tai korkeuden yli ei voi mennä (esim. taulukko[taulukko.length][0] tai taulukko[0][taulukko[0].length]).

Voit kokeilla metodiasi muunmuassa seuraavilla esimerkeillä.

GameOfLife gol = new GameOfLife(3, 3);
  
int[][] taulukko = new int[3][3];
taulukko[0][0] = 1;
taulukko[0][1] = 1;
taulukko[1][1] = 1;
taulukko[2][2] = 1;

System.out.println(gol.elossaOleviaNaapureita(taulukko, 0, 0));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 1, 0));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 1, 1));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 2, 2));
2
3  
3
1
GameOfLife gol = new GameOfLife(4, 4);

int[][] taulukko = {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}};

System.out.println(gol.elossaOleviaNaapureita(taulukko, 0, 0));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 1, 1));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 2, 2));
System.out.println(gol.elossaOleviaNaapureita(taulukko, 3, 3));
3
7
5
1

Kehittyminen

Täydennä seuraavaksi GameOfLife-luokan metodia public void kehity() siten, että se käy yhden Game of Life -pelin askeleen.

Toteuta toiminnallisuus niin, että luot toisen taulukon, jonka koko on sama kuin alkuperäisen taulukon. Käy tämän jälkeen alkuperäistä taulukkoa läpi alkio alkiolta siten, että seuraat seuraavia sääntöjä:

  1. Jos alkuperäisen taulukon alkion arvo on 1 ja sillä on alle kaksi elävää naapuria, kopioon asetetaan alkion arvoksi 0.
  2. Jos alkuperäisen taulukon alkion arvo on 1 ja sillä on kaksi tai kolme elävää naapuria, kopioon asetetaan alkion arvoksi 1.
  3. Jos alkuperäisen taulukon alkion arvo on 1 ja sillä on yli kolme elävää naapuria, kopioon asetetaan alkion arvoksi 0.
  4. Jos alkuperäisen taulukon alkion arvo on 0 ja sillä on tasan kolme elävää naapuria, kopioon asetetaan alkion arvoksi 1.

Käytä naapureiden lukumäärän selvittämisessä edellisessä osassa tehtyä metodia. Kun olet käynyt koko taulukon läpi, vaihda kopio taulukon paikalle.

Kokeile tämän jälkeen sovelluksen toimintaa graafisen käyttöliittymän kautta. Sovelluksen pitäisi käynnistyä -- yksi mahdollinen hetkellinen tila on seuraavanlainen.

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);
    }
}

Kirjoita ohjelma, joka tulostaa kaikki mahdolliset nelilukuiset PIN-koodit.

0000
0001
0002
0003
... paljon rivejä välissä ...
9996
9997
9998
9999

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.

Pienimmän arvon etsiminen

Tee luokkaan Valintajarjestaminen metodi pienin, joka palauttaa metodille parametrina annetun kokonaislukutaulukon pienimmän luvun.

Metodin runko on seuraava:

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

Seuraava esimerkki esittelee metodin toimintaa:

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

Pienimmän arvon indeksi

Tee luokkaan Valintajarjestaminen metodi pienimmanIndeksi, joka palauttaa sille parametrina annetun taulukon pienimmän luvun indeksin.

Metodin runko on seuraava:

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

Seuraava koodi esittelee metodin toimintaa:

// 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

Taulukon pienin luku on 5, ja sen indeksi eli sijaintipaikka taulukossa on 1. Muistathan, että taulukon numerointi alkaa 0:sta.

Pienimmän arvon indeksi taulukon loppuosassa

Tee luokkaan Valintajarjestaminen metodi pienimmanIndeksiAlkaen, joka toimii samalla tavalla kuin edellisen tehtävän metodi, mutta ottaa huomioon vain taulukon loppuosan jostain indeksistä alkaen. Metodille annetaan parametrina taulukon lisäksi aloitusindeksi, josta lähtien pienintä lukua etsitään.

Metodin runko on seuraava:

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

Seuraava koodi esittelee metodin toimintaa:

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

Esimerkissä ensimmäinen metodikutsu etsii pienimmän luvun indeksin aloittaen indeksistä 0. Indeksistä 0 alkaen pienin luku on -1, ja sen indeksi on 0. Toinen metodikutsu etsii pienimmän luvun indeksiä indeksistä 1 aloittaen. Tällöin pienin luku on 6, ja sen indeksi on 1. Kolmas kutsu etsii pienimmän luvun indeksiä aloittaen indeksistä 2. Indeksistä 2 alkaen pienin luku on 8, ja sen indeksi on 3.

Lukujen vaihtaminen

Tee luokkaan Valintajarjestaminen metodi vaihda, jolle annetaan taulukko ja kaksi sen indeksiä. Metodi vaihtaa indekseissä olevat luvut keskenään.

Metodin runko on seuraava:

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

Seuraavassa estellään metodin toimintaa. Taulukon tulostamisessa käytetään apuna taulukon merkkijonoksi muotoilevaa Arrays.toString-metodia:

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]

Järjestäminen

Nyt koossa on joukko hyödyllisiä metodeja, joiden avulla voimme toteuttaa järjestämisalgoritmin nimeltä valintajärjestäminen.

Valintajärjestämisen idea on seuraava:

  • Siirretään taulukon pienin luku indeksiin 0.
  • Siirretään taulukon toiseksi pienin luku indeksiin 1.
  • Siirretään taulukon kolmanneksi pienin luku indeksiin 2.
  • Jne.

Toisin sanoen:

  • Tarkastellaan taulukkoa indeksistä 0 alkaen. Vaihdetaan keskenään indeksissä 0 oleva luku sekä taulukon pienin luku indeksistä 0 alkaen.
  • Tarkastellaan taulukkoa indeksistä 1 alkaen. Vaihdetaan keskenään indeksissä 1 oleva luku sekä taulukon pienin luku indeksistä 1 alkaen.
  • Tarkastellaan taulukkoa indeksistä 2 alkaen. Vaihdetaan keskenään indeksissä 2 oleva luku sekä taulukon pienin luku indeksistä 2 alkaen.
  • Jne.

Toteuta metodi jarjesta, joka perustuu yllä olevaan ideaan. Metodissa on syytä olla silmukka, joka käy läpi taulukon indeksejä. Metodeista pieninIndeksiAlkaen ja vaihda on varmasti hyötyä. Tulosta myös taulukon sisältö ennen järjestämistä ja jokaisen kierroksen jälkeen, jotta voit varmistaa algoritmin toimivan oikein.

Metodin runko on seuraava:

public void jarjesta(int[] taulukko) {
}

Testaa metodin toimintaa ainakin seuraavalla esimerkillä:

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

Ohjelman tulosteen tulisi olla seuraavanlainen. Huomaa että sinun tulee tulostaa taulukon sisältö jokaisen vaihtamisen jälkeen!

[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]

Huomaat, miten taulukko tulee pikkuhiljaa järjestykseen alkaen alusta ja edeten loppua kohti.

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 ensin lukua 33, sitten 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
Binäärihaku vs. Peräkkäishaku

Peräkkäishaun pahimmassa tapauksessa käydään kaikki taulukon arvot läpi. Miljoona alkiota sisältävässä taulukossa tämä tarkoittaa miljoonan alkion tarkastelua.

Binäärihaun pahimmassa tapauksessa tutkittava alue jaetaan kahteen osaan kunnes osan koko on yksi. Alkioita tarkastellaan huomattavasti vähemmän kuin peräkkäishaussa. Tarkastellaan tätä hieman tarkemmin.

Taulukko, jossa on 16 alkiota, voidaan jakaa kahteen osaan korkeintaan 4 kertaa, eli 16 -> 8 -> 4 -> 2 -> 1.

Toisaalta, taulukko, jossa on miljoona alkiota voidaan jakaa kahteen osaan korkeintaa 20 kertaa, eli 1000000 -> 500000 -> 250000 -> 125000 -> 62500 -> 31250 -> 15625 -> ~7813 -> ~3907 -> 1954 -> ~977 -> ~489 -> ~245 -> ~123 -> ~62 -> ~31 -> ~16 -> ~8 -> ~4 -> ~2 -> ~1.

Mitä tämä tarkoittaa? Binäärihakua käyttäen miljoona alkiota sisältävästä taulukosta tulee pahimmassa tapauksessa tarkastella noin kahtakymmentä alkiota, kun peräkkäishaussa tarkasteltavia alkioita on miljoona.

Koska haettavien alkioiden määrä puolittuu binäärihaussa jokaisen tarkastelun yhteydessä, voi binäärihaun tehokkuutta tarkastella kaksikantaisen logaritmin avulla. Kaksikantainen logaritmi (log2) annetusta luvusta kertoo kuinka monta kertaa luku voidaan puolittaa. Esimerkiksi kaksikantainen logaritmi luvusta 16777216 (log2 16777216) on 24, ja luvun 4294967296 kaksikantainen logaritmi, (log2 4294967296) on 32. Tämä tarkoittaa että 4294967296 eri arvoa sisältävästä järjestyksessä olevasta taulukosta hakeminen vaatisi binäärihaulta korkeintaan 32 eri alkion tarkastamista.

Valmiiden järjestämisalgoritmien hyödyntäminen

Java tarjoaa myös 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

Käytetään jälleen edellisessä osassa käytettyä UNESCOn avointa dataa lukutaidosta. Data sisältää tilastot eri maiden arvioiduista tai raportoiduista lukutaidoista viimeisen kahden vuoden ajalta. Tehtäväpohjassa mukana oleva tiedosto lukutaito.csv sisältää arviot sekä yli 15-vuotiaiden naisten että yli 15-vuotiaiden miesten lukutaidosta. Tiedoston lukutaito.csv yksittäisen rivin muoto on seuraava: teema, ikäryhmä, sukupuoli, maa, vuosi, lukutaitoprosentti. Alla on esimerkkinä tiedoston viisi ensimmäistä riviä.

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
  

Kirjoita ohjelma, joka lukee tiedoston lukutaito.csv ja tulostaa tiedoston sisällön pienimmästä lukutaidosta suurimpaan. Tulostus tulee muotoilla seuraavan esimerkin näyttämään muotoon. Esimerkki näyttää tulostuksen ensimmäiset 5 odotettua riviä.

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

Tehtävä on kahden pisteen arvoinen.

Matkailijat tykkäävät ottaa valokuvia. Usein kuvissa sattuu kuitenkin olemaan ärsyttävä turisti, joka on esimerkiksi kuvatun kohteen edessä. Harmitus kasvaa erityisesti, jos samainen turisti esiintyy jokaisessa kuvassa.

Alla on kaksi kuvaa eräästä reissusta.

 

 

Täydennetään ohjelmaa, mikä mahdollistaa kuvan katsomisen ilman turistia. Apunamme meillä on iso nippu samasta kohteesta otettuja kuvia (turisti on harmittavasti kylläkin jokaisessa niistä...)

Tehtäväpohjassa on valmiina ohjelma, jolla voi tarkastella kuvia. Kun ohjelma on käynnissä, painamalla numeronäppäintä saat näkyville kuvalistan tietyssä indeksissä olevan kuvan. Kun painat näppäintä "v", näet kuvan muodossa, missä jokaisen kuvan jokaisesta pikselistä on valittu vaaleimmat pikseliarvot.

 

Tummimman värin valinta

Muokkaa sovellusta siten, että kun käyttäjä painaa näppäintä "t", ohjelma näyttää kuvan, missä näkyy yhdistettävien kuvien tummimmat pikselit. Toteuta tummimman värin valinta luokan Yhdistin metodiin public WritableImage tummin(final ArrayList<Image> kuvat) -- ota mallia metodista vaalein.

Kun olet lisännyt tummennustoiminnallisuuden, tumman kuvan pitäisi näyttää kutakuinkin seuraavalta.

 

Värien mediaani

Noniin, hankkiudutaan turistista eroon.

Muokkaa sovellusta siten, että kun käyttäjä painaa näppäintä "m", ohjelma näyttää kuvan, missä näkyy yhdistettävien kuvien väriarvojen mediaanit. Toteuta mediaanivärin valinta luokan Yhdistin metodiin public WritableImage mediaani(final ArrayList<Image> kuvat).

Mediaani on järjestettyjen lukujen keskimmäinen arvo. Esimerkiksi, jos viiden kuvan sinisten värien arvot ovat 211, 123, 17, 155, 8, on niiden mediaani 123. Saat mediaanin selville järjestämällä arvot, ja valitsemalla listan keskimmäisen arvon.

Toteutuksen pitäisi poistaa ärsyttävä turisti:

Tehtävän alkuperäinen versio: John Nicholson / Austin Peay State University

Sisällysluettelo