Hidrológiai Közlöny 2007 (87. évfolyam)
4. szám - Gálai Antal: A Szmirnov-Kolmogorov próba – ahogy az alkalmazók monták: élesítése
58 HIDROLÓGIAI KÖZLÖNY 2007. 87. ÉVF. 4. SZ. ban nálunk fellelhető adatok köre is. Alap-szoftverek, s ma megszokott operációs rendszerek hiányában az adattárakat s a korábbi úttörő eljárásokat e statisztikai feladatoknál a szakmától azóta távolra került, de párban maradt Márfai Péter és Mezó'di Edit programozási munkája kötötte ma megszokott módon alkalmazási csokorba. A homogenitás-vizsgálat során Zsuffa István javaslatára az adatokat minimum 10 elemű részhalmazokra bontottuk, s e részminták gyakorisági eloszlásának számolásához a két adatsor-részt sorba rendeztük. Ezt követően a lépcsős-függvények össze-vissza váltakozó töréspontjain számoltuk a töréspont két oldalán a különbségeket, melyek közül a legnagyobbat megtartva, képeztük a mintaméret gyökével súlyozott különbség felső becslését, majd a homogenitás/inhomogenitás mértékét. + OO Z=d ma x.[(n 1n 2)/(n 1+n 2)] l/ 2 L(z) l-L(z) L(z) = I e" 2i V Kolmogorov eloszlás Ezután a minta szétvágási pontját eggyel arrább léptetve, ciklikusan ismételtük elölről az egészet. Ez ugyan már meghaladta a BME-n ljjas István akkoriban kiadott kiváló mérnöki programozási mintafeladatainak átlagát, de a két függvény lépcsőin való lépdelés józan paraszti észt (common sence) kívánó enyhén macerás pár sorától eltekintve jó fejű diákoknak való alapfeladat volt, semmi egyéb, ezért is birkóztunk meg mi magunk is vele. Azonban az algoritmusok fejlődését legtöbbször a kényszer szüli, s nem egyszer az ördög, mint mondják, a részletekben lakozik. Történt egyszer, hogy Schuller Harro és Petróczky Ferenc az ÉDUVIZIG-től nagyobb mennyiségű részben mikrofilmen lévő adatsort küldtek előre rögzítésre, majd néhány végső adatot hoztak, s helyben óhajtották kivárni azokban a mikroszekundumos időkben a számítások végét. S bár a tetemes számú állomás sokféle jellemzőjét a sornyomtató nagy sebességgel röpítette volna, nem is a mikro-programozott lebegőpontos müvelet miatt, hanem a tömérdek sorba rendezés okán a szekrénynyi CPU hosszasan behunyta a szemét, és csak időnként reccsentetett egyegy sort a leporellókra. A hosszan tartó kalkulációk hatására ásításukat nehezen elnyomó kollégák láttán beindultak csikorgó fogaskerekeim, s másnap már nagyságrendekkel sebesebb algoritmussal futott a kétmintás homogenitás-próba. No, de „lássuk a medvét!" Az első nyilvánvaló ötlet a sorba-rendezés váltása volt. Rátértünk a logaritmikus keresésre. Miképp az idegen nyelvet nem teljesen birtoklók szótár-használatkor leggyorsabban a betű szerint rendezett szóhalmaz oldal-csoportjainak állandó felezésével érik el a keresett szót, sorba-rendezéskor sem a rendezetlen szóhalmaz V elemének vizsgálatával keressük ki a következő legkisebb, vagy legnagyobb elemet, hanem a már rendezett részbe - kihasználva annak szabályos elrendezését - szúrjuk be helyére a következő rendezetlen elemet. Tesszük ezt valahogy úgy, ahogy az osztályba egymás után belépő diákok névsor szerint rendezve várják a következő érkező társukat, aki a szótár példa alapján egyre feleződő bakugrásokkal találja meg a helyét az eddig érkezettek között. Mindig a közepén levővel hasonlítva tudjuk eldönteni, melyik felében van a keresett vagy beszúrandó elem helye. A szükséges hasonlítások (és bakugrások) száma maximum annyi, ahányszor felezni tudjuk a sorba-rendezett elemeket tartalmazó részmintát, vagyis ahányszor felezni tudjuk a minta-elemszámot, ami éppen log 2n. A minta egymást követő elemeinek beszúrását a lineáris rendezések n nagyságrendű lépésszáma helyett legroszszabb esetben is kettes alapú log 22 + log 23 + ... + log 2n összehasonlítással végezhetjük el. Ergo 50-es elemszámnál 2500 helyett 214, míg 100-nál 10 000 helyett 524 összehasonlítással rakjuk az adatokat sorba. Vagyis ebben a tartományban a gyorsulás 12-20-szoros, míg 1000 adatnál már 117 szeres lesz. A második ötlet már erre a feladatra vonatkozott. Bár a sorba-rendezés komoly részét képviselte a szükséges műveleteknek, s ezzel már egy nagyságrendet nyertünk, de a sorozatos rendezések még mindig majdnem ugyanazt csinálták újra és újra. Ekkor ugyanis az adatsort egymás melletti részekre bontjuk, s ekkor a két egymást követő vizsgálat során a két-két rész-adatsor csupán egyetlen adatában különbözik az előzőktől, mivel az egyik adat átmászik a második adatsorból az elsőbe. Ez már sugallja, hogy a két új rész-adatsort nem kellene újrarendezni, csupán ezt az egyetlen adatot kell kiemelve a másikba áttenni. Ez ugyan kezdőknek okozhat némi fejtörést, de mielőtt erre vettettem volna kollégáimmal az irányt, felsejlett bennem, hogy a teljes adatsor egyetlen rendezésével s a rendezett rész-adatsorokba való elem-átmentések hókuszpókusza és a gyakorisági függvények lépcsőinek keresgélése helyett kell lennie frappánsabb, s egyszerűbben nemcsak programozható, hanem tanítható tanulságos lépéssornak is. Elhajítva minden eddigi programot, semmi már ismert vagy kipróbált algoritmust fel nem használva, a gyorsítás érdekében újrafogalmaztam a feladatot. Az alapötletet az adta, hogy az egész számítás nem függ attól, hogy pontosan mekkorák is a mért adatok, hanem azoknak konkrét nagyságuktól függetlenül, de azonos relációban kell maradniuk. Nem az számít, hogy mekkorák, hanem az, hogy hányadik a legnagyobb, második legnagyobb, stb. és legkisebb. A két rész-adatsorra választás elvágási pontjától függően sokféleképp előálló lépcsős függvények ott lépnek mindig egyet, ahol az eredeti adatsorban mért adatok vannak. A mért adatokon növekedve lépkedve az adat sorszáma, a mérés/észlelés ideje dönti el, hogy melyik rész-adatsor függvénye ugrik egyet. Ha az elvágási időpont előtti a soron következő adat, akkor az első lépcsős ugrik, ha későbbi, akkor a második. Tulajdonképpen felírhatom az adatokat egy kártya egyik felére, míg a hátára az észlelési időpontot/évet/sorszámot. Ezt követően a mérési adatokat növekvő sorrendbe rendezem, majd - mivel az észlelt adatok megtették kötelességüket, a sorrend meghatározását - a kártyákat megfordítom, s ezzel tudom meg, hogy növekvő érték szerinti sorrendben hányadik adat mikor lett észlelve. Jelentse az X(t(k)) a k-adik legkisebb adatot, míg X(i) az eredeti észlelési sorrendben i-edik mért adatot. Vagyis, t(k) a nagyság szerint rendezett adatok közül a £-adik legkisebb eredeti sorszámát/időpontját jelenti. Ekkor a lépcsős függvények közti maximális eltérés az 'e' elvágási pontonként az alábbi pár sorral számítható: for e = 10 to n-10 (i = j = d ma x=0; for k=l to n {if k < e then i = i+l else j = j+1 max(abs(i/e-j/(n-e)), d m a ,)) z = d ma x*sqrt(e*(n-e)/n); print e, L(z), l-L(z)) Az ötlet pofonegyszerű, és mégis tán éppen ezért tanulságos és közreadásra érdekes, hiszen bárki megcsinálhatja. Vagy ösztönzést kap, hogy más feladatot is mindig átfogalmazva, frappánsan és gyorsabban számíthatón oldjon meg. További gyorsításhoz adhat segítséget, hogy a logaritmikusrendezés során az egyes adatok beszúrásánál a beszúrási
