ProgramozásMódszertan
12. előadás’2004[SzP1]
(vázlat)

1. Bevezetés – Programhatékonyság

A hatékonyság – a HELYES program minőségi jellemzője

Dimenziói:

· Idő

· Hely

· Bonyolultság

„Kiterjedése”:

· Globális – az algoritmus egy funkcionális egységére vonatkozik
Þ megkívánja a feladat, a megoldás „logikájának” ismeretét

· Lokális – (legtöbbször) a kód egy darabkájára vonatkozik[SzP2]
Þ nem igényli az algoritmus ismeretét (még a feladatét sem), cserében a programozási nyelv (ami most elsősorban a Turbo Pascal) lehetőségeit és korlátait annál inkább

2. Lokális hatékonyság

2.1. A végrehajtási idő csökkentése

2.1.1. Elvek

Itt elsősorban az általánosan figyelembe veendő „elveket” taglaljuk. Jórészt magától értetődőek, mégis megéri rendszerezni őket. Lássuk:

· konstans kifejezések fordítási időben vagy egyetlen konstansként –
½ helyett 0.5; ½*9.81 helyett Const g=9.81; gPer2=g/2

· gyors(abb) elérést lehetővé tevő típusok –
Real Þ Integer Þ Byte; String Þ Szám / Felsorolási típus[SzP3]
„kétértékű” String („Igaz”/„Hamis”, „Igen”/„Nem”, „Van”/„Nincs” …) Þ Char („I”/„H”, „I”/„N”, „V”/„N” …) Þ Boolean…

Fordítási példák – értékadások (TPROF – Disassembly-funkció felhasználásával)

· gyors típus-műveletek –
A*2^N helyett A ShL N[SzP4] , A Div 2^N helyett A ShR N,
A² helyett A*A, 2*A helyett A+A,
A:=A+1 helyett Inc(A), vagy Succ(A)

Fordítási példák – inkrementálások (TPROF – Disassembly-funkció felhasználásával)

i<=N ésmég T(X(i)) helyett i<=N és T(X(i))
vagy ugyanez Turbo Pascal-ul:

While {$B+}i<=N and T(X[i]){$B-} do Inc(i);

helyett

While i<=N and T(X[i]) do Inc(i);

Fordítási példák – logikai kifejezés teljes kiértékelése (TPROF – Disassembly-funkció felhasználásával)

· kifejezések ekvivalens, kevesebb vagy „olcsóbb” műveletet igénylővé alakítása –
not A£B helyett A>B;
(I<1) and (J<1) or (I>N) and (J<1) or (I<1) and (J>M) or (I>N) and (J>M) helyett (I<1 or I>N) and (J<1 or J>M[SzP5] );
I<Sqrt(N) helyett I*I<N,
Exp(A)*Exp(B) helyett Exp(A+B),
helyett [SzP6]

· Műveletek ekvivalens átalakításai[1] –

2.1.2. Programtranszformációk

A programtranszformációk némelyike (s egyik irányba végrehajtva) alkalmasak időrövidítésre is. Itt most nem részletezzük, lásd a korábbi előadásban!

2.1.3. A programozási nyelv szerepe

Az alábbiak a „trivialitásokon” túli nyelvi lehetőségekre mutat példát.

· Összetett szerkezetek értékadása és azonosságvizsgálata –

Const MaxN=4;
Type TPont=Record x,y,z: Real End;
      TIdom=Record
              db:Byte;
              pont:Array [1..MaxN] of TPont;
            End;
Const haromSzog:TIdom=(db:3;
                       pont:((x:0.0,y:0.0,z:0.0),
                             (x:-1.0,y:1.0,z:1.0),
                             (x:1.0,y:1.0,z:1.0)))
Var   p,q,r:TPont;
      pqr:TIdom;
…
If (p.x=r.x) and (p.y=r.y) and (p.z=r.z) then
Begin
q.x:=p.x; q.y:=p.y; q.z:=p.z;
End;
pqr.db:=haromSzog.db;
For i:=1 to 3 do
Begin
pqr.pont[i].x:=haromSzog.pont[i].x;
pqr.pont[i].y:=haromSzog.pont[i].y;
pqr.pont[i].z:=haromSzog.pont[i].z;
End;

helyett

If p=r then q:=p; [2]
pqr:=haromSzog;

· Kezdőértékadás –

Var haromSzog:TIdom;
…
haromSzog.db:=3;
haromSzog.pont[1].x:=0.0;
haromSzog.pont[1].y:=0.0;
haromSzog.pont[1].z:=z:0.0;
…

helyett[SzP7]

Const haromSzog:TIdom=(db:3;
                       pont:((x:0.0,y:0.0,z:0.0),
                             (x:-1.0,y:1.0,z:1.0),
                             (x:1.0,y:1.0,z:1.0)))

· Alprogramok „makrósítása” – C++ inline-ja
Eljárások/függvények/operátorok törzsének behelyettesítése a hívás helyénél az aktuális paraméterek a formális helyére történő behelyettesítése mellett.

· Feltételek –

If
kif(x)=1 then A(x) else if
kif(x)=2 then B(x) else if
kif(x)=3 then C(x)
else D(x);

helyett

Case kif(x) of
1 : A(x);
2 : B(x);
3 : c(x);
else D(x)
End;

· Ciklusok –

i:=N;
While i=>1 do
Begin
A(x,i); i:=i-1
End;

helyett

For i:=N downto 1 do
Begin
A(x,i)
End;

· Címszerinti paraméterátadás az értékszerinti helyett –

Procedure Eltol(Var hova:TPont;
honnan, mennyivel:TPont);
Begin
…
End;

helyett

Procedure Eltol(Var hova:TPont;
Const honnan, mennyivel:TPont);
Begin
…
End;

2.2. A helyfoglalás csökkentése

2.2.1. Elvek

· Kisebb helyfoglalású típusok –
Real Þ Integer Þ Byte; String Þ Szám / Felsorolási típus;
TDatum=Record ev,ho,nap:Word End Þ TDatum=Record ev:0..99; ho:0..12; nap:1..31 End Þ TDatum=1..100*12*31 Þ TDatum=Word

· Kiszámítható adatok mellőzése§–

TSzemely=Record szsz:String[11]; szulIdo:TDatum; … End

helyett

TSzemély=Record szsz:String[11]; … End[SzP8] ;

· Nagy helyigényű adatok kódolása^§ –
hónapnév helyett hónapsorszám

· Ismétlődő kódrészek alprogrammá egyesítése –
A programkód csökkentése általában nem kecsegtet túl nagy reménnyel. Így nagy hangsúlyt fektetni rá nem szabad. Mivel gyakorta jár a bonyolultság csökkentésével, ezért szólunk egyáltalán róla.
Függvények/eljárások definiálása és hívása. (Erre helyes programozási stílus alkalmazása esetén persze már az algoritmuskészítéskor sor kerülhet.)

2.2.2. Programtranszformációk

A programtranszformációk némelyike (s egyik irányba végrehajtva) alkalmasak helyfoglalás csökkentésre is. Itt most nem részletezzük, lásd a korábbi előadásban!

2.2.3. A programozási nyelv szerepe

· A lehető legkisebb méretű típus kiválasztása –
LongInt Þ Word/Integer Þ Byte/ShortInt;
(„Ffi”/„No”:) String Þ String[1] Þ Char/Boolean;
Intervallum típus: Integer Þ 1..31;
Felsorolási típus: String Þ String[8] Þ Integer Þ Byte Þ 1..7 Û TNap=(Hetfo, Kedd, Szerda, Csutortok, Pentek, Szombat, Vasarnap)

· Tömör ábrázolás –
Packed Array, Word-határ figyelmen kívül hagyása

· Címszerinti paraméterátadás az értékszerinti helyett –
a verembe nem a teljes struktúra, hanem csak a kezdőcíme kerül (l. az előbbi példát)

· Egyebek –
a végrehajtási idővel kapcsolatban elhangzott módszerek egyike-másika alkalmas arra is, hogy a program kód méretét is csökkentse:

o Feltételek

o Összetett szerkezetek

o Kezdőértékadás

2.3. Bonyolultság

Most csak előre utalunk: a kérdés összefügg a strukturáltság – objektum orientáltság kérdéskörével, így majd ott visszatérünk e kérdésre.

Előzetesen néhány kódolással is összefüggő „ötlet”:

· modulok [SzP9] használata (l. Crt, Crt22)

· kódrészek újrafelhasználhatósága – beillesztés (Pascal/C include-ja)

3. A hatékonyság mérése

3.1. A mérés tárgya – mit mérjünk

3.1.1. Végrehajtási idő

Mi célból mérünk?

· a program mely része lassú

· több „hasonmás” program közül melyik gyorsabb

· a programműködés „időtartománya” (minÞátlagÞmax)

Mit-hol mérünk?

· a teljes program végrehajtási időt

· egy-egy alprogram (programrész) végrehajtási idejét

„Dinamikus” (absztrakt) jellemzők mérése:

· egyes programrészek végrehajtási száma

· egyes adatokhoz fordulás mennyisége

3.1.2. Helyfoglalás

Mi célból mérünk?

· a programnak mekkora az összmemória-, háttértár-igénye

· mely adatokat lehet (kell) a memóriában tartani

· a programnak mekkora az „időszakonkénti” memóriaigénye (verem/dinamikus memória)

Fejlesztői rendszer adta információk

· kód és adatterület-méret (l. MAP)

· használt fájlok száma, helyfoglalása

Dinamikus jellemzők mérése:

· heap pillanatnyi/maximális mérete

· verem pillanatnyi/maximális mérete

3.1.3. Bonyolultság

„Ezt maj’ lekközelebb!”

3.2. A mérés módszere – hogyan mérjünk

3.2.1. Végrehajtási idő

Van elméleti módszer. Ennek célja meghatározni az átlagos M(t) végrehajtási időt.

Ehhez ismerni kell a program szerkezetét (a különböző végrehajtási u_i utak t(u_i) idejét), a bemenő adatok várható eloszlását (ami meghatározza az egyes utak P(u_i) előfordulási esélyét). így:

Praktikusabb a teszteken alapuló módszer. Lényege: bemenő adatok osztályokra bontása a végrehajtás szempontjából. A fenti képlet itt is alkalmazható, ha az u_i út helyett e_i ekvivalencia osztályt értünk.

3.2.2. Helyfoglalás

Az előzőhöz hasonlatosan…

3.3. A mérés eszközei – mivel mérjünk

3.3.1. Végrehajtási idő

· Beépített óra –

{ Időmérő betét }
Var KezdoIdo,VegIdo: LongInt;
IdoTartam: Real;

Procedure OraIndulj;
Var o,p,mp,szmp: Word;
Begin
GetTime(o,p,mp,szmp);
KezdoIdo:=Round(szmp+100*(mp+60.0*(p+60.0*o)));
End; {OraIndulj}

Procedure OraAllj;
Var o,p,mp,szmp: Word;
Begin
GetTime(o,p,mp,szmp);
VegIdo:=Round(szmp+100*(mp+60.0*(p+60.0*o)));
IdoTartam:=VegIdo-KezdoIdo;
End; {OraAllj}

· Gyakoriságszámlálás –
Az érintett kódrészekhez önálló számláló rendelése, és kezelése (kezdetben nullázni, minden egyes végrehajtáskor inkrementálni). L. a rekurzió és iterációról szóló gyakorlatok anyagában!

· Speciális fordítási környezetbeli szolgáltatások –
L. Turbo ProFiler-ről írottakat!

3.3.2. Helyfoglalás

A statikus és globális méretadatokat a fordító általában szolgáltatja. (l. MAP)

A dinamikusakhoz más eszközökhöz kell nyúlni:

· Gyakoriságszámlálás –
L. előbbi példát!

· Speciális fordítási környezetbeli szolgáltatások –

[1] Ez a példa már átmenet a globális hatékonyság felé…

[2] Feltéve, hogy a nyelvben a rekord-azonosság operáció értelmezve van.

§ Ez már talán inkább a globális hatékonysághoz sorolható, hiszen „távolabbra” hat az esetleges utólagos figyelembe vétele.

ProgramozásMódszertan 12. előadás’2004[SzP1] (vázlat)

1. Bevezetés – Programhatékonyság

Tartalom

ProgramozásMódszertan
12. előadás’2004[SzP1]
(vázlat)