1. Dynaaminen muistinkäyttö

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:

http://www.mit.jyu.fi/~vesal/kurssit/ohj2/moniste/esim/dyna/

 

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

1.1 Muistin käyttö

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.

1.2 Dynaamisen muistin käyttö Javassa

1.2.1 new

Javassa kaikki oliot luodaan dynaamisesta muistista (keosta).

1.2.2 Olion tuhoaminen

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

1.2.3 Taulukon luominen new []

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

 

1.3 Dynaamiset taulukot

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:

dyna\Taulukko.java -esimerkki dynaamisesta taulukosta

/**

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

  }

}

 

1.4 Javan tietorakenneluokat ja algoritmeja

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

1.4.1 vector-luokka

Seuraavassa on Taulukko.javaa vastaava esimerkki toteutettu Vector-luokan avulla. 

dyna\VectorMalli.java – vector-luokka

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

  }

}

 

1.4.2 Iteraattori

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

1.4.3 ListArray

Edellinen esimerkki voitaisiin toteuttaa myös ListArray-rakenteella:

dyna\ArrayListMalli.java – ListArray-luokka

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

  }

}

 

1.4.4 Algoritmit

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

 

  }

}

1.5 Tietovirta parametrinä

Metodi tulosta on esitelty

  public static void tulosta(OutputStream os,  Collection luvut) {

 

Näin voidaan tulostusvaiheessa valita mille laitteelle tulostetaan.