Syklomaattinen monimutkaisuus

Ohjelman syklomaattinen monimutkaisuus on rakenteellinen (tai topologinen)  tietokoneohjelman monimutkaisuuden mitta . Toimenpiteen kehitti Thomas J. McCabe vuonna 1976.

Syklomaattista monimutkaisuutta laskettaessa käytetään ohjelman ohjausvuokaaviota . Graafin solmut vastaavat jakamattomia ohjelmakäskyryhmiä, ne on yhdistetty suunnatuilla reunoilla , jos toista solmua vastaava komentoryhmä voidaan suorittaa välittömästi ensimmäisen solmun komentoryhmän jälkeen. Syklomaattinen monimutkaisuus voidaan laskea myös yksittäisille funktioille , moduuleille , menetelmille tai luokille ohjelman sisällä.

McCabe käytti testauksessa syklomaattisen monimutkaisuuden laskentaa . Hänen ehdottamana menetelmänä oli testata jokainen lineaarisesti riippumaton reitti ohjelman läpi, jolloin tarvittavien testien määrä on yhtä suuri kuin ohjelman syklomaattinen monimutkaisuus. [yksi]

Kuvaus

Ohjelmakoodin syklomaattinen monimutkaisuus on ohjelmakoodin läpi kulkevien lineaarisesti riippumattomien reittien lukumäärä . Jos lähdekoodi ei esimerkiksi sisällä haarapisteitä tai silmukoita, niin monimutkaisuus on yksi, koska koodin läpi on vain yksi reitti. Jos koodissa on yksi lause IF, joka sisältää yksinkertaisen ehdon, koodissa on kaksi polkua: yksi, jos lauseen ehto IFon tosi, TRUEja toinen, jos FALSE.

Matemaattisesti strukturoidun ohjelman [2] syklomaattinen monimutkaisuus  määritetään käyttämällä suunnattua graafia , jonka solmut ovat reunoilla yhdistettyjä ohjelmalohkoja, jos ohjaus voidaan siirtää lohkosta toiseen. Sitten monimutkaisuus määritellään seuraavasti: [3] :

M = E − N + 2 P ,

missä:

M = syklomaattinen kompleksisuus, E = kaavion reunojen lukumäärä, N = kaavion solmujen lukumäärä, P = liitäntäkomponenttien lukumäärä .

Toinen muotoilu käyttää kaaviota, jossa jokainen lähtöpiste on yhdistetty sisääntulopisteeseen. Tässä tapauksessa graafi on vahvasti kytketty ja ohjelman syklomaattinen monimutkaisuus on yhtä suuri kuin graafin syklomaattinen luku (tunnetaan myös nimellä ensimmäinen Betti-luku ), joka määritellään [3]

M = E − N + P .

Tämän määritelmän voidaan ajatella laskevan graafissa olevien lineaarisesti riippumattomien syklien lukumäärän, toisin sanoen niiden syklien, jotka eivät sisällä muita syklejä. Koska jokainen poistumispiste on yhdistetty sisääntulopisteeseen, jokaiselle poistumispisteelle on vähintään yksi jakso.

Yksinkertaiselle ohjelmalle, aliohjelmalle tai menetelmälle P on aina 1. Syklomaattinen monimutkaisuus voi kuitenkin koskea useita tällaisia ​​ohjelmia tai aliohjelmia (esimerkiksi kaikkiin luokan menetelmiin ), jolloin P on yhtä suuri kuin kyseessä olevat aliohjelmat , koska jokainen aliohjelma voidaan esittää itsenäisenä graafin osana.

Voidaan osoittaa, että minkä tahansa strukturoidun ohjelman syklomaattinen monimutkaisuus, jossa on vain yksi aloituspiste ja yksi lähtökohta, vastaa kyseisen ohjelman sisältämien haarapisteiden (eli lauseiden iftai ehdollisten silmukoiden) lukumäärää plus yksi. [3] [4]

Syklomaattinen monimutkaisuus voidaan laajentaa ohjelmaan, jossa on useita lähtöpisteitä; tässä tapauksessa se on [4] [5]

π − s + 2,

missä:

π on ohjelman haarautumispisteiden lukumäärä, s  on poistumispisteiden lukumäärä.

Muodollinen määritelmä

Muodollisesti syklomaattinen monimutkaisuus voidaan määritellä suhteelliseksi Betti-luvuksi :

eli " graafin G ensimmäinen homologia terminaalisten solmujen t suhteen . Tämä on toinen tapa sanoa "lineaarisesti riippumattomien polkujen lukumäärä kaavion läpi tulosta lähtöön".

Syklomaattinen monimutkaisuus voidaan myös laskea absoluuttisen Betti-luvun suhteen (absoluuttista homologiaa käyttäen, ei suhteellista) yhdistämällä tietyn komponentin kaikki päätesolmut (mikä vastaa lähtöpisteiden yhdistämistä sisääntulopisteeseen), tässä tapauksessa uusi, laajennettu, kaavio

Sovellus

Kehityksen monimutkaisuuden rajoittaminen

Yksi McCaben alkuperäisistä käyttötavoista oli rajoittaa ohjelmien monimutkaisuutta kehityksen aikana. Hän suosittelee, että ohjelmoijia vaaditaan laskemaan kehittämiensä moduulien monimutkaisuus ja jakamaan moduulit pienempiin aina, kun näiden moduulien syklomaattinen monimutkaisuus ylittää kymmenen. [3] NIST sisällytti tämän käytännön Structural Testing -metodologiaan havainnolla, että McCaben alkuperäisen julkaisun jälkeen 10:n valinta on saanut vahvaa tukea, mutta joissain tapauksissa saattaa olla tarkoituksenmukaista lieventää rajoitusta ja sallia moduulien monimutkaisuus. 15. Tässä menetelmässä tunnustetaan, että joskus voi olla syitä ylittää sovittu raja. Tämä on muotoiltu suositukseksi: "Jokaisen moduulin syklomaattinen monimutkaisuus tulisi joko rajoittaa sovittuihin rajoihin tai antaa kirjallinen selitys siitä, miksi raja ylitettiin."

Sovellus ohjelmistotestauksessa

Toinen syklomaattisen monimutkaisuuden käyttötarkoitus on määrittää täydelliseen koodin peittoon vaadittavien testien määrä .

Se on hyödyllinen, koska M :n syklomaattisella kompleksisuudella on kaksi ominaisuutta tietylle moduulille :

Osana muita mittareita

Syklomaattista kompleksisuutta käytetään yhtenä parametrina ylläpidettävyysindeksissä [ 6 ] . 

Muistiinpanot

  1. ↑ AJ Sobey. Päätestireitti . Haettu 2. toukokuuta 2009. Arkistoitu alkuperäisestä 26. huhtikuuta 2012.
  2. ↑ Tässä termi "strukturoitu" tarkoittaa, että ohjelmalla on vain yksi poistumispiste.
  3. ↑ 1 2 3 4 McCabe. Monimutkaisuusmittari  // IEEE  Transactions on Software Engineering : päiväkirja. - 1976 - joulukuu. - s. 308-320 . Arkistoitu alkuperäisestä 29. joulukuuta 2009.
  4. ↑ 1 2 Belzer, Kent, Holzman ja Williams. Tietojenkäsittelytieteen ja -tekniikan tietosanakirja  (englanniksi) . - CRC Press , 1992. - S. 367-368.
  5. ↑ Harrison. Mccaben monimutkaisuusmitan soveltaminen usean poistumisen ohjelmiin  //  Software: Practice and Experience : Journal. - J Wiley & Sons, 1984. - lokakuu.
  6. ↑ Linda M. Laird, M. Carol Brennan John. Ohjelmiston mittaus ja arviointi: käytännön lähestymistapa. Wiley & Sons, 2006.