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.

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.

2 thoughts on “Java rendezés – avagy hogyan ne tegyük”

  1. Amit biztosan tudok adni, az egy magyarázat arra, hogy miért nem működik, ha nem monoton összehasonlító függvényt adsz meg quicksort-nak. Az algoritmust nem részletezem, annak te is utána tudsz nézni 🙂

    A probléma jellegét jól érted, az algoritmus “particionálás”-nak nevezett lépésében a rendezendő tömböt egy heurisztikusan kiválasztott elem szerint két felé osztja. Ugye ekkor minden elemet csak a kiválasztott elemmel hasonlítja össze. Ha nem monoton a rendezés, akkor megeshet, hogy a kiválasztott elemnél nagyobbnak bizonyult elem kisebb lesz egy a kiválasztott elemnél kisebbnek ítélt elemnél. Ezután hiába fűzi a közben rendezett részhalmazokat egymás után, rosszul rendezett elemek lesznek a listában.

    Megoldásként nem tudok mondani a problémára triviálisan monoton rendezést, ehelyett olyan rendezési algoritmust javaslok, ami részleges rendezés esetén is jól működik. Például alkalmas lenne az öröklődési gráfból egy topológikus sorrend lefejtése (ami létezik, ha a gráfban nincs irányított kör).

    Az összehasonlítás-alapú rendezéseket átgondolva mindegyikre igaz, hogy a monotonitást feltételezi. kivéve, ha minden elemet minden elemmel összehasonlítasz, ami nem túl hatékony (köbös lépésszám, ha jól emlékszem), miközben a topológikus sorrend csak egy szélességi bejárást kíván, ami DAG(http://en.wikipedia.org/wiki/Directed_acyclic_graph) esetén lineáris lépésszámú.

    Remélem segítettem

  2. Nem tudom, hogy monoton-e a rendezés, ezt a témát ezért épp nem erőltetem túlságosan – de ha nem monoton, akkor könnyű megindokolni, hogy miért nem jó.

    Az írás előtt meg pontosan megnéztem a quick sort algoritmust is, és az alapján próbáltam megítélni, hogy az összehasonlítás megfelelő-e, de nem tudok a rendezéshez olyan ellenpéldát mondani, amivel a sort elszúrhatja (egyébként kell, hogy legyen… mert a gyakorlati esetben elrontotta, de én nem találtam olyan relatíve kis példát, ami elmehet).

    A köbös lépésszám a mindent mindennel összehasonlításra túlzás azért: sztem négyzetes algoritmussal megoldható, ugyanis n*(n-1) összehasonlítással, és n darab listába illesztéssel megoldható biztosan, feltéve, hogy hajlandóak vagyunk egy új tömbbe pakolni. Valamint még a legegyszerűbb buborékrendezésről is elképzelhetőnek tartom, hogy működne (ez utóbbi nem biztos…).

    Topologikus sorrend: az írás végén sikerült egy ilyen algoritmust leírni. Magamtól. És per pillanat ez van belőve, mint rendezés. Mint írtam is, ez erősebb, mint ami nekem kell, de megfelelő, ugyanis már biztosítja a leírt részleges rendezésben leírt tulajdonságokat.

Leave a Reply