Informatika4-2018/Gyakorlat9

A MathWikiből
A lap korábbi változatát látod, amilyen Gaebor (vitalap | szerkesztései) 2019. november 20., 22:50-kor történt szerkesztése után volt.

Előző - Fel - Következő

Tartalomjegyzék

Generics

tutorial

C++ template megfelelője.

Tetszőleges metódust vagy osztályt megírhatunk úgy, hogy működjön több osztályra is. Például:

public class Main
{
    public static <T> boolean IsIn(T[] a, T v)
    {
        for( int i = 0; i < a.length; ++i)
        {
             if (a[i].equals(v))
                 return true;
        }
        return false;
    }
}

Írhatunk generikus osztályt is:

public class A <T>
{
    . . . 
}

Feladat

Írjunk generikus Ring interface-t, ami a három alapműveletet definiálja. Ezt implementálja a Real és Int osztályok.

Ezután megírhatjuk a generikus Complex osztályt, amit így példányosíthatunk:

Complex<Real>
Complex<Int>
public interface  Ring<T> {
	public T add(T other);
	public T mul(T other);
	public T sub(T other);
	public T clone();
}

Wildcards

Collections

Kollekciókban lehet objektumokat tárolni.

List

Sorrendet őrző kollekció. Lehet beszúrni, kitörölni elemet, tetszőleges pozícióban. Le lehet kérdezni az adott pozícióban lévő elemet.

ArrayList

A List-nek olyan megvalósítása, ahol az elemek egy összefüggő memóriatartományban (tömb) helyezkednek el.

  • Időben konstans költsége van egy elem elérésének
  • Időben lineáris egy elem beszúrása vagy törlése, mert az összes többi elemet is mozgatni kell hozzá.
|a|b|c|d|e|f|g| -> |a|b|x|c|d|e|f|g|
    ^
    x

LinkedList

Láncolt lista, az elemek helye nem rögzített a mamóriában, de mindegyik eltárol egy-egy referenciát ez előtte és a mögötte álló elemre, így őrzi a sorrendet.

   +-+ -> +-+ -> +-+ -> +-+ -> 
   |a|    |b|    |c|    |d|
<- +-+ <- +-+ <- +-+ <- +-+
  • Egy adott pozíció elérése időben lineáris, mert az elejétől lépkedve lehet eljutni minden elemhez.
  • Egy elem beszúrása időben konstans, mert csak a szomszédos elemeket érinti a beszúrás
   +-+          +-+ -> +-+ -> +-+ -> 
   |a|\        /|b|    |c|    |d|
<- +-+ \      / +-+ <- +-+ <- +-+
      \ \    / /
       \ +-+  /
        \|x| /
         +-+

Set

A Set olyan tároló, amiben egyedi elemek vannak, nem lehet benne kétszer ugyan az (halmaz). De cserébe nem beszélhetek adott indexű elemről, mert az elemet sorrendje nem kötött. Egy elem beszúrása mind az előtte, mind az utána lévőket átrendezheti. Sőt nem is lehet egy adott pozícióba beszúrni elemet, csak beszúrni lehet, ha már benne volt az elem, akkor nem történik semmi, ha nem, akkor benne lesz, de nem tudjuk, hogy hol.

HashSet

Hash függvény segítségével határozza meg, hogy hova kerüljön egy elem. Az elemek sorrendje látszólag véletlen.

  • Egy elem beszúrása, megkeresése és törlése is időben várhatóan konstans!
    • de legrosszabb esetben lineáris!
    • ez azt jelenti, hogy általában gyorsak a fent említett műveletek, de néha lehet lassú, várható értékben még mindig nagyon gyors.

TreeSet

Elemeit rendezett fában tárolja. Beszúrás/törlés hatására a sorrend garantáltan nem romlik el. A lenti példában az [1,2,3,5,7] elemeket tároljuk.

    2
   / \
  1   5
     / \
    3   7

A fa kiegyensúlyozott, ami azt jelenti, hogy nem engedi, hogy bármelyik ága is túl hosszú legyen. Széles és sekély fára törekszik az implementáció.

Ennek következménye, hogy:

  • a beszúrás, keresés, törlés időben logaritmikus

Map

A Set-hez hasonló, csak még értékeket is tudunk az elemekhez tárolni, hasonlít a python dict-hez.

["anna": 555, "beatrice": 1234, "cecile": 1234]

A kulcsok azok, helyek a Set-hez hasonlóan vannak tárolva, az értékek egyértelműek egy adott kulcshoz, de lehet két kulcsnak ugyan az az értéke.

HashMap

Lásd #HashSet, csak Map.

TreeMap

Lásd #TreeSet, csak Map.

Feladat

Implementáljunk egy gráf osztályt!

  • A gráf csúcsait jelöljék egész számok
  • két egész szám jelöljön egy irányított élet a két csúcs között
  • Tudjunk csúcsot hozzáadni és törölni
    • void add(Integer a)
    • void remove(Integer a)
  • Tudjunk élet hozzáadni és törölni
    • void add(Integer a, Integer b)
    • void remove(Integer a, Integer b)
  • Írjuk meg a toString metódust, hogy lássunk is valamit a gráfból.
  • Legyenek GetV és GetE metódusok, melyekkel a csúcsok és élek számát tudjuk lekérdezni.

Naív

Kezdetben a csúcsokat tároljuk listában, az éleket pedig egy list-of-list adatstruktúrában, ami kettő hosszú listák listája.

private List<Integer> nodes_;
private List<List<Integer>> edges_;

Ha így teszünk, mennyi az egyes metódusok műveletigénye? Konstans, lineáris, logaritmikus?

Map

Az éleket hatékonyabb egy adott csúcshoz eltárolni: legyen minden csúcshoz egy lista, ami a belőle kiinduló éleket tárolja.

private Map<Integer, List<Integer>> edges_;

Ekkor mennyi az egyes metódusok műveletigénye?

Generic

Változtassuk meg az osztályt úgy, hogy a csúcsokat tetszőleges objektum jelölje, például Integer vagy String.

public class Graph <Type>
{
}

Előző - Fel - Következő

Személyes eszközök