2009-10-16

Megoldás

Szóval ott tartottam hogy Scala és Java programkódokat hasonlítgatok össze, ami egy tömbben egy adott karakter előfordulásait számolja meg. Egy szerény 30 millió karakteres tömbön próbálgattam a négyféle programkódot, amit az előző post-ban fabrikáltam össze tegnapelőtt: Volt sima for ciklusos és rekurzív algoritmus Java-ban és Scala-ban is.

Nézzük hogyan muzsikáltak:

Az első sima Java megoldás (1.) kb 160 ezredmásodperc alatt birkózik meg a feladattal. A Scala program, amibe a Java imperativizmusát másoltam le (2.), 1200 ezredmásodpercig dolgozik ugyanezen. Ez egyáltalán nem elhanyagolható különbség, de mégegyszer hangsúlyoznám, hogy ész nélkül írtam át a Java kódot Scala-ba: Egyszer talán majd pörgök egy post-ot ezen a különbségen is, de alapvetően "nem érdekel ez most engem".

Következőnek a (4.) Java programkódot tárgyalom ki, amit kvázi funkcionálisan írtam meg, rekurziót használva, viccből. Na ez már hatezer karakteres bemeneti karaktertömbnél is csúnyán elcsattan StackOverflowError-ral. Ha ismerjük a rekurzió működését, -azaz hogy a program minden egyes függvényhívásnál felépít egy stack frame-et- ez nem is túl meglepő. Ahány karakter, annyi stackframe: a verem hamar felzabálja a memóriát.

Végül jöjjön a (3.) funkcionális Scala program, ami a 4.-eshez hasonlóan rekurziót használ. Ez viszont nem száll el StackOverFlowError-ral, sőt egész jó időt hoz, kb. 160 ezredmásodpercet. Csak kicsivel lassabb mint a legelső kód. Hogyan lehet ez?

A megoldás kulcsa a farokrekurzió és annak kioptimalizálása. A dolog lényege, hogy a rekurzív függvény legutolsó művelete saját magának a meghívása. Még általánosabban, ha egy függvény utolsó művelete egy másik függvény meghívása (Tail Call). Ilyenkor levezethető, hogy a legutolsó stackframe újrafelhasználható, vagy legalábbis eldobható a következő függvény meghívása előtt. A jelenlegi Java-t futtató JVM implementáció nem támogatja ezt a feature-t. Vannak rá törekvések, ami talán új bájtkód prefixet is szükségessé tenne, de ez nem a közeljövőben fog megvalósulni. Biztonsági kérdések is felmerülnek, mert a Java nem optimalizálhatja ki csak úgy a stack frame-eket. Kivétel dobásánál vagy hozzáférési jogosultság ellenőrzésnél nem szerencsés ha hiányoznak frame-ek. A ScalaByExample.pdf -ami külön fejezetet szán ennek a magyarázatára- megemlíti hogy a Scala esetében farokrekurzió optimalizására lehet építeni, de a stackoverflow-n találtam még két kitételt ezen felül: Csak lokális vagy final függvények esetében.

Aki arra is kíváncsi hogy a Scala (valószínűleg) hogyan oldja meg, illetve hogyan oldható ez meg magas szinten egy nyelv meglévő elemeivel a program átírásával de az algoritmus jellegének megtartásával, az itt találhat egy kimerítő leírást róla. Elég messziről indul és körmönfont példát hoz, de egyébként nem egy bonyolult dolog. Hasonlít a Command Pattern-re.

Egyébként ezzel az egésszel csak arra akartam megnyugtató választ kapni, hogy a Scala-ban előszeretettel használt tail rekurzió megállja-e a helyét gyári környezetben. A válasz: igen.

2009-10-14

Scala fejtvény

Ahogy beleolvasgattam egy-két Scala ismertetőbe az volt az érzésem, hogy folyton túl kézreálló példákat próbálnak hozni a nyelvhez. Arra gondoltam, csinálok egy olyan példát, ami nem annyira kézreálló. Számoljuk meg egy karakter tömbben a paraméterben megadott karaktereket. Sokkal kreténebb példákat is lehetne kitalálni, de én most megelégszem ezzel. Java-ban elég kézenfekvő a megoldás (1.):

public int count(char a, char[] array) {
int ctr = 0;
for(char ch : array) if(ch==a) ctr++;
return ctr;
}
Ezt tükörfordításban ész nélkül kb. így lehet átírni Scala-ba (2.):
def count(a: Char, array: Array[Char]) : Int = {
var ctr = 0;
for(ch <- array) if(ch==a) ctr = ctr + 1;
ctr;
}
Viszont a Scala funkcionális nyelv és ha ezt a paradigmát kihasználva szeretnénk megírni a programot, nem tehetjük meg, hogy ezt mondjuk: ctr = ctr + 1. Ez az a dolog, ami miatt ezt én "nem kézreálló példának" tartom. Ehelyett valami olyasmit kell elkövetnünk, mintha fél lábon állva a bal fülünket a jobb kezünkkel a fejünk mögött átnyúlva vakarnánk meg (3.):
def count(a: Char, array: Array[Char]) = {
def count_(i : Int, ctr : Int) : Int =
if(i == array.length) ctr else
count_(i+1, if(array(i)==a) ctr+1 else ctr)
count_(0, 0)
}
Bár nem tartozik szorosan a témához, azért néhány Scala jellegzetességet gyorsan kiemelek: A külső függvénynek nincs meghatározva visszatérési értéke, mert kikövetkeztethető. Nem írtam pontosvesszőket a sor végére, mert a fordító így is érti miről van szó. Ja és ezek egymásba ágyazott függvények, ráadásul a belső függvény látja a külső bemenő paramétereit.

Csak a vicc kedvéért, ezt az utóbbit visszaírom java-ba, úgyhogy ha az előző megoldás nem volt érthető, talán ez tisztába teszi a dolgokat némileg a Java-s emberek számára is. Itt viszont már két függvényre van szükségem (4.):
public int count(char a, char[] array) {
return count_(a, array, 0, 0);
}

private int count_(char a, char[] array, int i, int ctr) {
return i==array.length ? ctr :
count_(a, array, i+1,
a==array[i] ? ctr+1 : ctr);
}
Namost a kérdés a következő: Szerintetek a négy megoldás mennyire gyors és mi történik (és miért - főleg ez a lényeges) ha egy jó nagy -de még nem akkora nagy hogy azonnal OutOfMemoryErrort okozzon- karaktertömböt adok meg bemeneti paraméterként? A megoldást megírom pénteken. Ha addig valaki bekommenteli a megfejtést, kap tőlem egy sört vagy ezzel egyenértékű élvezeti cikket a következő JUM-on.