Refleksija i sortiranje

Nikola Zifra

1 Jun 2004

Svakako jedan od najstarijih problema koji se sreće u programiranju je sortiranje kolekcija ili nizova objekata. Sistemi za upravljanje bazama podataka (RDBMS) obezbedjuju efikasnu implementaciju algoritama za sortiranje i jedno od rešenja je bilo da njima prepustite sortiranje, ukoliko je reč o podacima iz baze podataka. Medjutim ne potiču svi podaci koji treba da se sortiraju iz baza podataka. Ne tako davno morali ste lično da implementirate pojedine algoritme za sortiranje kao što su bubble-sort, merge-sort ili quick-sort. Java 2 je problem sortiranja elegantno rešila na dva moguća načina uz pomoć utility klase java.util.Collections na dva načina:

"Prirodnim" načinom poređenja, koji je realizovan je tako što klase čije instance nameravamo da sortiramo treba da implementiraju java.util.Comparable interface, koji ima samo jedan metod compareTo(Object), čija implementacija treba da vrati -1 (u slučaju da je objekat manji od objekta sa kojim ga poredimo), 0 (u slučaju da su objekat i objekat sa kojim ga poredimo isti) i 1 (u slučaju da je objekat veći od objekta sa kojim ga poredimo)
Korišćenjem Comparator klasa koje implementiraju java.util.Comparator interfejs sa jedinim compare(Object, Object) metodom, koji implementira način poređenja 2 objekta. Naime metod compare(Object, Object), treba da vrati -1 (u slučaju da je prvi objekat manji od drugog objekta), 0 (u slučaju da su prvi i drugi objekat isti) i 1 (u slučaju da je prvi objekat veći od drugog objekta)

Kod koji bi sortirao instance klase koja implementira java.util.Comparable korišćenjem "prirodnog" poređenja izgledao bi ovako:

// pretpostavimo da imamo listu Integer-a ili neke druge klase

// koja implementira Comparable interfejs

List l = ..poziv nekoj metodu koji puni listu Integer-a...

Collections.sort(l);

Kod koji bi sortirao instance neke proizvoljne klase korišćenjem Comparator klasa:

// pretpostavimo da imamo proizvoljnu listu objekata

List l = ..

Collections.sort(l, new MojComparator());

pri čemu je klasa MojComparator, klasa koja implementira java.util.Comparator interfejs.

Očigledno je da Comparator klase omugućavaju da se ista kolekcija objekata sortira na različite načine i po različitom kriterijumu, što ih čini efikasnim rešenjem problema sortiranja. Implementacija Collections.sort() metoda koristi modifikovani merge-sort algoritam. Ukoliko se odlučimo da za svaki kriterijum napišemo odgovarajuću Comparator klasu, lako može doći do eksplozije broja Comparator klasa. Kako se izboriti sa tim problemom? Zašto bi za svaku Java Bean klasu morali da pišemo posebnu komparator klasu ili komparator klasu sa komplikovanim instanceof ispitivanjima.

Refleksija kao sredstvo za ostvarivanje generičnosti u sortiranju

Odgovor u postizanju generičnosti u sortiranju nalazi se u refleksiji. Java refleksija predstavlja skup paketa koji u toku izvršavanja aplikacije omogućavaju pristup .class objektima gde se čuvaju definicije klasa. Svaka klasa ima svoj .class objekat u toku izvršavanja programa gde se čuvaju definicije metoda i atributa. Refleksija pruža API za rad sa .class objektima. Korišćenjem refleksije u implementaciji compare(Object,Object) bi mogli da postignemo generičnost i izbegnemo pisanje velikog broja Comparator klasa. Koristeći refleksiju mozemo da procitamo u toku izvršavanja programa vrednost bilo kog propert-ija Java Bean-a i to na sledeći način:

Method getterMethod = argClass.getDeclaredMethod(geterName, null);

// invoke geter method on supplied object

field = getterMethod.invoke(arg, null);

Pri čemu je argClass varijabla tipa Class i predstavlja klasu objekta čiji metod hoćemo da pozovemo koristeći refleksiju, arg predstavlja objekat čiji metod pozivamo preko refleksije, field je tipa Object i predstavlja povratnu vrednost metoda pozvanog preko refleksije, geterName je varijabla tipa String koja predstavlja naziv pozvanog metoda (u ovom slučaju to je get metod koji vraća vrednost nekog polja). Za više informacija pogledati implementaciju metoda getFieldValue() klase net.javasvet.util.UniversalComparator. Ukoliko pretpostavimo da je već postoji napisan metod metod getFieldValue() pojednostavljeno telo compare(Object arg0,Object arg1) metoda izgledalo bi ovako:

Object field0 = getFieldValue(arg0, arg0Class);

Object field1 = getFieldValue(arg1, arg1Class);

Comparable c0 = (Comparable) field0;

Comparable c1 = (Comparable) field1;

return (sortOrder == SORT_ASC ? c0.compareTo(field1) : c1.compareTo(field0));

Suština je da korišćenjem polimorfizma, sav posao oko poređenja 2 vrednosti prepustimo compareTo(Object o) metodi klasa čije instance poredimo. Sve klase koje implementiraju interfejs Comparable implementiraju ovaj metod a to su skoro svi značajniji Java 2 tipovi (Long, Integer, Double, java.util.Date, java.sql.Date, java.sql.Timestamp, String...). Po default-u način sortiranja je opadajući. Na taj način je izbegnuto korišćenje komplikovanih instanceof ispitivanja i iskorišten je već postojeći kod Sun-ovih programera. Na prvi pogled moglo bi se reći da je problem sortiranja rešen u par linija koda. San svakog programera :)...

Problem sa našim latiničnim alfabetom

Ovakva implementacija odradiće posao prilikom poređenja propert-ija skoro svih tipova i rezultat će biti zadovoljavajući, ali šta će se desiti ukoliko pokušamo da poredimo String-ove koji su sadrže karaktere latiničnog pisma kao što su 'č','ć' ili 'š'? Redosled sortiranja zavisiće od UTF-16 vrednosti pojedinih karaktera koji je osnovni standard kodiranja koji Java 2 podržava. Problem leži u činjenici da se slovo 'š' po našoj verziji latiničnog pisma nalazi između 's' i 't'. Međutim uzimajući u obzir njihove UTF kodove ('s' - \u0053, 'š' - \u0161, 't'-\u0054) rastući redosled ovih karaktera bi bio sledeći 's','t' i 'š'. U doba internacionalizacije i globalizacije kada softver treba da se prilagodi jezicima i očekivanjima raznih nacija ovaj problem je veoma aktuelan. Na svu sreću on je rešiv u Javi 2, uz pomoć klasa java.text.Collator i java.text.RuleBasedCollator (pogledati Java API Doc za više informacija). Naš problem rešava java.text.RuleBasedCollator klasa koja kao parametar svog konstruktora uzima pravila poređenja proizvoljnih karaktera, npr. pravila latinične verzije našeg alfabeta, ili pak pravila za ćirilični raspored latiničnih slova definisanih u String-u oblika kao u sledećem primeru:

"<a=A<b=B<v=V<g=G<d=D<\u0110=\u0111<e,E
<\u017D=\u018E<z=Z<i=I<j=J<k=K<l=L
<lj=Lj=LJ<m=M<n=N<nj=Nj=NJ<o=O<p=P
<s=S<t=T<\u0106=\u0107<u=U<f=F<h=H
<c=C<\u010C=\u010D<d\u017E=D\u017D=D\u017E<\u0160=\u0161"

Opadajući redosled može se definisati preko sledećeg String pravila:

"<\u0160=\u0161<d\u017E=D\u017D=D\u017E<\u010C=\u010D<c=C<h=H<f=F<u=U
<\u0106=\u0107<t=T<s=S<p=P<o=O<nj=Nj=NJ<n=N<m=M<lj=Lj=LJ<l=L<k=K<j=J
<i,I<z=Z<\u017D=\u017E<e,E<\u0110=\u0111<d=D<g=G<v=V<b=B<a=A"

Relacije koje se mogu koristiti između karaktera su: "=","<",">" i ",". Prve tri relacije imaju očigledno značanje dok se "," koristi za razdvajanje velikih i malih slova. U tom slučaju velika i mala slova nemaju istu težinu.

String serbian = (sortOrder == SORT_ASC) ?

    STRING_ASC : STRING_DESC;

    RuleBasedCollator serCollator = null;

try {

    serCollator = new RuleBasedCollator(serbian);

} catch (ParseException e1) {

    e1.printStackTrace();

    throw new RuntimeException(e1);

}

return serCollator.compare(field0, field1);

Pozivom metode compare(String s1,String s2) klase java.text.RuleBasedCollator vršimo poređenje String-ova po pravilima željenog pisma, u ovom slučaju latiničnog alfabeta po ćiriličnom rasporedu. Ukoliko predpostavimo da se ovakva implementacija poređenja Stringova nalazi u compareStrings(String field0, String field1) metodi finalna implementacija compare(Object arg0, Object arg1) metoda bi izgledala ovako:

public int compare(Object arg0, Object arg1) {



    Class arg0Class = arg0.getClass();

    Class arg1Class = arg1.getClass();        

    // compare only instances of the same class

    if (arg0Class != arg1Class) {

        throw new IllegalArgumentException("Only instances of the same class should be compared!");

    }            

    // obtain specified field values from compared objects

    Object field0 = getFieldValue(arg0, arg0Class);

    Object field1 = getFieldValue(arg1, arg1Class);

    // don't perform null values comparison

    if (field0 == null || field1 == null) {

        throw new IllegalArgumentException("Can't perform null values comparison for property " + fieldName + ".");

    }

    // compare only instances of Comparable class

    if (!(field0 instanceof Comparable) || !(field1 instanceof Comparable)) {

        throw new IllegalArgumentException("Property " + fieldName +

                                           " doesn't implement java.util.Comparable " +

                                           " interface, so natural comparison method can't be applied.");        

    }    

    // characters and strings care ompare using separate comparison

    // algorithm emobidied in compareStrings(String,String) method

    if (field0 instanceof String && field1 instanceof String) {            

         return compareStrings((String)field0, (String)field1);        

    }    

    

    if (field0 instanceof Character && field1 instanceof Character) {            

         return compareCharacters((Character)field0, (Character)field0);        

    }

    // compare types like java.sql.Timestamp, java.util.Date, java.sql.Date, Long, long,

    // Integer, int,... using natural comparison method

    Comparable c0 = (Comparable) field0;

    Comparable c1 = (Comparable) field1;        

    return (sortOrder == SORT_ASC ? c0.compareTo(field1) : c1.compareTo(field0));

}

Implementacija metoda proverava:

da li je reč o instancama iste klase
da neka od poređenih nije null vrednost
da li polje po kome se vrši sortiranje implementira java.util.Comparable interfejs

U slučaju da neki od uslova nije ispunjen metod "baca" IllegalArgumentException. Po default-u redosled sortiranja koji se koristi je opadajući.

Korišćenje univerzalnog Comparator-a

Veoma jednostavno.

List l = new ArrayList();

// Sortiranje Liste Student objekata na osnovu vrednosti id polja u

// opadajucem redosledu. Probajte sa sledecim poljima: id, firstName

Collections.sort(l, new UniversalComparator("id", UniversalComparator.SORT_DESC));

Zaključna razmatranja

Korišćenjem UniversalComparator-a možete sortirati u opadajućem ili rastućem redosledu liste proizvoljnih Java Bean objekata na osnovu vrednosti nekog propert-ija. Taj property može biti drugi Java Bean. Uslov koji property mora da ispuni jeste da implementira java.util.Comparable interfejs i da predstavlja ne-null vrednost. Spisak tipova koji implementiraju java.util.Comparable interfejs u Javi 2 je poduži: Integer, Long, java.util.Date, java.sql.Date. Property može predstavljati neki primitivan tip kao što je int ili long ali će sortiranje i dalje raditi. Postavlja se pitanje performansi generičkog sortiranja. Na mojoj mašini sa Celeronom na 1,7Gh i 512 MB SD-RAM-a sortiranje 10000 instanci objekta Student po propert-iju id tipa int je trajalo 2125 ms, dok sortiranje 100 Studenata po po propert-iju firstName tipa String traje 5906 ms što ukazuje na rapidnu degradiciju performansi prilikom poređenja Stringova. UniversalComparator-a stoga treba koristiti prilikom sortiranja manjih lista podataka naročito ukoliko uključuje poređenje String-ova. O metodama za ubrzavanje procesa sortiranja biće više reči u narednim člancima Java Sveta.

Primer

Primer koji prati članak se može downloadovati ovde.