Aina ei aavista kokoa
suuruuttapa suuren suurta
dynaamisuus siis avuksi
mielehen muuttuva kokokin.
Varaa muistia tarvittaissa
uutta uikuta muuttujille
viitteen päähän pantavaksi
sieltä sitten saatavaksi.
Listoja ja taulukoita
vinkeitä vipeltimiä
algoritmejä arvokkaita
valmiinakin tarjonnassa.
Mitä tässä luvussa käsitellään?
· Dynaaminen muistinhallinta
· Dynaamiset taulukot
· Muistinsiivous
· Algoritmit
Syntaksi:
Dyn.olion.luonti muuttuja = new Luokka(parametrit)
"Hävittäminen" muuttuja = null;
Luvun esimerkkikoodit:
Olemme oppineet varaamaan muuttujia esittelyn yhteydessä. Usein olioita voidaan luoda (= varata muistitilaa) myös ohjelman ajon aikana. Tämä on tarpeellista erityisesti silloin, kun ohjelman kirjoittamisen aikana ei tiedetä muuttujien määrää tai ehkei jopa edes kokoa (taulukot).
Karkeasti ottaen tavallisen ohjelman muistinkäyttö näyttäisi ajan funktiona seuraavalta:
^
muistin │
kaytto │ ┌───────────────────────────────┐
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
└────┴───────────────────────────────┴──────>
ohjelman ohjelman
alku loppu
Edellinen kuva on hieman yksinkertaistettu, koska "oikeasti" aliohjelmien lokaalit muuttujat (automaattiset muuttujat) syntyvät aliohjelmaan tultaessa ja häviävät aliohjelmasta poistuttaessa. Näin ollen käytetyn muistin yläraja vaihtelee sen mukaan mitä aliohjelmia on kesken suorituksen.
Dynaamisia muuttujia voidaan tarvittaessa luoda ja kun muistitilaa ei enää tarvita, voidaan vastaavat muuttujat vapauttaa:
^
muistin │
kaytto │ ┌──┐
│ ┌────┐ │ │ ┌───┐
│ │ │ │ │ ┌─┘ │
│ ┌──┘ └────┘ └───┘ └─────┐
│ │ │
│ │ │
└────┴──┼────┼────┼──┼───┼─┼───┼─────┴──────>
ohjelman new new new new
alku olio=null null null
Näin muistin maksimimäärä saattaa pysyä huomattavasti pienempänä kuin ilman dynaamisia muuttujia. Idea on siis siinä, että muistia varataan aina vain sen verran, kuin sillä hetkellä tarvitaan. Kun muistia ei enää tarvita, vapautetaan muisti.
Ajonaikana luotaviin muuttujiin tarvitaan osoitteet. Nämä osoitteet pitää sitten tallettaa johonkin. Talletus voitaisiin tehdä esimerkiksi taulukkoon tai sitten alkioista pitää muodostaa linkitetty lista.
Javassa kaikki oliot luodaan dynaamisesta muistista (keosta).
Kun oliota ei enää tarvita, se häviää aikanaan, kun kaikki siihen osoittavat viitteet asetetaan null-arvoon tai poistetaan viitteen kokonaan (poistutan metodista jolloin lokaalit viitteet katoavat) . Tällöin olio muuttuu roskaksi ja muistisiivous aikanaan tuhoaa kaikki oliot, joihin ei ole viitteitä.
Jos new–operaattorilla on luotu taulukollinen olioita niin varsinaiset oliot pitää luoda erikseen.
monta = new Luokka[20];
...vielä ei ole varsinaisia alkiota, vain 20 viitettä.
Kerhon jäsenrekisterissä käytettiin osoitintaulukkoa dynaamisesti. Vastaavan rakenteen tarve tulee usein ohjelmoinnissa. Tällöin tulee aina vastaan ongelma: montako alkiota taulukossa on nyt? Jäsenrekisterissä tämä oli ratkaistu Jasenet–luokassa tekemällä sinne kentät, joista nämä rajat selviävät.
Javassa edällä mainittu dynaaminen taulukko voidaan toteuttaa käyttäjän kannalta todella joustavaksi:
/**
* Esimerkki dynaamisesta taulukosta
* @author Vesa Lappalainen
* @version 1.0, 02.03.2002
*/
public class Taulukko {
public class TaulukkoTaysiException extends Exception {
TaulukkoTaysiException(String viesti) { super(viesti); }
}
private int alkiot[];
private int lkm;
public Taulukko() {
alkiot = new int[10];
}
public Taulukko(int koko) {
alkiot = new int[koko];
}
public void lisaa(int i) throws TaulukkoTaysiException {
if ( lkm >= alkiot.length ) throw new TaulukkoTaysiException("Tila loppu");
alkiot[lkm++] = i;
}
public String toString() {
StringBuffer s = new StringBuffer("");
for (int i=0; i<lkm; i++)
s.append(" " + alkiot[i]);
return s.toString();
}
public void set(int i, int luku) throws IndexOutOfBoundsException {
if ( ( i < 0 ) || ( lkm <= i ) )
throw new IndexOutOfBoundsException("i = " + i);
alkiot[i] = luku;
}
public int get(int i) throws IndexOutOfBoundsException {
if ( ( i < 0 ) || ( lkm <= i ) )
throw new IndexOutOfBoundsException("i = " + i);
return alkiot[i];
}
public static void main(String[] args) {
Taulukko luvut = new Taulukko();
try {
luvut.lisaa(0); luvut.lisaa(2);
luvut.lisaa(99);
} catch ( TaulukkoTaysiException e ) {
System.out.println("Virhe: " + e.getMessage());
}
System.out.println(luvut);
luvut.set(1,4);
System.out.println(luvut);
int luku = luvut.get(2);
System.out.println("Paikassa 2 on " + luku);
luvut.set(21,4);
}
}
Koska erilaisten dynaamisten tietorakenteiden (vrt. Taulukko.java) käyttö on erittäin yleistä, on Javaan standardiin lisätty joukko tietorakenteita. Jotta nämä tietorakenteet pystyisivät tallentamaan erilaisia tyyppejä on niistä tehty sellaisia, että ne tallentavat Javan kaikkien luokkien kantaluokan Object-luokan viitteitä.
Meidänkin esimerkissämme Jasenet ja Harrastukset eroavat toisistaan vain hyvin vähän. Ero on itse asiassa muutaman Jasen –sanan muuttuminen Harrastus –sanaksi. Jos olisimme olleet tarpeeksi ”ovelia”, olisimme voineet tehdä vain yhden geneerisen tietorakenteen, joista olisi sitten luotu kaksi erilaista esiintymää.
Seuraavassa on Taulukko.javaa vastaava esimerkki toteutettu Vector-luokan avulla.
import java.util.Vector;
import java.util.Iterator;
import java.io.*;
import fi.jyu.mit.ohj2.*;
/**
* Esimerkki Javan vektorin käytöstä
* @author Vesa Lappalainen
* @version 1.0, 02.03.2002
*/
public class VectorMalli {
public static void tulosta(OutputStream os, Vector luvut) {
PrintStream out = Tiedosto.getPrintStream(os);
for (Iterator i = luvut.iterator(); i.hasNext(); ) {
int luku = ((Integer)i.next()).intValue();
out.print(luku + " ");
}
out.println();
}
public static void main(String[] args) {
Vector luvut = new Vector(7);
try {
luvut.add(new Integer(0)); luvut.add(new Integer(2));
luvut.add(new Integer(99));
} catch ( Exception e ) {
System.out.println("Virhe: " + e.getMessage());
}
System.out.println(luvut);
luvut.set(1,new Integer(4));
System.out.println(luvut);
int luku = ((Integer)luvut.get(2)).intValue();
System.out.println("Paikassa 2 on " + luku);
tulosta(System.out,luvut);
luvut.set(21,new Integer(4));
}
}
Esimerkissä taulukon tulostus on tehty iteraattorin avulla. Iteraattorin ideana on tarjota tietty, erittäin suppea joukko operaatiota, joita siihen voidaan kohdistaa. Näin samalla rajapinnalla varustettu iteraattori voidaan toteuttaa hyvin erilaisille tietorakenteille esimerkiksi taulukoille ja linkitetyille listoille. Iteraattorille esitettyjä suomennoksia ovat esimerkiksi selain ja vipellin.
Vektorin tapauksessa tietorakenne voitaisiin käydä läpi myös taulukkomaisesti,
for (i=0; i<luvut.size();i++)
out.print(((Integer)(luvut.get(i)).intValue());
mutta tällöin tietorakenteen vaihtaminen esimerkiksi linkitetyksi listaksi vaatisi muutoksia tulosta-aliohjelmaan. Eli aina kun mahdollista, kannattaa välttää käyttämästä sitä tietoa, mikä tietorakenne on käytössä.
Edellinen esimerkki voitaisiin toteuttaa myös ListArray-rakenteella:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Collection;
import java.io.*;
import fi.jyu.mit.ohj2.*;
/**
* Esimerkki Javan ArrayListin käytöstä
* @author Vesa Lappalainen
* @version 1.0, 02.03.2002
*/
public class ArrayListMalli {
public static void tulosta(OutputStream os, Collection luvut) {
PrintStream out = Tiedosto.getPrintStream(os);
for (Iterator i = luvut.iterator(); i.hasNext(); ) {
int luku = ((Integer)i.next()).intValue();
out.print(luku + " ");
}
out.println();
}
public static void main(String[] args) {
ArrayList luvut = new ArrayList(7);
try {
luvut.add(new Integer(0)); luvut.add(new Integer(2));
luvut.add(new Integer(99));
} catch ( Exception e ) {
System.out.println("Virhe: " + e.getMessage());
}
System.out.println(luvut);
luvut.set(1,new Integer(4));
System.out.println(luvut);
int luku = ((Integer)luvut.get(2)).intValue();
System.out.println("Paikassa 2 on " + luku);
tulosta(System.out,luvut);
luvut.set(21,new Integer(4));
}
}
Kun tietorakenteelta oletetaan tietty rajapinta, voidaan sille suorittaa sopiva algoritmi, esimerkiksi lajittelu, tietämättä tietorakenteen yksityiskohtia:
import java.util.ArrayList;
import java.util.Vector;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.io.*;
import fi.jyu.mit.ohj2.*;
/**
* Esimerkki Javan algoritmien käytöstä
* @author Vesa Lappalainen
* @version 1.0, 05.03.2002
*/
public class AlgoritmiMalli {
/**
* Luokka joka vertailee kahta kokonaislukuoliota ja
* palauttaa niiden järjestyksen niin, että lajittelu menee
* laskevaan järjestykseen.
*/
public static class LaskevaInt implements Comparator {
public int compare(Object o1, Object o2) {
return ((Integer)o2).intValue() - ((Integer)o1).intValue();
}
}
public static void tulosta(OutputStream os, Collection luvut) {
PrintStream out = Tiedosto.getPrintStream(os);
for (Iterator i = luvut.iterator(); i.hasNext(); ) {
int luku = ((Integer)i.next()).intValue();
out.print(luku + " ");
}
out.println();
}
public static void main(String[] args) {
ArrayList luvut = new ArrayList();
try {
luvut.add(new Integer(0)); luvut.add(new Integer(2));
luvut.add(new Integer(99)); luvut.add(new Integer(7));
luvut.add(new Integer(22)); luvut.add(new Integer(71));
} catch ( Exception e ) {
System.out.println("Virhe: " + e.getMessage());
}
System.out.println(luvut); // [0, 2, 99, 7, 22, 71]
Collections.sort(luvut);
tulosta(System.out,luvut); // 0 2 7 22 71 99
Collections.sort(luvut,new LaskevaInt());
tulosta(System.out,luvut); // 99 71 22 7 2 0
Collections.shuffle(luvut);
tulosta(System.out,luvut); // 99 2 7 71 0 22
Collections.sort(luvut,Collections.reverseOrder());
tulosta(System.out,luvut); // 99 71 22 7 2 0
Collections.reverse(luvut);
tulosta(System.out,luvut); // 0 2 7 22 71 99
int suurin = ((Integer)Collections.max(luvut)).intValue();
System.out.println("Suurin = " + suurin); // Suurin = 99
int pienin = ((Integer)Collections.min(luvut)).intValue();
System.out.println("Pienin = " + pienin); // Pienin = 0
pienin = ((Integer)Collections.max(luvut,new LaskevaInt())).intValue();
System.out.println("Pienin = " + pienin); // Pienin = 0
List luvut2 = new LinkedList();
luvut2.addAll(0,luvut);
tulosta(System.out,luvut2); // 0 2 7 22 71 99
luvut2 = luvut.subList(2,5);
tulosta(System.out,luvut2); // 7 22 71
}
}
Metodi tulosta on esitelty
public static void tulosta(OutputStream os, Collection luvut) {
Näin voidaan tulostusvaiheessa valita mille laitteelle tulostetaan.