tegnap írtam arról, hogy a JDK 7 ötös mérföldkövével számos újítás kipróbálható. például a JSR-166 új implementációja, ami konkurenciához kapcsolódó dolgokat tartalmaz. ezt én is áttanulmányoztam és csupa hasznos dolgot találtam benne. ebben a postban a ForkJoinPool osztály használatáról fogok írni, a többiről majd később.

a legegyszerűbb ott kezdeni, hogy a ForkJoinPool egy ExecutorService. egy ExecutorService arra való, hogy taskokat hajtsunk végre vele konkurrens módon. ezt természetesen a Thread osztállyal is megtehetjük, de annek a megoldásnak van egy hátránya: a végrehajtás kevésbé válik külön a végrehajtó objektumtól. ráadásul az ExecutorService implementációk kifinomult szálkezelést, poolozást stb. valósítanak meg, ami megint csak az ő javukra szól. a ForkJoinPool tehát egy ExecutorService kiegészítve pár dologgal. a legfontosabb plusz az úgynevezett work-stealing. ez röviden annyit jelent, hogy a ForkJoinPool tétlen szálai megpróbálnak átvenni a többi száltól feladatokat, hogy így gyorsítsák a végrehajtást. ennek köszönhetően nagyon egyszerűen használhatjuk olyan algoritmusok implementálásánál, amik egymástól független részfeladatokat állítanak elő. például a gyorsrendezést úgy implementálhatjuk, hogy a menet közben létrejövő részfeladatokat betesszük a poolba. a pool aztán gondoskodni fog róla, hogy valaki azokat a feladatokat is elvégezze.

a ForkJoinPool ForkJoinTask-ok végrehajtására képes. általában mégsem ezt az osztályt kell kiterjesztenünk, hanem valamelyik alosztályát. jelenleg két alosztályt tartalmaz az API: a RecursiveTask-ot olyan részfeladatok végrehajtására, amik kiszámítanak egy értéket és a RecursiveAction-t a visszatérési érték nélküli taskokhoz. ezeknek a compute() metódusát kell felüldefiniálnunk, itt kell elvégeznünk a számítást.

a ForkJoinPool-t tehát így használhatjuk:

• elkészítjük a ForkJoinTask egy alosztáját.ebben implementáljuk a számítást és elkészítjük az esetleges részproblémáknak megfelelő objektumokat. ezeket a ForkJoinTask metódusainak segítségével a poolba tesszük.
• készítünk egy ForkJoinPool objektumot.
• a ForkJoinPool megfelelő metódusával végrehajtjuk a feladatot.

az alábbi kódban a gyorsrendezést implementáltam a fent leírt eszközök segítségével. a ForkJoinPool létrehozása a sort() metódusban történik, a részfeladatokat pedig a compute() metódus készíti el. ezek az invokeAll() metódusok keresztül kerülnek be a poolba.

tegnap letöltöttem a java 7 legfrissebbverzióját innen és kipróbáltam pár újdonságot.

az egyik fontos dolog az, hogy már működik a String switch, azaz a switch utasításban már Stringeket is használhatunk. ez nem nagy újítás, de érdekes volt egy teljesen új nyelvi  képességet használni.

ennél nagyobb lépés, hogy a JSR-166 nagy részét is implementálták már. ez számos konkurenciával kapcsolatos osztályt, interfészt jelent. mihelyt lesz időm, ezekről írok bővebben is. egyelőre a TransferQueue és a ForkJoinPool (és tartozékai) tűnnek a legérdekesebbnek.

sok olyan feladat van az ACM problémák között, amiben a cél a leghosszabb növekvő részsorozat megkeresése. erre létezik O(n2) idejű dinamikus programozást használó algoritmus iletve van egy O(nlog(n))-es algoritmus is 1975-ből. van azonban egy ezenél is szebb megoldás 1999-ből: a passziánsz rendezés. ez egy mohó algoritmus, ami azért szép, mert a szerzők teljesen új módon közelítették meg a problémát, nem a kézenfekvő dinamikus megoldást próbálták alkalmazni. ráadásul a mohó algoritmusok általában sokkal könnyebben megérthetők, megjegyezhetők, mint a dinamikus párjaik. így könnyebben fel lehet őket idézni, ha esetleg internet nélkül kell megoldanunk egy ilyen problémát.

az algoritmus kitalálói egy elképzelt passziánsz játékból indultak ki. ebben adott n darab, 1-től n-ig számozott kártyalap. ezeket egyesével vesszük elő. minden lapot rárakhatunk egy meglévő kupacra, ha a kupac tetején annál a lapnál kisebb értékű van. ha nincs ilyen, akkor új kupacot kell kezdenünk. a cél az, hogy a lehető legkevsebb kupaccal fejezzük be a játékot. a szerzők bebizonyították, hogy létezik egy stratégia, ami mindig az optimális megoldást adja. egyszerűen kezdjük el lerakni a lapokat. minden lapot arra a legbaloldalibb kupacra rakjuk rá, amelyikre tudjuk. ha nincs ilyen, akkor kezdjünk új kupacot. ez egy mohó stratégia, hiszen nem kell előre gondolkodnunk, mindig csak az adott kártyalappal foglalkozunk. ráadásul azt is sikerült bebizonyítaniuk a szerzőknek, hogy mikor a játékot ezzel a stratégiával játsszuk, a végén pontosan annyi kupacunk lesz, amennyi a kártyalapokból kiválasztható leghosszabb növekvő részsorozat hossza. azaz van egy mohó algoritmusunk a LIS problémára, ami O(nlog(n)) idő alatt végez a feladattal.

ahhoz, hogy egy konkrét részsorozatot megkapjunk, elég nyilvántartanunk, hogy melyik elem volt az utolsó kupac tetején, amikor egy új kupacot kellett kezdenünk. ilyen egyszerű.

az O(nlog(n)) időt úgy kapjuk, hogy minden új elemnél bináris kereséssel keressük meg azt a kupacot, amire rátehetjük. (a bináris keresés O(nlog(n)) ideje garantált azoknál a listáknál, amik implementálják a RandomAccess interfészt). a kód az alábbi.

csináltam egy bookmarkletet, ami a böngészőben kijelölt szövegről eldönti, hogy az egy kis L betű, egy egyes vagy más. szükségem volt erre, mert szemmel sosem megy. ha használni akarod, vonszold ezt a linket a böngésző könyvjelsző sávjába.

mostanában újra ráálltam az ACM versenyfeladatok megoldására. az egyik ilyen feladatban egy tömb résztömbjeinek a legkisebb elemét kellett megtalálnom. valahogy így nézett ki:

for(int i = 0; i < n; i++) {

for(int j = 1; j < n; j++) {

// az ar[i,j] részvektor legkisebb elemének az indexét keressük
int m = minIndex(arr, i, j);

}

}

a többszörösen beágyazott ciklusok rontották a hatékonyságot, ezért, hogy ne emiatt bukjon el a programom, másképp oldottam meg a minimális index megkeresését.

a probléma neve egyébként "Range Minimum Query" és szerencsére több hatékony megoldás is létezik rá. az egyik, amit én választottam, a szegmensfa használata. a szegmensfában a tömb bizonyos résztömbjeiről tárolunk információkat. ezekből aztán könnyen előállítható a válasz egy tetszőleges résztömbre is.

a szegmensfa minden csomópontja egy résztömb kezdő- és végindexét tartalmazza, illetve az adottrésztömb minimális elemének az indexét. a gyökér a [0, n] résztömbhöz tartozik (n a tömb utolsó elemének indexe).ha adott egy csomópont, ami a [b, e] résztömbhöz tartozik, akkor az ő baloldali részfájának a gyökere a [b,(b + e) /2] résztömbhöz, a jobboldali részfájának gyökere pedig a [(b +e) / 2 + 1, e] résztömbhöz tartozik. egy csomópont minimális elemének az indexét úgy találjuk meg, ha vesszük a bal- és a jobboldali részfák minimális indexét, és a két elemet összehasonlítjuk. amelyik kisebb, az lesz a csomópontban a minimális. ahol b és e megegyezik, ott a minimális elem indexe b.

ha a szegmensfát felépítettük, tetszőleges [i, j] résztömb minimális elemének megkeresésére használhatjuk. elindulunk a fa gyökerétől. ha olyan csomópontot találunk, amit az [i, j] intervallum. teljesen tartalmaz, akkor megvagyunk: a csomópont minimális eleme jó lesz. ha a csomópont intervalluma tartalmazza [i, j]-t akkor megyünk tovább a bal- és jobboldali részfákra. hogy hogya, az a kódból majd látszik.

ezzel meg is van minden a szegmensfa implementálásához. íme a fát felépítő és a minimális indexet tetszőleges intervallumra lekérdező kód.

crystal postjáról eszembe jutott, hogyrégen ln is jártam ACM programozó versenyekre. akkor általában C-ben küldtük be a feladatokat. most eldöntöttem, hogy egy párat megoldook Javában is.

a második, amit megoldottam, ez volt.  mivel az ilyenoptimalizálós feladatokat sokszor dinamikus programozással vagy valamilyen mohó algoritmussal kell megoldani, ezért átgondoltam, hogy itt melyik lenne a jobb. a mohó algoritmusok nem mindig adnak optimális megoldást, így először azt kellett belátnom, hogy ennél a feladatnál mi a helyzet. szerencsére könnyű volt észrevenni, hogy ha egy intervallum része az optimális fedésnek, akkor a mohó módszer is beválasztja azt a megoldásba. innen pedig már könnyű volt megírni a programot. ez lett az eredmény.

a program először a bal végük alapján növekvőleg rendezi az intervallumokat. ezután végigmegy a listán és megpróbálja mindig a legnagyobb részt lefedő új intervallumot kiválasztani. az új intervallumnak természetesen illeszkednie kell az előző végéhez, vagy átfedésben kell lenniük. addig fut, amíg van ilyen intervallum és el nem éri a lefedendő intervallum végét. a mohósága abban van, hogy nem gondolkodnik előre, mindig csak egy lépésre koncentrál és azt a lehető legjobban teszi meg.

a kódban vannak hibák és biztosan lehet még rajta gyorsítani. de mivel bőven az időkorláton belül lefutott és a tesztelő elfogadta ezért nem finomítottam tovább.

kedden írtam a pluggable annotation processingről, ami a java 6-os verziójától létezik. most itt egy összetettebb kód a funkciók bemutatására.

a lenti processor a @Decorate annotációkat dolgozza fel (saját annotáció típus). minden osztályhoz, amin használjuk ezt az annotációt, generál egy alosztályt. az alosztály neve OsztálynévDecorated lesz. ebben minden metódus felül van írva (kivéve a private, a final és a static metódusokat). ezek az újradefiniált metódusok meghívják a szülő megfelelő metódusát, de előtte kiírnak valamit a szabványos kimenetre.

a kód nincs felkészítve minden esetre, viszont  pár fontos dolgot le lehet belőle szűrni:

• új állományokat egy Filer objektummal generálhatunk
• a generált fájlok Writer-ét le kell zárnunk, mert addig az új osztályok létre sem jönnek
• az ExecutableElement osztálytól elkérhetjük a metódus nevét, viszont ha a paraméterek típusára vagyunk kíváncsiak, akkor egy ExecutableType objektumra van szükségünk. erre a TypeElement asType() metódusával tehetünk szert

a kód pedig itt következik.