4. GQM. A szoftver mérete

m´ ert´ ekek Szoftvermetrik´ ak ´ es min˝ os´ egmenedzsment

Bod´ o Zal´ an GQM

mértékek ( ( (((a Szoftver( metrik´ k és min˝oségmenedzsment 4. GQM. A szoftver mérete

Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as

Bod´ o Zalán

Szoftver u ´jrafelhaszn´ alts´ aga

Babe¸s–Bolyai Tudom´ anyegyetem Matematika ´ es Informatika Kar

1/27


GQM

GQM – Goal, Question, Metric I Victor Basili (1940–), University of Maryland professzora1 I a m´ erési modell: I I

I

Goal (konceptu´ alis szint): soroljuk fel a f˝ o célokat Question (oper´ aci´ os szint): minden célhoz rendelj¨ unk kérdéseket, melyek megv´ alaszol´ as´ aval eld¨ onthet˝ o, hogy elért¨ uk-e a célt Metric (kvantitat´ıv szint): hat´ arozzuk meg, hogy mit kell mérn¨ unk a kérdések megv´ alaszol´ as´ ahoz

Bod´ o Zal´ an GQM Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

Példa (Fenton, 85. old)

1 Goal Question Metric Paradigm, https://www.cs.umd.edu/~basili/publications/technical/T89.pdf 2/27

Bels˝o és küls˝o attribútumok


Bod´ o Zal´ an

Mit mér¨ unk? I

Folyamat/processz (process) – szoftverrel kapcsolatos tevékenységek

I

Termék/produktum (product) – valamilyen kész´ıtmény, átadand´ o vagy dokumentum, amely egy folyamat-tevékenység eredménye

I

Er˝ oforrás (resource) – egy folyamat-tevékenység által megk¨ ovetelt entitások

GQM Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

Attrib´ utumok osztályozása: I

egy F/T/E bels˝ o attrib´ utumai azok, melyek az entitáson k¨ ozvetlen¨ ul mérhet˝ ok; egy ilyen attrib´ utum az entitás vizsgálata által mérhet˝ o, f¨ uggetlen¨ ul annak viselkedését˝ol

I

egy F/T/E k¨ uls˝ o attrib´ utumat csak u ´gy mérhet˝ ok, ha megfigyelj¨ uk, hogyan hat ki a F/T/E a k¨ ornyezetére; itt az entitás viselkedése a fontos, nem az entitás maga

3/27

Példa I

F: bels˝ o: valaminek az id˝ otartama (pl. fejlesztés), er˝ ofesz´ıtés, adott t´ıpus´ u incidensek száma; k¨ uls˝ o: megfigyelhet˝ oség, stabilitás


Bod´ o Zal´ an GQM Bels˝ o´ es k¨ uls˝ o attrib´ utumok

I

T: bels˝ o: méret, er˝ ofesz´ıtés, k¨ oltség; k¨ uls˝ o: reliability, maintainability, usability

A szoftver m´ eret´ enek m´ er´ ese

I

E: bels˝ o: méret (pl. fejleszt˝ oi csapat mérete), k¨ oltség (pl. fejlesztési eszk¨ oz¨ oké); k¨ uls˝ o: fejleszt˝ ok produktivitása

Ciklomatikus komplexit´ as

Halstead-f´ ele m´ ert´ ekek


4/27


A szoftver méretének mérése

Bod´ o Zal´ an

Követelmény Hossz

GQM

Terv

LOC

Kód

Halstead

Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek

Funkciópont Szoftver mérete

Funkcionalitás

Feature pont

Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

Objektumpont Use-case pont Komplexitás

Ciklomatikus komplexitás Újrafelhasználtság szintje

Újrafelhasználtság (Reuse)

Újrafelhasználtság gyakorisága Újrafelhasználtság sűrűsége

5/27


K´ odsorok sz´ ama (LOC) I

LOC – Lines Of Code (egyes helyeken SLOC (Source Lines Of Code)) I I I

I I

dokumentálás mértéke, s˝ ur˝ usége: CLOC /LOC hogyan számolják? I I I I

I

NCLOC vagy ELOC – non-commented LOC, effective LOC CLOC – commented LOC LOC = NCLOC + CLOC


minden sort (¨ ures sorokat is) mindent, kivéve az u ¨res sorokat és a kommenteket csak az utas´ıt´ asok sz´ aml´ al´ asa stb.

KLOC – 103 sor, MLOC – 106 sor (milli´ o), GLOC – 109 sor (milliárd)

El˝ onyei: I

egyszer˝ u és k¨ onnyen automatizálhat´ o

I

korrelál a programozási er˝ ofesz´ıtéssel (és a k¨ oltséggel) 6/27


H´ atr´ anyai:

I

nem pontos/homályos defin´ıci´ o

I

nyelvf¨ ugg˝ o

GQM

I

nem alkalmazhat´ o a fejlesztés korai szakaszaiban

Bels˝ o´ es k¨ uls˝ o attrib´ utumok

I

f¨ ugg a programoz´ o jártasságát´ ol, a használt fejlesztési metodol´ ogiát´ ol

A szoftver m´ eret´ enek m´ er´ ese

I

a k´ odsorok számának indokolatlan n¨ ovelésére ¨ oszt¨ on¨ ozhet

Ciklomatikus komplexit´ as

Oper´ aci´ os rendszer Windows NT 3.1 (1993) Windows NT 3.5 (1994) Windows NT 4.0 (1996) Windows 2000 (2000) Windows XP (2001) Windows Server 2003 (2003)

Bod´ o Zal´ an

MLOC 4–5 7–8 11–12 >29 45 50

Halstead-f´ ele m´ ert´ ekek


t´ abl´ azat : Néh´ any oper´ aci´ os rendszerekre vonatkoz´ o adat (Wikipedia).

7/27

Halstead-féle mértékek I

I

Maurice Howard Halstead, 1977 (Elements of Software Science) programsz´ ot´ ar: n = n1 + n2 , n1 a k¨ ul¨ onb¨ oz˝ o operátorok száma, n2 a k¨ ul¨ onb¨ oz˝ o operandusok száma;

I

programhossz: N = N1 + N2 , N1 az operátorok ¨ osszes el˝ ofordulásainak száma, N1 az operandusok ¨ osszes el˝ ofordulásainak a száma; ˆ = n1 log2 n1 + n2 log2 n2 becs¨ ult programhossz: N

I

n1∗ – a k¨ ul. operátorok minimális száma

I

n2∗ – a k¨ ul. operandusok minimális száma program t´ arhelym´ erete: V = N · log2 n

I

I

I I

I



a program fizikai megval´ os´ıt´ as´ at jellemzi a k¨ ovetkez˝ oképpen értelmezhet˝ o: adott program-megval´ os´ıt´ asnak a (minim´ alis) mérete; minim´ alis méret alatt az oper´ atorok és operandusok biteken val´ o (egyenletes eloszl´ as mellett optim´ alis) t´ arol´ as´ at értj¨ uk egyszer˝ ubben: a program t´ arol´ as´ ahoz sz¨ ukséges minim´ alis sz´ am´ u bit 8/27

Egy kis kit´ er˝ o Miért nem minimális szám´ u bitszámot határoz meg a log2 n? I mert nem kell mindent ugyanannyi biten t´ arolni I a gyakoribb szimb´ olumokat kevesebb biten kellene tárolnunk, a kevésbé gyakorikat pedig t¨ obb biten I megold´ as: optimális prefix k´ odok használata I

I

I

prefix k´ od = a k´ odszavak k¨ oz¨ ul egyik sem folytat´ asa a m´ asiknak a prefix k´ od megfelel egy f´ anak, ahol minden levélhez val´ o eljut´ askor egy k´ odsz´ ot kapunk optim´ alis k´ od (ha ismerj¨ uk a szimb´ olumok megjelenési val´ osz´ın˝ uségeit): Huffman-k´ od (David A. Huffman, 1925–1999, inform´ aci´ o- és k´ odelméleti problém´ akkal foglalkozott)



ALG 1 1: Minden forrásszimbólumhoz egy levelet rendelünk. 2: while 1 db. csúcshoz nem jutunk do 3: Megkeress¨ uk a k´ et legkisebb val´ osz´ın˝ us´ eggel rendelkez˝ o cs´ ucsot. 4: Ezeket ¨ osszevonjuk egy cs´ ucsba, az ´ elekhez rendre 0-t ´ es 1-et rendel¨ unk. A cs´ ucshoz rendelt val´ osz´ın˝ us´ eg a k´ et val´ osz´ın˝ us´ eg ¨ osszege lesz.

5: end while 6: Egy szimbólum kódját megkapjuk, ha a gyökért˝ol indulva összeolvassuk a szimb´ olumhoz vezet˝ ou ´ton lev˝ o c´ımk´ eket. 9/27

Huffman-kód Legyen X = {x1 , . . . , x5 }, p(x1 ) = 0.35, p(x2 ) = 0.2, p(x3 ) = 0.2, p(x4 ) = 0.15, p(x5 ) = 0.1, Y = {0, 1}. Keress¨ uk meg az ehhez tartoz´ o Huffman-k´ odot.



x1 kódja tehát 11, m´ıg x5 -é 100.

10/27


A Huffman-k´ od optim´ alis k´ od. I

I

az átlagos k´ odsz´ ohosszt akarjuk minimalizálni a val´ osz´ın˝ uségek f¨ uggvényében átlagos k´ odsz´ ohossz: E |f (X )| =

Bels˝ o´ es k¨ uls˝ o attrib´ utumok

n X

p(xi )|f (xi )|

i=1

ahol I I I


X a forr´ as´ abécé val´ osz´ın˝ uségi v´ altoz´ oja f a k´ od f (xi ) az xi k´ odszav´ anak a hossza

A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

Példa Legyen X = {a, b, c, d, e, f , g }, p(a) = 0.2, p(b) = 0.2, p(c) = 0.15, p(d) = 0.15, p(e) = 0.12, p(f ) = 0.11, p(g ) = 0.07. Huffman: E |f (X )| = 2.78 Shannon–Fano: E |f (X )| = 2.8

11/27

I

minim´ alis t´ arhelym´ eret: V ∗ = (2 + n2∗ ) log2 (2 + n2∗ ) I

I

∗

program absztrakci´ os szintje (level): L = V /V I

I I I

I

I

egy algoritmus implement´ al´ as´ ahoz sz¨ ukséges szellemi tevékenység


programoz´ asi id˝ o (programming time): 2n T = E /S = n1 N22nN2log , ahol S I

I

mennyire ide´ alisan ´ır´ odott a program

ˆ = 2n2 becs¨ ult absztrakci´ os szint (?): L n1 N2 program neh´ ezs´ ege (difficulty): D = 1/L sz¨ uks´ eges er˝ ofesz´ıt´ es (programming effort): N log2 n E = VL = n1 N22n 2 I

I

magyar´ azat (?): minim´ alisan n1∗ = 2 pl. C-ben, mert sz¨ ukséges egy main f¨ uggvény és a (. . . ) z´ ar´ ojelek


S a Stroud-féle (John M. Stroud, pszichol´ ogus) sz´ am, az emberi agy 1 m´ asodperc alatt végzett alapvet˝ o megk¨ ul¨ onb¨ oztetéseinek (mental discriminations) sz´ ama ezt szoftverfejleszt˝ ok esetében 18-ra becs¨ ulik (P. G. Hamer, G. D. Frewin: M. H. Halstead’s Software Science - A Critical Examination. 1982.), ´ altal´ aban pedig 5 és 20 k¨ oz¨ otti érték

program intelligens tartalma vagy informáci´ otartalma ˆ (intelligent content): I = LV stb. 12/27


Példa

Bod´ o Zal´ an

cin >> a ; cin >> b ; a = a + b; b = a - b; a = a - b; cout << a << " ," << b ;

GQM Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek

I

n1 = 7 (cin, >>, =, +, -, cout, ”<<)

I

n2 = 3 (a, b, ",")

I

N1 = 14

I

N2 = 14

I

programhossz: N = N1 + N2 = 28

I

becs¨ ult programhossz: ˆ = n1 log2 n1 + n2 log2 n2 = 19.6515 + 4.7549 = 24.4064 N

I

tárhelyméret: V = 28 log2 10 = 93.014 ˆ = 2n2 = 0.0612 becs¨ ult absztrakci´ os szint: L

I


n1 N 2

13/27

A Halstead-féle mértékek kritikái: I

val´ ojában assembly nyelvekre lett kitalálva

I

bizonyos mértékek defin´ıci´ oja nem pontos, nincsenek indokolva a dolgok

I

hogyan számoljuk ki az

n2∗

értékét?



14/27

Ciklomatikus komplexitás I

I

I

Thomas J. McCabe, 1976 (A Complexity Measure, IEEE Transactions on Software Engineering) gráfelméletben: ciklomatikus sz´ am = lineárisan f¨ uggetlen k¨ or¨ ok száma egy teljesen ¨ osszef¨ ugg˝ o gráfban mi mit jelent? I

I

I

teljesen ¨ osszef¨ ugg˝ o gr´ af = b´ armely cs´ ucsb´ ol b´ armely cs´ ucs elérhet˝ o line´ arisan f¨ uggetlen k¨ or¨ ok = a k¨ or¨ ok nem ´ırhat´ ok fel valamilyen, a halmazban szerepl˝ o m´ as k¨ or¨ ok line´ aris kombin´ aci´ ojaként



képlet: r =e −n+1

(val´ ojában r = e − n + c)

vagy ahol I I I

e az élek sz´ ama n a csom´ opontok (cs´ ucsok) sz´ ama c az o ¨sszef¨ ugg˝ o komponensek sz´ ama

15/27


Bod´ o Zal´ an

Ha c komponens¨ unk van: GQM

r=

c X

ei −

i=1

c X i=1

ni +

c X

1=e −n+c

i=1

Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek

Kapcsolat a s´ıkgráfokkal: I

Leonhard Euler (1707–1783, svájci matematikus): s´ıkgráfok

I

s´ıkgr´ af = felrajzolhat´ ou ´gy, hogy az élek ne metsszék egymást

I

Euler bebizony´ıtotta, hogy egy s´ıkgráf esetén igaz a köv. képlet: 2=n−e +r


ahol I I

I

n, e ua. mint ezel˝ ott r a régi´ ok sz´ ama, azaz az élek ´ altal alkotott, egym´ ast´ ol elhat´ arolt ter¨ uletek sz´ ama (nem o ¨sszetévesztend˝ oa ciklomatikus sz´ ammal!)

ha leszám´ıtjuk a k¨ uls˝ o ter¨ uletet, megkapjuk a ciklomatikus számot 16/27


A ciklomatikus komplexit´ as: v (G ) = e − n + 2c

vagy

v (G ) = p + 1

ahol I

I

I


p a predikátumcs´ ucsok (predicate nodes) száma (predikátumcs´ ucs = 2-es kimen˝ o fokszám´ u cs´ ucs, azaz a d¨ ontési/elágazási cs´ ucsok) (Mills. Mathematical Foundations for Structured Programming. IBM, 1972.) vez´ erl´ esfolyamgr´ af (control flow graph, CFG) = a program utas´ıtásainak szekvenciája, az utas´ıtások egymásutániságát ´ırja le irány´ıtott gráffal ábrázoljuk: minden csom´ opont a program egy utas´ıtásának felel meg, az élek a k¨ ovetkez˝ o utas´ıtást mutatja I

I I I

Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

proced´ ura csom´ opontok (procedure nodes) – kimen˝ o foksz´ am =1 predik´ atum csom´ opontok – kimen˝ o foksz´ am = 2 kezd˝ ocs´ ucs – bemen˝ o foksz´ am = 0 termin´ alis cs´ ucs – kimen˝ o foksz´ am = 0

(Ha ciklomatikus sz´ am → ciklomatikus komplexit´ as: egy k´ epzeletbeli ir´ any´ıtott ´ elt h´ uzunk a termin´ alis cs´ ucsb´ ol a kezd˝ ocs´ ucsba – ez magyar´ azza a +1-et a k´ epletben) 17/27

I

más megfogalmazás: f¨ uggetlen utak száma a kezd˝ ocs´ ucsból a terminális cs´ ucsba

I

f¨ uggetlen utak: a vezérlésfolyamgráfban egy u ´t f¨ uggetlen az el˝ oz˝ okt˝ ol, ha legalább egy u ´j él behozatala



18/27


S´ıkgráf, ciklomatikus szám és komplexitás

Bod´ o Zal´ an

I a

b

d

c

e

f

lineárisan f¨ uggetlen k¨ or¨ ok (a már kib˝ ov´ıtett gráfban): (abea), (beb), (abefa), (acfa), (adcfa) ((abebea) nem lehet, mert (abebea) = (ab) + (beb) + (ea))

I

ciklomatikus szám (a kib˝ov´ıtett gráfban): r = 10 − 6 + 1 = 5

I

a régi´ ok száma (a kib˝ ov´ıtetlen gráfban) = 5

I

ciklomatikus komplexitás (a kib˝ ov´ıtetlen gráfban): v (G ) = 9 − 6 + 2 = 5

I

predikátum csom´ opontok: ?

GQM Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

B

19/27


a1


a2

d

Bels˝ o´ es k¨ uls˝ o attrib´ utumok A szoftver m´ eret´ enek m´ er´ ese

b

c

Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

e1

e2

I

f

predikátum csom´ opontok: a1, a2, e1, e2 ⇒ p + 1 = 5

A gyakorlatban: elágazások megszámolása2 I if, case/switch I while, repeat/do-while, for 2 Megjegyz´ es: ha o ¨sszetett a d¨ ont´ esi felt´ etel (pl. and), akkor azt is sz´ et kell bontani 20/27

´ Ervek, ellen´ ervek: I mellette: I I

I

viszonylag k¨ onny˝ u kisz´ am´ıtani, k¨ onnyen automatiz´ alhat´ o komplexit´ as objekt´ıv mértéke

ellene: I

I

két ugyanakkora ciklomatikus komplexit´ assal rendelkez˝ o program k¨ ul¨ onb¨ oz˝ o programoz´ asi er˝ ofesz´ıtést jelenthet ugyanazon k¨ ovetelményeknek, specifik´ aci´ onak megfelel˝ o feladat k¨ ul¨ onb¨ oz˝ oképpen, k¨ ul¨ onb¨ oz˝ o ciklomatikus komplexit´ assal implement´ alhat´ o



K¨ usz¨ ob´ ert´ ek: I

egy bizonyos ciklomatikus komplexitás (szám) felett nagyobb a hiba val´ osz´ın˝ usége, illetve a karbantartás, debuggolás stb. is bonyolultabb, nehezebb

I

McCabe szerint ez a k¨ usz¨ obérték 10 (egy modulban)

21/27



Ciklomatikus komplexit´ as 1 − 10 11 − 20 21 − 50 > 50

Kock´ azat Egyszer˝ u program Komplex program, mérsékelt kockázat Komplex, magas kockázat Tesztelhetetlen program

A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as Szoftver u ´jrafelhaszn´ alts´ aga

t´ abl´ azat : Program/kock´ azat jellemzése a ciklomatikus komplexit´ as f¨ uggvényében (http://www.sze.hu/~heckenas/okt/swmet.pdf)

22/27

Szoftver u´jrafelhasználtsága I

I

a k´ od u ´jrafelhasználtságát (reuse) mérj¨ uk = mekkora részét másoltuk, m´ odos´ıtottuk? mit jelent az u ´jrafelhasználás? I I I I I

I

teljes programok u ´jrafelhaszn´ al´ as´ at modulokét, oszt´ alyokét f¨ uggvényekét, elj´ ar´ asokét f¨ uggvények részeit stb.



az u ´jrafelhasználtság mértékének definiálása (Software Productivity Consortium, 1995): I I

I

I

egy-az-egyben ´ atvett: ugyanaz kevés mértékben m´ odos´ıtott: a k´ odsorok kevesebb mint 25%-a m´ odosult nagy mértékben m´ odos´ıtott: a k´ odsorok t¨ obb mint 25%-a m´ odosult u ´j k´ od: 0% ´ atvett k´ od

(William Frakes, Carol Terry. Software Reuse: Metrics and Models. ACM Computing Surveys 28(2), pp. 415-435, 1996. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.8317)

23/27

Hogyan hat´ arozzuk meg k´ et dokumentum hasonl´ os´ ag´ at? 1. informáci´ o-visszakeresési modell: I

bag-of-words modell + koszinusz-hasonl´ os´ ag

2. dokumentumok ujjlenyomatainak meghatározása és azok osszehasonl´ıtása ¨ I

MOSS: https://theory.stanford.edu/~aiken/moss/ cikk: http://theory.stanford.edu/~aiken/ publications/papers/sigmod03.pdf

3. szintaxisfa/lexikális elemz˝ o alapján: I I I

szintaxisfa/token-lista felép´ıtése (a fa bej´ ar´ asa (pl.) preorder m´ odon) az ´ıgy kapott list´ ak o ¨sszehasonl´ıt´ asa (pl. a Levenshtein-t´ avols´ ag (edit distance) seg´ıtségével)



4. leghosszabb k¨ oz¨ os alsorozat (longest common subsequence, LCS) 5. . . .

24/27

Szerkeszt´ esi t´ avols´ ag (edit distance), Levenshtein-t´ avols´ ag I hogyan (= h´ any lépésben) kapjuk meg s1 -b˝ ol s2 -t (és ford´ıtva) I h´ arom m˝ uvelet: besz´ urás (insert), t¨ orlés (delete), helyettes´ıtés (replace)   M[i − 1, j − 1] +0, ha s1 [i] = s2 [j],       +1, k¨ ul¨ onben, (replace) M[i, j] = min M[i − 1, j] + 1 , (insert/delete)       M[i, j − 1] + 1 (insert/delete)

Példa (Manning, Raghavan, Schütze: Introduction to IR)



s1 = cats, s2 = fast

25/27


LCS

I

X = (x1 , x2 , . . . , xm ), Y = (y1 , y2 , . . . , yn )

I

prefix: Xi = (x1 , x2 , . . . , xi ) defin´ıci´ o:

I

( LCS(Xi , Yj ) =

∅ LCS(Xi−1 , Yj−1 ).xi hosszabbik(LCS(Xi , Yj−1 ), LCS(Xi−1 , Yj ))


ha i = 0 vagy j = 0 ha xi = yj ha xi 6= yj

A szoftver m´ eret´ enek m´ er´ ese Halstead-f´ ele m´ ert´ ekek Ciklomatikus komplexit´ as

Példa (Wikipedia)


X = GAC , Y = AGCAT

26/27



27/27

4. GQM. A szoftver mérete

Recommend Documents