Zrozumienie cykliczności złożoności

Ostatnio spotkałem się ze złożonością cyklomatyczną i chciałbym spróbować to lepiej zrozumieć.

Jakie są praktyczne przykłady kodowania różnych czynników, które wpływają na obliczanie złożoności? W szczególności dla równania z Wikipedii M = E − N + 2Pchcę lepiej zrozumieć, co oznacza każdy z następujących terminów:

• E = liczba krawędzi wykresu
• N = liczba węzłów wykresu
• P = liczba podłączonych komponentów

Podejrzewam, że E lub N może być liczbą punktów decyzyjnych (jeśli, inaczej, forach, itd.) W bloku kodu, ale nie jestem do końca pewien, co to znaczy lub co drugi oznacza. Zgaduję również, że P odnosi się do wywołań funkcji i instancji klas, ale nie ma jasnej definicji, biorąc pod uwagę, że widzę. Pomogłoby to, gdyby ktoś rzucił nieco więcej światła na jasne przykłady kodu każdego z nich.

Jako kontynuacja, czy złożoność cyklomatyczna jest bezpośrednio skorelowana z liczbą testów jednostkowych potrzebnych do 100% pokrycia ścieżki ? Na przykład, czy metoda o złożoności 4 wskazuje, że potrzebne są 4 testy jednostkowe, aby objąć tę metodę?

Wreszcie, czy wyrażenia regularne wpływają na złożoność cyklomatyczną, a jeśli tak, to w jaki sposób?

Jeśli chodzi o wzór: węzły reprezentują stany, krawędzie reprezentują zmiany stanu. W każdym programie instrukcje wprowadzają zmiany w stanie programu. Każda kolejna instrukcja jest reprezentowana przez krawędź, a stan programu po (lub przed ...) wykonaniem instrukcji jest węzłem.

Jeśli masz instrukcję rozgałęziającą ( ifna przykład) - wtedy wychodzą dwa węzły, ponieważ stan można zmienić na dwa sposoby.

Innym sposobem obliczenia cyklicznej liczby złożoności (CCN) jest obliczenie liczby „regionów” na wykresie wykonania (gdzie „region niezależny” to koło, które nie zawiera innych kół). W tym przypadku CCN będzie liczbą niezależnych regionów powiększoną o 1 (co będzie dokładnie taką samą liczbą, jaką daje poprzednia formuła).

CCN jest używany do pokrycia rozgałęzień lub pokrycia ścieżki , który jest taki sam. CCN jest równy liczbie różnych ścieżek rozgałęzień teoretycznie możliwych w jednej aplikacji wątkowej (która może obejmować gałęzie takie jak „ if x < 2 and x > 5 then”, ale dobry kompilator powinien je uchwycić jako nieosiągalny kod). Musisz mieć co najmniej taką liczbę różnych przypadków testowych (może być więcej, ponieważ niektóre przypadki testowe mogą powtarzać ścieżki objęte poprzednimi, ale nie mniej, zakładając, że każdy przypadek obejmuje jedną ścieżkę). Jeśli nie możesz zakryć ścieżki jakimkolwiek możliwym przypadkiem testowym - znalazłeś nieosiągalny kod (chociaż musisz naprawdę udowodnić sobie, dlaczego jest on nieosiągalny, prawdopodobnie jakieś zagnieżdżone x < 2 and x > 5czające się gdzieś).

Co do wyrażeń regularnych - oczywiście mają one wpływ, jak każdy inny fragment kodu. Jednak CCN konstrukcji wyrażenia regularnego jest prawdopodobnie zbyt wysoki, aby pokryć go w pojedynczym teście jednostkowym, i można założyć, że silnik wyrażeń regularnych został przetestowany, i zignorować potencjał rozgałęzień wyrażeń dla potrzeb testowania (chyba że testujesz swój silnik regex, oczywiście).

Kilka uwag na ten temat, które bezczynnie piszę ...

W szczególności dla równania Wikipedii M = E - N + 2P

To równanie jest bardzo błędne .

Z jakiegoś powodu McCabe rzeczywiście używa go w swoim oryginalnym artykule („A Complexity Measure”, IEEE Transactions on Software Engineering, Vo .. SE-2, No.4, December 1976), ale bez uzasadnienia i po przytoczeniu właściwej formuła na pierwszej stronie, którą jest

v (G) = e - v + p

(Tutaj elementy formuły zostały ponownie oznaczone)

W szczególności McCabe odwołuje się do książki C.Berge, Graphs and Hypergraphs (w skrócie poniżej G&HG). Bezpośrednio z tej książki :

Definicja (strona 27 na dole G&HG):

Cyklomatyczna liczba v (G) (niekierowanego) wykresu G (który może mieć kilka odłączonych elementów) jest zdefiniowana jako:

v (G) = e - v + p

gdzie e = liczba krawędzi, v = liczba wierzchołków, p = liczba połączonych komponentów

Twierdzenie (strona 29 na górze G&HG) (nieużywane przez McCabe):

Cyklomatyczna liczba v (G) na wykresie G jest równa maksymalnej liczbie niezależnych cykli

Cykl jest sekwencją wierzchołków wyjściowych i kończących się na tym samym wierzchołek z każdymi dwoma kolejnymi wierzchołkami w sekwencji przylegających do siebie na wykresie.

Intuicyjnie zestaw cykli jest niezależny, jeśli żadnego z cykli nie można zbudować z innych poprzez nałożenie spacerów.

Twierdzenie (strona 29 środek G&HG) (używane przez McCabe):

Na silnie połączonym wykresie G liczba cykliczna jest równa maksymalnej liczbie liniowo niezależnych obwodów.

Obwód jest cykl bez powtórzeń wierzchołkach i krawędziach dozwolony.

Mówi się, że ukierunkowany wykres jest silnie połączony, jeśli każdy wierzchołek jest osiągalny z każdego innego wierzchołka, przechodząc przez krawędzie w wyznaczonym kierunku.

Zauważ, że tutaj przeszliśmy z niekierowanych wykresów do silnie powiązanych wykresów (które są skierowane ... Berge nie wyjaśnia tego całkowicie)

McCabe stosuje teraz powyższe twierdzenie, aby uzyskać prosty sposób obliczenia „McCabe Cyclomatic Complexity Number” (CCN) w ten sposób:

Biorąc pod uwagę ukierunkowany wykres reprezentujący „topologię skoku” procedury (wykres przepływu instrukcji), z wyznaczonym wierzchołkiem reprezentującym unikalny punkt wejścia i wyznaczonym wierzchołkiem reprezentującym unikalny punkt wyjścia (wierzchołek punktu wyjścia może wymagać „zbudowania” dodając go w przypadku wielu powrotów), utwórz silnie połączony wykres, dodając skierowaną krawędź od wierzchołka punktu wyjścia do wierzchołka punktu wejścia, dzięki czemu wierzchołek punktu wejścia będzie osiągalny z dowolnego innego wierzchołka.

McCabe twierdzi teraz (raczej myląco mogę powiedzieć), że cykliczna liczba zmodyfikowanego wykresu przepływu instrukcji „jest zgodna z naszym intuicyjnym pojęciem„ minimalnej liczby ścieżek ””, więc wykorzystamy tę liczbę jako miarę złożoności.

Fajnie, więc:

Cyklomatyczną liczbę złożoności zmodyfikowanego wykresu przepływu instrukcji można określić, zliczając „najmniejsze” obwody na niekierowanym wykresie. Nie jest to szczególnie trudne dla człowieka lub maszyny, ale zastosowanie powyższego twierdzenia daje nam jeszcze łatwiejszy sposób jego ustalenia:

v (G) = e - v + p

jeśli pominąć kierunkowość krawędzi.

We wszystkich przypadkach bierzemy pod uwagę tylko jedną procedurę, więc na całym wykresie jest tylko jeden podłączony element, a więc:

v (G) = e - v + 1.

W przypadku rozważenia oryginalnego wykresu bez dodanej krawędzi „wyjścia do wejścia” , uzyskuje się po prostu:

ṽ (G) = ẽ - v + 2

jako ẽ = e - 1

Zilustrujmy to na przykładzie McCabe z jego artykułu:

Mamy tutaj:

• e = 10
• v = 6
• p = 1 (jeden składnik)
• v (G) = 5 (wyraźnie liczymy 5 cykli)

Wzór na liczbę cykliczną mówi:

v (G) = e - v + p

co daje 5 = 10 - 6 + 1 i tak jest poprawne!

„Cyklomatyczna liczba złożoności McCabe'a” podana w jego pracy to

5 = 9 - 6 + 2 (w artykule nie podano dalszych wyjaśnień)

które okazuje się być poprawne (daje v (G)), ale z niewłaściwych powodów, tj. używamy:

ṽ (G) = ẽ - v + 2

a zatem ṽ (G) = v (G) ... uff!

Ale czy ten środek jest dobry?

W dwóch słowach: niezbyt

• Nie jest całkowicie jasne, jak ustanowić „wykres przepływu instrukcji” procedury, szczególnie jeśli obsługa wyjątków i rekurencja wchodzą w obraz. Zauważ, że McCabe zastosował swój pomysł do kodu napisanego w FORTRAN 66 , języku bez rekurencji, bez wyjątków i prostej strukturze wykonywania.
• Fakt, że procedura z decyzją i procedura z pętlą dają ten sam CCN, nie jest dobrym znakiem.

• Jeszcze mniej dobry jest fakt, że forpętle i whilepętle są obsługiwane w ten sam sposób (zauważ, że w C można nadużywać fordo wyrażania whilew inny sposób; tutaj mówię o ścisłej for (int i=0;i<const_val;i++)pętli). Wiemy z teoretycznej informatyki, że te dwie konstrukcje dają całkowicie różne moce obliczeniowe: funkcje prymitywno-rekurencyjne, jeśli jesteś tylko wyposażony for, częściowe funkcje μ-rekurencyjne, jeśli jesteś wyposażony while.
• Eksperyment mający ekspertów ocenić złożoność kodu pokazuje, że CCN nie oddają ideę „kodu złożoności”, a także innych środków, w szczególności nauki oprogramowania Halstead za i Shao and Wangs' poznawczego rozmiaru funkcjonalnego (ten ostatni jest najwyraźniej zwycięzca), patrz: Zastosowanie trzech wskaźników złożoności poznawczej, Międzynarodowa konferencja nt. postępów w dziedzinie technologii informacyjno-komunikacyjnych w regionach wschodzących, 12–15 grudnia 2012 r.
• Weryfikacja empiryczna pokazuje, że (przynajmniej w przypadku dojrzałego kodu) CCN jest silnie skorelowana liniowo z LOC (liniami kodu), tj. CCN zwiększa się naturalnie wraz z długością procedury i równie dobrze można użyć liczby LOC do wyrażenia złożoności. Lepszym miernikiem niż bezwzględny CCN może być CCN / LOC. Zobacz w szczególności: Ponownie przeanalizowane wskaźniki złożoności cyklicznej - DSpace @ MIT i Rola empiryzmu w poprawie niezawodności przyszłego oprogramowania

Jako kontynuacja, czy złożoność cyklomatyczna jest bezpośrednio skorelowana z liczbą testów jednostkowych potrzebnych do 100% pokrycia ścieżki?

Tak, w zasadzie. Dobrym pomysłem jest również wykorzystanie złożoności cyklomatycznej jako wskaźnika tego, kiedy dokonać refaktoryzacji. Z mojego doświadczenia wynika, że ​​testowalność i możliwość ponownego użycia znacznie się zwiększają dla niższego CC (chociaż powinieneś być praktyczny - nie przesadzaj, a niektóre metody będą miały wysokie CC ze względu na ich naturę - nie zawsze ma sens próbować je wymusić niższy).

Wreszcie, czy wyrażenia regularne wpływają na złożoność cyklomatyczną, a jeśli tak, to w jaki sposób?

Tak, jeśli chcesz być dokładny, chociaż większość narzędzi do analizy kodu nie bierze ich pod uwagę w ten sposób. Wyrażenia regularne są po prostu skończonymi maszynami stanu, więc przypuszczam, że ich CC można obliczyć na podstawie wykresu FSM, ale byłaby to dość duża liczba.