Java rendezés – avagy hogyan ne tegyük

A Java Collection könyvtára remek munka – könnyen használható, mégis sokoldalú API-t biztosít. Megfelelő listákhoz, gráfreprezentációkhoz és feltételezem, hogy még sok minden egyébhez.

Ehhez képest nem (sokkal) bonyolultabb kezelni, mint egy tömböt. Sőt, a C nyelv tömbkezeléséhez képest sokkal egyszerűbb is… 🙂

Ami nekem különösen tetszik, az a beépített rendezési lehetőségek: a Collections.sort statikus metódus használatával saját Comparator segítségével lehet rendezéseket definiálni.

Ezután szinte magától adódott már, hogy amikor nekem egy objektumhierarchia reprezentálására van szükségem, akkor ahhoz ezt a beépített könyvtári osztályokat használjam. Az általam használt algoritmus (most ezt nem részletezném a szükséges tömörség miatt) feltételezte, hogy a hierarchia elemeit felülről lefelé adom be (azaz mindig előbb az őst adom be, és csak utána a leszármazottakat). Miután ezt a bemenetemről nem tudtam feltételezni, ezért adódott a dolog, írjunk rá egy rendezést, saját komparátorral.

public int compare(IEntity i1, IEntity i2){
if (i1.isSubtypeOf(i2)) return -1;
else if (i2.isSubtypeOf(i1)) return 1;
else return i1.getFullyQualifiedName().compareTo(i2.getFullyQualifiedName());
}

Szép, olvasható kód, és pontosan azt írja le, amit szeretnék. Igaz? Hisz itt látszik, hogy szépen az öröklési hierarchia szerint rendezi a mezőket. Amikor ezt a kódot úgy nagyjából egy hónapja megírtam, akkor működött is – igaz, csak erőteljesen korlátozott tesztelés volt, mert ez csak egy nagyon parányi része volt a dolognak, amit csináltam, és utána pedig egy kicsit ezt a részt jegeltem.

Ehhez képest most jött a feketeleves, hogy amikor egy kicsit változott a környezet, amiben az új funkciót teszteltem, kaptam egy hatalmas nullpointer exception-t. Remek…

Némi játék után (ugyanis a futási környezet lenyelte a kivételt, és csak az üzetenet jelenítette meg, ami nullpointer exception-nél mindig “”, azaz nem látszik), kiderítettem, hogy a gondot az okozza, hogy egy objektum kapcsán próbálok hivatkozni az ősére egy saját adatszerkezetben, de ebbe az adatszerkezetbe nem került bele. Ez pedig csak úgy lehetséges, ha az eredeti rendezésnél valami miatt a leszármazott előbbre kerül, mint az őse (általában nem, de az én programomban igen).

Kíváncsi vagyok, hogy hány ember látja, hogy hol is van a probléma a fenti komparátorral, hogyan jöhet össze, hogy a beépített Java sort algoritmus is ezt a rossz eredményt adja ki…

Tökéletes magyarázatom nincs a problémára, de a hiba oka nagyjából két dolog lehet. Egyfelől a definiált komparátor csak egy részben rendezéshez ad megfelelő támpontot, másrészt a Java feltehetőleg a qsort algoritmust használja, ami nem végzi el az összehasonlítást az összes párra, így tipikusan nem hasonlít össze minden egyes elemet minden másik elemmel.

Van még egy tényező, ami a rendezési eljárást még kevésbé egyértelművé teszi, ez pedig az egymástól akár teljesen független ágak a hierarchiában. Az eredeti példáimban ezekből kevés volt, míg a példa, amin kiakadt a program, viszonylag sok, egymástól független ágat tartalmazott, ezzel jócskán megnehezítve az algoritmus munkáját.

Ötletem nem volt, hogyan kellene működővé varázsolni a rendezést egy átírt komparátorral, ezért más, korábbi tanulmányokhoz nyúltam vissza: a bsz-en/algoritmuselméleten bemutatott topologikus rendezéshez nyúltam vissza. Ugyan az jóval erősebb rendezési feltétel, mint amire nekem konkrétan szükségem volna, de ezért cserébe viszonylag kevés munkával lekódolható, és nem is túlságosan lassú (jó, ez persze relatív).

Persze ennek a kódolásakor is segítségemre volt a Java Collections API, még így is kevesebb, mint 20 sor volt a teljes rendezési eljárás, amit még zárásnak beszúrok az írás végé elé.

/**
* Creates a topological ordering on the modelelements
*/
private List orderModelElements(List elementsToOrdered){

List orderedElements = new ArrayList();
while (!elementsToOrdered.isEmpty()){
//The currentLevel is needed in order to remove all the elements that
//do not have any ancestors, not only the first one
//If we delete the elements straight from the elementsToOrdered list,
//the iterator in the for cycle will not work.
List currentLevel = new ArrayList();
for (IEntity element : elementsToOrdered){
Collection ancestors = new ArrayList();
ancestors.addAll(element.getSupertypes());
ancestors.retainAll(entities);//remove all non-entities
if (ancestors!=null && orderedElements.containsAll(ancestors)){
currentLevel.add(element);
}
}
orderedElements.addAll(currentLevel);
elementsToOrdered.removeAll(currentLevel);
}
return orderedElements;
}


És hogy miért is írtam ezt így ide meg? Ennek két oka is van: egyrészt egy nagyon önző, magamat szem előtt tartó indok: ha valaki el tudja esetleg mondani nekem, hogyan kellene a komparátort kijavítani, esetleg részletesebben elmagyarázza csak, hogy miért is hasal el az a komparátor a quick sorton (ha quick sort), nagy örömmel veszem akármilyen formában a reakcióját. Másfelől pedig okulásnak is akart menni mások számára, hogy esetleg nekik ne kelljen órákat bogarászniuk egy pár ezer soros kódbázisban, hogy pontosan hogyan is adódhat az a nullpointerexception.

Author: Zoltán Ujhelyi

I am an Eclipse Technology Expert at IncQuery Labs Ltd. and a regular contributor of open-source projects, most importantly the VIATRA project at eclipse.org. Furthermore, I am in the process of finishing my PhD in computer science at the Budapest University of Technology and Economics focusing on analysis techniques for model queries and transformations. View all posts by Zoltán Ujhelyi