Ciklusok lépésszámának csökkentése, a ciklusmag végrehajtási idejének csökkentése, az adatok és a programszöveg helyfoglalásának csökkentése, a bonyolultság csökkentése

Hatékonyság

Háromféle szempont szerint vizsgáljuk:

végrehajtási idő	– gépfüggő

helyfoglalás	– függ az adat és program ábrázolásától (nyelv, implementáció)

bonyolultság szerint	– elsősorban a programozó felkészültségétől függ

A kód hatékonysága

Globális hatékonyság

Az algoritmus egészének, a programnak a hatékonyságáról van szó. A programtervezés része.

Végrehajtási idő csökkentése:

Ciklusok végrehajtási számának csökkentése

sorozat elemszámának csökkentése

sorozat részekre osztása (pl. Quicksort)

párhuzamos feldolgozás

gyakoriság szerinti rendezés (főleg keresési feladatokhoz)

csoportos feldolgozás

ciklustranszformáció

iterált típus megfelelő finomítása

(Halmaz: elemek közt nincs kapcsolat

Sorozat: minden elemet pontosan egy követ és előz meg, kivéve a két szélső elemet

Hierarchikus szerkezet: minden elemet egy előz meg, de több is követhet, kivéve az első

Hálós szerkezet: Az egyes elemeket megelőzőkből és a következőkből is több lehet. Feladattól függően megfelelő finomítást választva hatékony megoldást kaphatunk.)

rekurzív előállítás (Pl. faktoriális)

Ciklusmag végrehajtási idejének csökkentése

elágazás transzformálása indexeléssé

a kivételes eset kiküszöbölése

ciklusok szétválasztása

felesleges feltételek elhagyása

adatok előfeldolgozása (pl. ½ = 0,5)

az adatmozgatások számának minimalizálása (mutatók)

felesleges műveletek kiküszöbölése

Alapelvében más megoldás keresése

matematikai ismeretek kihasználása, specifikáció átírása

dinamikus programozás, stb.

A helyfoglalás csökkentése

Az adatok mennyiségének csökkentése (elsősorban sorozatoknál)

az indexes változók csökkentése

ciklusok összevonása

hézagosan kitöltött struktúrák tömörítése, optimalizálása
(változók szerkezetének átalakítása)

speciális szervezésű sorozatok definiálása (

adatterületek megosztása (pl. két vektor szemben, egy helyen)

adatelemek számítása

adatelemek kódolása (pl. hónapszám név helyett)

Programkód méretének csökkentése

azonos funkciók közös eljárásba foglalása

adatok előfeldolgozása

ciklusok összevonása

programkód adattá formálása

Lokális hatékonyság

A kód hatékonyságát vizsgáljuk, a program működését nem kell megérteni (formai vizsgálat!)

Végrehajtási idő csökkentése

Elvi tanácsok:

használjunk gyorsabb számolást lehetővé tevő adattípusokat

gyorsan végrehajtható műveleteket (pl. a*a, 2*a, a+a)

hozzuk egyszerűbb alakra az összetett feltételeket

kerüljük a különböző típusú adatokkal végzett műveleteket (+ konverzió)

egyszerűsítsük az algebrai kifejezéseket

képlettranszformáció (pl. a2x → ((a2)x, a*b=(2*a)*(b/2) ha b ps., a+a*(b-1) kül.)

konstansok előre történő kiszámítása (1/2=0,5)

részkifejezések helyett új változók használata

Programtranszformációk

összetett feltételek szétválasztása

elágazások felesleges feltételeinek elhagyása

elágazások összevonása

ciklusok összevonása

ciklustól független utasítások kiemelése

Programozási nyelv szerepe

értékadások speciális fajtáinak használata (tömbök, struktúra..)

mutató típus használata

speciális műveletek használata(succ, pred, inc,..)

speciális feltétel utasítások

tömbök használata

paraméterátadás (érték vagy cím szerint)

háttértárak megfelelő kezelése

Helyfoglalás csökkenése

Elvi tanácsok

használjunk kisebb helyfoglalást lehetővé tevő típusokat

ne tároljunk más adatokból kiszámítható adatokat

kódoljuk a hosszú szöveges információt tartalmazó adatokat

kódoljunk egy adatban több elemi adatot (dátum= nap+32*hónap+512*év)

Programtranszformációk

elágazásból utasítások kiemelése

elágazások felesleges feltételeinek elhagyása

elágazások összevonása

ciklusok összevonása

Programozási nyelv szerepe

tömör ábrázolás

adott méretű és pontosságú számítások

dinamikus memóriakezelés

alternatívák a rekordszerkezetben (ha bizonyos mezők nincsenek kitöltve)

háttértárak megfelelő kezelése

változó hosszúságú szövegtípus használata

eljárások használata

struktúrák kezelése

kezdőérték-adás

Bonyolultság csökkentése

Egy program akkor egyszerűbb a másiknál, ha kevesebb elágazás és ciklus van benne, egyszerűbbek a feltételek, kisebb a struktúrák egymásba-ágyazásának a mélysége, és absztrakcióval megértés- könnyítő fogalmakat alkotunk.

Szerkezeti bonyolultság: algoritmus bonyolultsága * adatok bonyolultsága

- algoritmus bonyolultsága: szerkezeti (pl. ciklusok száma), illetve kifejezés szerinti (műveletszám)

- adat bonyolultsága: a struktúrák és a hivatkozások számától, bonyolultságától függ

Algoritmus bonyolultsága

Algoritmus szerkezeti bonyolultsága

ciklikus bonyolultság = a programgráfban lévő döntések száma + 1

módosított ciklus bonyolultsága számpár: ([ciklus bonyolultsága], [ciklus bonyolultsága + az „és” és „vagy” műveletek száma])

mélységi bonyolultság = különböző mélységben lévő elágazások és ciklusok számának súlyozott összege + 1

absztrakciós bonyolultság = az eljárások számának megnövelve az egyes eljárások mélységi bonyolultságainak összegével

Kifejezés bonyolultsága

Műveletek számával megadható (értékadás, reláció, aritmetkiai/logikai/… műveletek, beírás, kiolvasás, eljárás-/függvényhívás)

paraméterek száma

kivételes eset kiküszöbölése

fiktív kezdőérték-adás

funkciók elhagyása

funkciók szétválasztása

adat-absztrakció (típusok, típusműveletek, típuskonstansok,… alkalmas használata)

Adat bonyolultsága

Adat szerkezeti bonyolultsága

Egy adattípus strukturális bonyolultságának nevezzük a típus definiálásában szereplő típuskonstrukciós eszközök számát.

Adatstruktúráló elemek egyszerűsítése: egyszerűsödik, ha kívül vannak a sorozatdefiniálók, belül a nem sorozatdefiniálók. A ciklus bonyolultsága ugyanis = a benne levő adatstruktúrák száma + 1

Műveletek bonyolultsága

hivatkozás: Egy adattípus hivatkozási bonyolultsága a leghosszabb hivatkozási mélyég, amit a felhasználónak használnia kell. pl. Rajzol(T.lap(i)) → minél kevésbé kelljen mélyre látni a struktúrában

műveletek száma: Egy típus műveleti bonyolultsága a típus független, egymással ki nem fejezhető műveleteinek a száma.

megértés szempontjából jó, ha kevés van, míg használat szempontjából a nagy a jó

Típuskonstrukciós eszközök összevonása pl. rekord különböző mezői azonos típusú sorozaton, amelyet helyettesítünk rekordok sorozatával.

Adatabsztrakció.

Informatika tanári szak államvizsga	5. Programozási módszertan – a program hatékonysága

Bálint Gergely Illés, 2002	4

Peter Szamoskozi

2004-06-21T17:57:04