Programozás módszertan (Hatékonyság-vizsgálat):


Fontos:

- algoritmus hatékonysága,

- programkód hatékonysága.

Vizsgálni kell:

- végrehajtási idő,

- helyfoglalás,

- bonyolultság (kevésbé fontos, csak átláthatóság, javítás szempontjából fontos).

- max. végrehajtási idő,

- átlagos végrehajtási idő,

- max., min., átlagos tárigény,

- programkód hossza.

 

Algoritmus hatékonysága:

- jó algoritmus,

- ciklusok végrehajtási száma (egymásba ágyazott ciklusok nagyon lassítják),

- egy ciklus végrehajtási ideje,

- feltételvizsgálat száma,

- kivételesetek kiküszöbölése.

 

Programkód hatékonysága:

- jó adattípusok (kis helyfoglalás, gyors számolás - a real számtípus nem szabványos, nem támogatja a koprocesszor),

- feltételek egyszerűsítése,

- lehetőleg ne használjunk különböző adattípusokat egy kifejezésben (átváltás miatt),

- függvények kiszámítását ritkán alkalmazzuk.

 

Hatékonysági program-transzformációk:

Ha F akkor U1;U2

különben U1;U3

U1
Ha F akkor U2
különben U3

Ha az F-et nem módosítja az U1.

Ha F akkor U2

különben U3

U1

Ha az utasítások sorrendje nem számít.

Ha F akkor U1;U3
különben U2;U3

Ha F akkor U1

különben U2

U3

Mindig megcsinálhatjuk.

Ha F1 és F2 akkor U

Ha F1 akkor

  Ha F2 akkor U

Akkor, ha F1 rövid, F2 bonyolult. (A Pascalban beállítható, hogy ne értékelje ki F2-t, ha F1 hamis.)

Ha F1 akkor U1

különben Ha F2 akkor U2

Ha F1 akkor U1

különben U2

Ha F1= NOT F2.

Ha F akkor U1

Ha F akkor U2

Ha F akkor U1;U2

Ha U1-nek nincs hatása F-re.

Ciklus amíg CF

  U1;U3

Cvége

Ciklus amíg CF

  U2;U3

Cvége

Ciklus amíg CF

  U1;U2;U3

Cvége

Ha U1 és U2 függetlenek egymástól, és nincsenek hatással CF-re, legfeljebb U3-ra.

U

Ciklus amíg Cf

  U

Cvége

Ciklus

  U

amíg CF

Mindig megcsinálhatjuk, de van, hogy nem célszerű.

Ciklus amíg CF

  Ha F akkor U

Cvége

Ha F akkor

  Ciklus amíg CF

    U

  Cvége

Ha F nem változik a ciklus futása alatt.

Ciklus amíg CF

  U1;U2

Cvége

U1

Ciklus amíg CF

  U2

Cvége

Ha az U1 végrehajtása független a ciklustól és saját maga korábbi végrehajtásától.

 

Program helyessége:

A program azt csinálja, amit szeretnénk?

- Bizonyítás (matematikai módszer): logikai, matematikai megközelítés -> bizonyítottan helyes.

- Empirikus (tapasztalati módszer): tesztelés -> valószínűleg helyes.

Empirikus módszer:

- tesztelés,

- hibakeresés (ha van hiba),

- hibajavítás (ha megtaláltuk a hibát)

Tesztelés:

Statikus

Dinamikus

A programot nem indítjuk el, csak a kódot nézzük.

Szintaktikai (formai) hibák ellenőrzése - ezt automatikusan tesztelik a modern programnyelvek.

Kód ellenőrzése <-> összevetni az algoritmussal.

Szemantikai (tartalmi) hibák ellenőrzése - ellentmondások kiküszöbölése (tipikus hiba: a változónak kell kezdőérték).

Vezérlési problémák ellenőrzése (pl. ciklus végessége).

Olyan elágazási ág ellenőrzése, amelyik sosem hajtódik végre.

Feketedoboz módszer:

1. Ekvivalens osztályokat képezünk az input adatokból. Az ekvivalens osztályok diszjunkt halmazok (nincs közös elemük). Az elemeik valamilyen szempontból azonosak.

Egy halmaz bármely elemét kiválaszthatjuk. Ha azzal az elemmel működik a program, akkor abból az osztály mindegyik elemével működik.

Pl. 40 karakteres szövegből számoljuk, hogy hány magánhangzót tartalmaz.

Ekvivalencia osztályok:

0 hosszú string,

40-nél hosszabb string,

csak mássalhangzókból áll,

van mássalhangzó is (csak 1, néhány, mindegyik).

Ennek előnye, hogy nem kell minden esetet megvizsgálni.

2. Határeset elemzés: az ekvivalens osztályok határeseteit külön tesztelni kell.

Pl. (az előző példánál maradva)

0, 1, 39, 40, 41

Fehérdoboz módszer:

Ismerjük a program kódját. A kódot kell vizsgálnunk.

Minden feltételágat kipróbálunk.

Utasításlefedés: mindet hajtsuk végre.

Részletlefedés: összetett feltételben minden ágat vizsgáljunk meg.

 

Hibakeresés:

- Indukció: hiba felfedezése után elképzelünk egy hibaokot, és arra vizsgáljuk. Ha nem az, akkor új hibaokot keresünk.

- Dedukció: ha rájövünk a hibára, akkor minden hibalehetőséget kizárunk, és egyenként vizsgáljuk.

- Visszalépéses módszer: megállítjuk a programot a hiba esetén, és visszafelé haladunk a program végrehajtásában, és keressük azt a pontot, ahol még jó volt.

Hibakeresés a gyakorlatban:

- Kiíratás

változóértéket,

rövid üzenetet.

- Állapotellenőrzés: nem mindig írunk ki üzenetet, csak feltétel esetekor. Új feltételeket hozunk létre.

- Töréspontok (Break-point): a megállási pontokat kritikus helyre tegyük (elé, közepére, végére).

- Nyomkövetés:

lépésenkénti végrehajtás (ciklusokat, eljárásokat, függvényeket egyben hajtsa végre),

ugrás a kurzorhoz,

visszafelé nyomkövetés (ilyen a SoftIce J)

változók értékének menet közbeni megváltoztatása.

Szűcs Tamás - szucs_t@freestart.hu