Informatika4-2018/Gyakorlat9
a (→Feladat) |
a (→Feladat) |
||
109. sor: | 109. sor: | ||
** '''void remove(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. | * Í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 == | == Naív == | ||
124. sor: | 125. sor: | ||
Ekkor mennyi az egyes metódusok műveletigénye? | 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> | ||
+ | { | ||
+ | |||
+ | } | ||
[[Informatika4-2018/Gyakorlat8|Előző]] - [[Informatika4-2018#Gyakorlat|Fel]] - [[Informatika4-2018/Gyakorlat10|Következő]] | [[Informatika4-2018/Gyakorlat8|Előző]] - [[Informatika4-2018#Gyakorlat|Fel]] - [[Informatika4-2018/Gyakorlat10|Következő]] |
A lap 2018. november 26., 14:03-kori változata
Tartalomjegyzék |
Generics
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; } }
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> {
}