…avagy hogyan lehet pozitív tulajdonság a gyengeség és a lustaság. 🙂
Arról a gyakran előforduló modellről van szó, amikor sorok és oszlopok metszeteiben rácselemek csücsülnek, melyek automatikusan létrejönnek a nekik megfelelő sor-oszlop párra való hivatkozáskor, valamint automatikusan megszűnnek soruk vagy oszlopuk törlése esetén.
A megvalósítás kézenfekvőnek tűnik: a sorokban/oszlopokban egy map-ben tároljuk az oszlopokkal/sorokkal indexelve a rácselemeket.
Valahogy így:
[cc_java]
public class Node {
}
public class Column {
}
public class Row {
protected final Map nodes = new HashMap();
public Map getNodes() {
return nodes;
}
}
[/cc_java]
Mi a gond ezzel?
- Ha törlünk egy oszlopot, az összes sor map-jében még ott marad a rá mutató referencia, mint kulcs. Ez memory leakhez vezet: a szemétgyűjtő nem tudja eltakarítani a “zombi” oszlopokat és a hozzájuk tartozó, ugyancsak zombi rácselemeket. Ez ráadásul az adatstruktúra perzisztálásánál is problémát jelent.
- Hogyan s mikor hozzuk létre a rácselemeket? Mindig, amikor létrehozunk egy oszlopot? Ezt jobban lehetne automatizálni, ráadásul ha nem minden rácspontba akarunk elemet tenni, fölöslegesen hozzuk létre ezeket.
Több megoldás is lehetséges, gondolhatnánk elsőre:
- Gondolkodhatnánk egy címkézett gráfban, és a beépített kollekciók helyett alkalmazhatnánk valamiféle gráfkezelő könyvtárat, pl. a JGraphT-t, mely gondoskodik csúcs törlésekor a hozzá tartozó élekről.
- Kibővíthetnénk a lista adatszerkezetet eseménykezelőkkel, melyek elem hozzáadásakor és törlésekor végrehajtanak egy megadott kódot.
Azonban a probléma megoldható a Java Collections Framework keretein belül, karöltve természetes kiegészítőjével, a Collections Generic API-val (a Commons Collections generikus változata). Nehogy már egy ilyen általános jelenséget ne tudjunk a megannyi hasznos absztrakciót tartalmazó Java nyelv elemeivel modellezni! A kulcsfogalom a gyenge referencia, mellyel befolyásolhatjuk a garbage collector működését, ezzel rábízva az elárvult elemek törlését.
Javában az alapértelmezett referencia erős (strong), de ezenkívül még létezik a gyenge (weak), lágy (soft) és fantom (phantom) referencia. A weak reference lényege, hogy amennyiben egy objektumra csak ilyenek mutatnak, a szemétgyűjtő teljes lelki nyugalommal eltakarítja. Nekünk pont ez a viselkedés jön kapóra: a map-ben gyenge referenciákat fogunk csak tárolni az oszlopokra/sorokra. (A másik két típus most nem érdekes számunkra, pedig azok is hasznosnak bizonyulhatnak más esetekben.)
A Collections API tartalmazza a WeakHashMap osztályt, mely a HashMap-hez hasonló, azonban kulcsai gyenge referenciák. A WeakHashMap ezeket átlátszóan kezeli, önmagától létrehozva és dereferálva nekünk őket. Így programunkban az automatikus törléshez csak két dolgot kell módosítanunk: HashMap helyett WeakHashMap-et használunk, és a kívánt pillanatban meghívjuk a garbage collectort.
A létrehozás pedig lusta map segítségével történik: a rácselemek példányosítása akkor és csak akkor történik, amikor először hivatkozunk az őket azonosító sor-oszlop párosra. Ehhez is kész eszközt kapunk a kezükbe a Collections Generic Libraryben: a LazyMap-et és az InstantiateFactory-t, melyek a Decorator és a Factory pattern alkalmazásával érik el céljukat.
Imhol a forráskód módosított része. Figyelemreméltó, hogy mennyi minden változott…
[cc_java]
public class Row {
protected final Map nodes = LazyMap.decorate(new WeakHashMap(), new InstantiateFactory(Node.class)); // !
}
[/cc_java]
És egy kis tesztosztály, a kiértékelés a kedves olvasó feladata:
[cc_java]
public class GridTest {
public static void main(String[] args) {
Grid grid = new Grid();
for (int i = 0; i < 2; i++) {
grid.getRows().add(new Row());
grid.getColumns().add(new Column());
}
for (Row row : grid.getRows()) {
for (Column column : grid.getColumns()) {
System.out.println(row.getNodes().get(column));
}
}
grid.getColumns().remove(1);
System.gc(); // !
for (Row row : grid.getRows()) {
for (Column column : row.getNodes().keySet()) {
System.out.println(row.getNodes().get(column));
}
}
}
}
[/cc_java]
Hát ilyen power a Collections Framework, amint már Stampie is [intlink id=”587″ type=”post”]rámutatott[/intlink], ami pedig esetleg hiányzik belőle, azt a Collections Generic pótolja. Mi a tanulság? Használjuk ki a nyelvi lehetőségeket, amelyek rendelkezésünkre állnak!
Nem tudom, hogy nem lenne-e jobb egy máshogy rekurzív adatszerkezettel leírni a hierarchiát.
Valami olyasmire gondolok, hogy
public class GridElement{public Integer columnID, rowID;
}
public Map map = new HashMap();
Számomra az előnyt ugye az adja, hogy ha tudom a helyet (GridElement a példában), akkor az alapján már a HashMapből egyszeres címzéssel ki tudom szedni az értéket. Jó, az tény, hogy így a GridElementeket is tárolni/kezelni kell, plusz a bejáráshoz sem árt egy saját iterátor.
Ha ezt nem akarod megtenni, akkor szóba jöhet esetleg a következő kód is:
public Map = ... Ez mondjuk kevésbé rugalmas, mint az előző…
Vááááá…
Most jöttem rá. Miért éppen Hashmap? Hiszen ha sorral/oszloppal tudsz címezni, akkor a sor/oszlop számával egy megfelelő ArrayList is címezhető. Talán kissé egyszerűbb megoldás…
Én egészen másképp állnék hozzá a dologhoz. HashMap helyett egy ArrayList-ben tárolnám az adatokat, aminek az az előnye, hogy integerrel indexelt. Ezután egy 2 dimenziós (x,y) indexelés a következőképpen képezhető le az egydimenziós listára, ismerve a mátrix sorainak hosszát:
i = y*rowlength + x;. Ezzel megoldható a mátrix dinamikus átméretezése is, hiszen kiszámítható, hogy hova kell beszúrni új oszlop- vagy sorelemeket, hogy új oszlopot/sort kapjunk, és vice-versa, törlésnél hogy honnan kell elemeket kivenni. Az ArrayList közvetlen haszna, hogy azinsert()ésremove()műveleteknél az elemek shiftelését automatikusan megoldja.Kicsit alulspecifikáltam a problémát. A Row és Column osztályok bevezetése nem overengineering eredménye, hanem az, hogy a feladat része, hogy a sorokhoz és oszlopokhoz is rendelhetünk tulajdonságokat, viselkedést kell tudni rendelni.
Az érvelésből kihagytam egy lépést, amikor a map-et egyből beletettem az egyik dimenzióba, ugyanis ezzel arra a dimenzióra nézve meg van oldva az automatikus node létrehozás/törlés kérdése. De még marad egy dimenzió – ez a cikk lényege.
Magába a Grid osztályba (aminek a kódja nem szerepel a példában) érdemes perszeNode getNodeAt(Row, Column) függvényt rakni, hogy átlátszó legyen, melyik dimenzió mentén van a trükk. Sőt, a Gridet érdemes generikus interface-ként megadni (Grid ), hogy minél inkább újrahasznosítható legyen, melynek a megvalósítása lehetne a cikkben leírt osztály.
A helyzet az, hogy ez nem segít abban számomra, hogy ne tűnjön túl bonyolultnak a megközelítés.
Az én megoldásaim nem követelik meg, hogy megszüntesd az oszlopokat:
public class Node{public Column col;
public Row row;
}
És ezt a Node mezőt címzésére meg fel lehet használni a Balage által ajánlott egyszerű címzési megoldásokat, feltéve, hogy hajlandó vagy egy columnID, illetve rowID mezőt felhasználni.
A rowba pakolás, mint sebességre (vagy megírandó kódra) optimalizálás meg szerintem nagyon csúnya…
A mi megoldásaink esetén sincs szükség túl bonyolult menedzselő kódra – és ha már úgyis be akarod pakolni egy generikus grid objektumba, akkor ezek a megoldások is beleférnek. A menedzselés tulképpen egy iterációt igényel mindössze – oszlop törlés esetén annyi darab keresést, ahány sor lehet, beszúráskor semmi különöset, szóval nem tűnik túlzásnak. Pláne, ha belül végül akár egy darab Hashmap van (ez egy közelítőleg konstans igényű keresés), akár egy többdimenziós tömböt vagy egydimenziós vektort használsz (érzésre ez is konstans, esetleg lineáris igényű keresés).
És amit első olvasásra nem is vettem észre: te ehhez a megoldáshoz már eleve 3rd party libet használsz (tudom, most magamat cáfolom egy kicsit ezzel, mert mindig is szerettem a 3rd party libeket) – de nem látom a többletet ebben a libben (arról nem is beszélve, hogy a plusz lib igénye csökkenti az újrahasznosíthatóságot): a mi összes megoldásunk maradt a natív Java libnél.
Ha valakinek van ideje rá, szívesen vennék egy összevetést ennek a WeakHashMap (és a kapcsolódó elemek), illetve a natív Java társaik sebességéről. Az ilyen szépségekért általában futási időben kell fizetni (de lehet, hogy tévedek, és most nincs időm a libet telepíteni, illetve tesztet tervezni).
Még egy megjegyzés: a //! típusú kommentek a példakódokban nem biztos, hogy szerencsések. Ha a tényleges kódodban is ezt csinálod, az határozottan nem szerencsés. Javaslatom helyette a külön sor(!) és a probléma szöveges leírása (ott lehet esetleg egy ❗ kezdetet tenni az elejére, ezt egyfajta tagként kezelve, hogy a komment milyen típusú).