24. fejezet - Konzolos záró példa

Tartalom

Az algoritmusok világa
A MaxItemSort első változata
Az ICompare interface implementálása
Az InsertSort.
A Buborék rendezés
A MaxMinSort generikus változata
A Selection sort
A QuickSort
A főprogram kialakítása

Az algoritmusok világa

Az algoritmusok a programozás olyan építőkövei, melyek optimalizált megoldásokat nyújtanak gyakran használt, és általában erőforrás igényes feladatok jó minőségű megoldására. A hangsúly a jó minőségen van, hiszen az adott algoritmust használó program hatékonysága alapvetően az alkalmazott algoritmusok minőségétől függ. Ha például egy adott adathalmaz valamilyen szempontból történő sorbarendezése merül fel igényként, akkor egyáltalán nem mindegy, hogy azt a program milyen hosszú idő alatt végzi el. Ha a sorbarendezés gyorsan történik, akkor a programot is hatékonynak látjuk, míg kifejezetten bosszantó, ha az egyes operációk között tétlenségre kényszerítik a felhasználót. Persze néha elkerülhetetlen, hogy a gép hosszas, esetleg több másodpercig/percig tartó műveletbe bonyolódjon, de ilyenkor vagy a korábban tanultak szerint külön szálon futtatva tesszük lehetővé, hogy felhasználó egyéb hasznos dolgot csinálhasson, vagy legalább tájékoztatjuk a futó folyamat előrehaladásának mértékéről, hogy maga is láthassa, mennyi időt vesz majd igénybe az adott operáció. Az algoritmusok elképesztően bőséges irodalmából mi most a konzolos zárópéldában a fenti elvek betartásával nem egy ismert sorbarendezési algoritmust fogunk megvalósítani, hanem azt magunk „találjuk fel”, szemléltetve, hogy adott esetben mi is készíthetünk jó(??) algoritmust. Később a winform-os zárópélda után visszatérve, ugyanebben a projektben adunk egy winform-os megoldást is külön szálkezeléssel és haladás jelzéssel.

A MaxItemSort első változata

Mint azt más korábban megszoktuk, az objektumorientált szemléletben először egy inteface megtervezésével kezdjük, mellyel az adott, később realizált osztály továbbfejlesztését és specializálódását támogatjuk. A projektünk szerkezete tehát az alábbi:

7-1. ábra -

kepek3/12fejezet-7-1.jpg


Az ISort interface-ben előírunk néhány kötelezően megvalósítandó háttér változót, és medódust az alábbiak szerint.

A metódusok közül a GetMaxItem visszaadja a legnagyobb tárolt értéket, míg a sorbarendezést magát a MakeSort függvény valósítja meg.

A MakeSort publikus függvény igen egyszerű és rövid:

Ha külön szálon szeretnénk megvalósítani, akkor a withownthread flag állása szerint vagy egy új szálon, vagy az akruális processen belül hajtjuk végre a MakeSortInside private hatókörű tagfüggvényt. Tuljadonképpen ez a függvény a lényege az eljárásnak, melynek elvi alapja az, hogy egyszerűen végigolvassuk az elemeket, majd kiválasztjuk a legnagyobbat, és annak helyére az adott ábrázolható legkisebbet helyezzük, így ezt az indexet a továbbiakban kizárjuk a feldolgozásból. A legnagyobb elem kiválasztásának függvénye a GetMaxItemInside private metódus:

A MakeSortInside függvény pedig a következő:

A tagfüggvény használata után rendelkezésre állnak a csökkenően és a növekedően rendezett tömbök, illetve egy-egy, csak az indexeket tartalmazó lista, mellyel az eredeti rendezetlen listát is manipulálhatjuk, illetve bejárhatjuk. Ez a rendezés meglehetősen erőforrás-igényes, hiszen készít egy másolatot, amit minden alkalommal újra és újra végig jár a komparációs (összehasonlító) hurokban. Most azonban az volt az első célunk, hogy lássuk egy algoritmus megvalósításának elemi építőköveit az egyes részfeladatokon keresztűl.

Ha optimalizálni akarnánk a fenti kiinduló algoritmust, akkor nyilván a másolatok kiváltását (a sorbarendezés az eredeti tárolóhelyen valósuljon meg), a legnagyobb elem kiválasztását, csak a még fel nem dolgozott elemeket vegye elő, stb. irányban lenne érdemes gondolkoznunk. Azok az algoritmusok, melyek ennél jóval hatékonyabbak, alkalmazzák a fenti egyszerűsítéseket, mint azt egy későbbi példán látni fogjuk. Keményen megdolgozva tehát (és még nem tudjuk, de nagy-nagy erőforrás pazarlás árán) létrehoztunk egy sorba rendező algoritmus osztályt, mely biztosítja a csökkenő, a növekedő, és az index alapú hozzáférést az adott rendezetlen halmazhoz. Kevés időt töltöttünk vele, és azt csinálja, amire szükségünk van, ismerjük a hátrányait, de megteremtettük a lehetőségét annak is, hogy háttérben futtassuk, vagyis ha nem túl sok elemű rendezettség a cél, akkor ez így jó, ahogy van. Ez a meggondolás nagyon fontos! Nem a mindenáron való hatékonyság az első szempont, hanem az alkalmazás diktálta minimális ráfordítás és az eredmény szükségességének az aránya. Ha például a legnagyobb elemszám 10000 akkor ez az algoritmus még elmegy. Ha 1000 akkor meg kifejezetten jó. Ha azonban 100000 elemű sorbarendezésre van szükség, akkor bizony mélyebbe kell nyúlnunk képzeletbeli pénztárcánkba, hogy finanszírozzuk a hatékonyabb eredményt.

A konzolos alkalmazásban a főprogram az alábbi:

Ebben látható, hogy 10000 elemű véletlenszámokkal feltöltött tömb sorba rendezése az alábbi kimenetet produkálja:

7-2. ábra -

kepek3/12fejezet-7-2.jpg


Ugyanezt az algoritmust, vagyis a korábban elkészített osztályt egy windows form projektben alkalmazva, és az alábbi vizualitást kölcsönözve neki:

7-3. ábra -

kepek3/12fejezet-7-3.jpg


Ezen a form-ol állithatjuk az osztály egyes korábban definiált tulajdonságait, pl.: háttérben történő futtatás, prioritás beállítás, sleep funknció, eseménykövetés, process kijelzés, stb. A futási idő a következőképpen alakul:

7-4. ábra -

kepek3/12fejezet-7-4.jpg


7-5. ábra -

kepek3/12fejezet-7-5.jpg


Vagyis külön szálon futtatva még grafikus környezetben is már csak a negyede a futási idő, és ez ebben az esetben elegendő lehet, figyelemmel arra, hogy milyen gyorsan valósítottuk meg. Vagyis mindig mérlegeljük a hatékonyság és a ráfordítás arányát.

Most pedig nézzünk néhány megvalósítást létező algoritmusok alkalmazására.

7-6. ábra -

kepek3/12fejezet-7-6.jpg


Mint látható, a példa kitér néhány ismert algoritmus alkalmazására az alábbi interface alapján:

Az ICompare interface implementálása

Ha egy osztály megvalósítja az ICompare interface-t, melynek egy kötelező tagfüggvénye van, a Compare metódus, akkor a C# biztosítja a sorbarendezésének lehetőségét. Ezt csak azért mutatjuk meg, még az ismert rendezések előtt, hogy lássuk, milyen alapvetően beépültek a nyelvi elemek közé az algoritmusok. Használatuk azon alapszik, hogy a Compare metódus visszatér egy nagyobb vagy kisebb jelzéssel, és ez alapján, mint láttuk (vagyis a Compare metódus hívásával), az elemek összehasonlítása, majd a rendezése megoldható. Vegyünk egy olyan osztályt, mely megvalósítja az ICompare interface-t.

Az a tervünk, hogy megmutatjuk, hogy egy konténerben tárolt, az ICompare interface-t megvalósító osztály a konténernek egyik tagfüggvényével sorba rendezhető, vagyis minden algoritmus-írás nélkül is eredményre juthatunk, de ennek ellenére úgy véljük, az algoritmusok készítésének alapfokú elengedhetetlen. Tehát a fenti osztályból adott számú elemet egy ArrayList-ben tárolunk. A feladat az, hogy a tartalom rendezett legyen az osztályok OneValue értéke szerint.

A fenti kódból látszik, hogy a rendezés mindössze egy sor alkalmazásával megoldható.

7-7. ábra -

kepek3/12fejezet-7-7.jpg


Mint láttuk, az ICompare interface implementálásával a C# beépített konténerei képesek a tartalom adott szempont szerinti rendezésére, azonban ez nem mindig a legjobb megoldás, hiszen itt a tároló osztálynak ez nem egy végsőkig optimalizált metódusa, ami a legjobban illik a mi igényeinkhez, ezért szükség lehet ennél is hatékonyabb algoritmusokra. Vegyük sorba tehát ezek. Első legyen az ún. InsertSort, de még mielőtt belevágnánk, ismerjük meg az algoritmusok egyik legfontosabb mérőszámának, a futási idő képletének fogalmát, ami a bemenet függvényében a végrehajtáshoz szükséges időt jelenti. Ennek a jellemzőnek - amennyiben az algoritmus által kitűzött feladat véges számú lépésben megoldható - ismeretében becsülhetjük a rendszer órajele, illetve az egyes utasítás-végrehajtások által igényelt gépi ciklusok alapján a szükséges időt.

A következőkben konzolos projektben teszteljük a legismertebb rendezési algoritmusokat az alábbi szerkezetű projektben.

7-8. ábra -

kepek3/12fejezet-7-8.jpg


Az InsertSort.

Az insert sort működése azon alapszik, hogy halmaz elemeinek balról jobbra történő összhasonlítása során az éppen vizsgált elem a baloldali rendezett listába kerül beszúrással úgy, hogy a már rendezett halmaz jobbra történő blokkmozgatással biztosít helyet az beszúrandó elemnek. Ha például a kiinduló lista

6 8 1 4 9 5, akkor lépések a következők:

6 8 1 4 9 5,

1 6 8 4 9 5 ,

1 4 6 8 9 5,

1 4 5 6 8 9

A grafikus vizualizáción látszik a rendezett és a redezetlen halmazok pillanatnyi állapota.

7-9. ábra -

kepek3/12fejezet-7-9.jpg


Az InsertSort növekményes algoritmus. A számítási idő korlátos erőforrás. A futási idő képlete: c1∙n2, ahol n az elemszám Például: Ha egy gép 1 milliárd (1* 10^9) műveletet hajt végre 1 sec alatt, akkor egy 1 millió elemből álló tömb rendezéséhez szükséges idő t=(c1∙(10^6)^2)/10^9, ahol c1 egy n-től független állandó pl: 2, egy olyan állandó, amely a programban található utasítások számát reprezentálja. (milyen tömör a program). Ekkor t=( 2*(10^6)^2)/10^9=2000sec, ami 33min. Az insert sort működésének szemléltetése a kártyák sorbarendezéséhez hasonlít, amikor a rendezendő elemet a pakli adott részébe szúrjuk, miközben a felül lévő csomag eggyel feljebb kerül.

Az InsertSort használatára írt konzolos teszt a következő előkészített tömbön hajtódik végre:

Ezt követően az egyes insert sort változatok a következő futási képet adják:

7-10. ábra -

kepek3/12fejezet-7-10.jpg


A Buborék rendezés

Mellékeljük egy későbbi gyakorlat futási képét, amelyen éppen a buborék rendezés grafikus vizualizációját látjuk.

7-11. ábra -

kepek3/12fejezet-7-11.jpg


Nevét onnan kapta, hogy az eredmény bufferben, mely egyben az originál buffer is, soros olvasással és összehasonlítással a legkisebb elem egyre előrébb jut, akár a könnyű buborékok a nehezebb folyadékban. Részletesen:

A rendezés a sorozat (tömb) legvégéről, tehát fordítva az eleje felé indul. Hátulról minden T[b] elemet összehasonlítunk a megelőző elelmmel T[b-1]-el. Ha a követő elem (T[b]) kisebb, mint az előtte lévő megelőző elem, T[b-1], akkor a két elemet felcseréljük. A sorozat elejére érve a legkisebb elem a helyére kerül. Innen az elnevezés, a kisebb elemek úgy emelkednek, mint a könnyű buborékok a folyadékban. Amikor egy sorozat végén a legkisebb elem a helyére kerül, akkor a következő sorozat már rövidebb lesz eggyel, hiszen nem kell az elejéig menni, mert ott már a helyén van az eddigi legkissebb elem.

Egy menetben mindig egy elem helyretételére van mód az egyre rövidülő sorozatokban. A folyamat addig tart, míg a sorozat hossza már csak egy elem. A sorozat már rendezetté válhat a végső iteráció előtt is. Ez onnan látható, hogy a sorozat rendezésében nincs cserélendő elem. Ilyenkor az iteráció megszakítható. Ha pedig minden második iteráció végén a legnagyobb elemet a sor végével kicseréljük, vagyis nem csak felfelé, hanem lefelé is mozognak a buborékok, akkor a hatásfok javítható. Ez az ún. osszcilláló rendezés. Szokás az algoritmusk világában egy olyan kódszerű leírását adni a megvalósítandó feladatnak amit pszeudó kódnak hívunk:

Látható, hogy a magunk kreálta rendezéshez képest ez már sokkal jobban tervezett és hatékonyabb. Nincsenek árnyék bufferek, nincs felesleges iteráció és összehasonlítás, mert a feldolgozott elemek mind kiesnek a következő rendezési ciklusból. Bár sokkal jobb, mint a mi első algoritmusunk, az az általános vélemény, hogy nem túl gyors és gazdaságos. Ez azért van, mert létezik ennél jóval hatékonyabb megoldás is, mint az látni fogjuk.

Az ehhez tartozó leszármaztatott és az ISort interface-t megvalósító, az alaposztályból származó osztály az alábbi:

A konzolos tesztelési kód az alábbi:

A program futásának eredménye következő lesz:

7-12. ábra -

kepek3/12fejezet-7-12.jpg


A MaxMinSort generikus változata

A MaxMinSort a MaxItemSort generikus változata, a már korábban létrehozozott konzolos tesztelésű algoritmusunk továbbfejlesztése, melyben ráadásul kipróbálunk két iteratív technikát is, mert megvalósítjuk iteratív és rekurzív elven is a mag feladatot jelentő operációt. Továbbra sem fűzünk nagy reményeket a hatékonyságához, de legalább azt csinálhatunk vele, amit csak akarunk.

7-13. ábra -

kepek3/12fejezet-7-13.jpg


A MaxMinSort továbbfejlesztésénél igyekeztünk korábbi hátrányaiból lefaragni. A fenti képen látszik, hogy az eredmény buffer kétoldalról történő feltöltése valósul meg. Az algoritmus egyébként továbbra sem bonyolult, működése azon alapszik, hogy egy másolat tömbből egy eredmény tömbbe mindig az adott sorozat legnagyobb és legkisebb elemét emeljük át. Ezzel egyidőben egy másik tömbbel logikai értékkel jelezzük, hogy az adott indexű elemet már feldolgoztuk. Így a következő iteráció csak azok közül az elemek közül hozza a Max-ot és a Min-t amelyik még nincs feldolgozva. Persze alkalmazhatnánk buffer pozíció mutatókat és operálhatnánk az originális halmazban és ezzel a másolati tömb létrehozása kezelése stb. nélkülözhető lenne, de szemléletesség érdekében ettől most eltekintünk. Azt tapasztaljuk majd, hogy az iteratív változat sokkal gyorsabb, mint a rekurzív és ez szinte mindig így van, figyelemmel a rekurzió hívási veremkezeléséhez tartozó overhead-re (költség).

Először az iteratív megoldás kódját tekintsük át:

7-14. ábra -

kepek3/12fejezet-7-14.jpg


A rekurzív megoldásban a kilépési feltétel az az eset, amikor már csak egy feldolgozandó elem maradt.

7-15. ábra -

kepek3/12fejezet-7-15.jpg


A Selection sort

Már a mi kezdetleges MaxMinSort megvalósításunk tervezésénél is felmerült annak szükségessége, hogy ne használjunk másolati halmazt, hanem közvetlenül az eredeti halmazban végezzük el a szükséges helycseréket. Persze ehhez szükséges lenne tudnunk, hogy mely része a halmaznak rendezett és mely része rendezetlen. Nem jelenthet meglepetést, hogy erre a célra egy mutatót/indexet használunk, mely elválasztja az originális halmaz rendezett és rendezetlen részét egymástól. A Selection sort működése azon alapszik, hogy a rendezetlen halmaz legkisebb értékű elemét kicseréljük a rendezetlen halmaz első elemével, majd ezt az elemet a rendezett halmaz új felső határolójának állítjuk be, vagyis a következő ciklusú feldolgozásban már nem vesz részt. A leszármaztatott osztály kódja az alábbi:

7-16. ábra -

kepek3/12fejezet-7-16.jpg


Mint látható, ez a rendezés az eddigiekhez képest jobb hatásfokúnak, de még ennél is lesz jobb algoritmusunk.

A QuickSort

A QuickSort, mint a neve is mutatja, igen gyors algoritmus, és lássuk be, egy sorbarendezésnél ez talán a legfontosabb szempont. A gyors rendezés alapja az, hogy a halmaz egy tetszőleges kiválasztott eleméhez képest a baloldalra kisebb, a jobb oldalra nagyobb elemeket pakoljuk, majd ezekre, mint részhalmazokra, újra elvégezzük a sorba rendezést, amíg a lista teljesen rendezett nem lesz. Szokás kombinálni a pivot (halmaz határ jelző) halmazaira a selection sort-ot, ha a részhalmaz elemszáma kisebb, mint 10.

A projektben három változatot készítünk, itt azonban helytakarékosság érdekében csak egyet mutatunk meg részletesen.

7-17. ábra -

kepek3/12fejezet-7-17.jpg


Az eredmény magáért beszél, valóban egy nagyságrenddel gyorabb megoldást ad.

A főprogram kialakítása

Végezetül pedig megadjuk a konzolos főprogram listáját, mely a fentiekben bemutatott futási képeket produkálta. A főprogram kialakításánál igyekeztünk ez egyes részfeladatokat tesztelhető módon elkülöníteni és mellékeljük a komplett szabványos dokumentációt is.

A főprogram mellett, bár itt nem kapott helyet, készítettünk egy összehasonlító winform-os alkalmazást is, melyet a projekt tartalmaz.