Czy istnieje korelacja między złożonością a osiągalnością?

18

Ostatnio badałem złożoność cykliczną (McCabe) i dostępność oprogramowania na uni. Dzisiaj mój wykładowca powiedział, że nie ma korelacji między tymi dwoma miernikami, ale czy tak naprawdę jest?

Sądzę, że na pewno istnieje pewna korelacja, ponieważ mniej złożone programy (z niewielu, na które patrzyliśmy) wydają się mieć „lepsze” wyniki pod względem osiągalności.

Czy ktoś wie o jakiejkolwiek próbie spojrzenia na te dwa wskaźniki razem, a jeśli nie, to co byłoby dobrym miejscem do znalezienia danych dotyczących zarówno złożoności, jak i osiągalności dla dużej (ish) liczby programów?

Saladin Akara
źródło

Odpowiedzi:

2

Ostatnio badałem złożoność cykliczną (McCabe) i dostępność oprogramowania na uni. Dzisiaj mój wykładowca powiedział, że nie ma korelacji między tymi dwoma miernikami, ale czy tak naprawdę jest?

Właściwie zarówno tak, jak i nie.

Przede wszystkim, dla przypomnienia, metryka McCabe dla cykliczności złożoności jest obliczana na grafie kontrolnym, gdzie abstrakcyjny kod źródłowy jest kierowany na grafie z podstawowymi blokami lub instrukcjami będącymi węzłami i przejściami między nimi (albo przez normalny przepływ kontrolny w dół lub w przypadku uwarunkowanych skoków i pętli) będących krawędziami. Cyklomatyczna złożoność może być z grubsza (jeśli weźmiesz pod uwagę, że cały program nie ma izolowanego kodu, tj. Wykres jest podłączony), postrzegana jako różnica między liczbą krawędzi i liczbą węzłów.

CC = E - N

Problem osiągalności jest powszechnym problemem w teorii grafów, który można wyrazić w następujący sposób: biorąc pod uwagę dwa węzły A i B, węzeł B jest osiągalny z węzła A, tzn. Czy można dotrzeć do B, zaczynając od A i prawidłowo podążając za krawędziami wykresu kierunek? Tak więc znowu metryka ma zastosowanie do grafu przepływu sterowania, a nie do kodu.

Istnieje kilka sposobów zastosowania tego problemu do grafu kontrolnego . Jednym ze sposobów jest tak zwana „analiza osiągalności zmiennej”, co oznacza, że ​​dla danej zmiennej analiza określa, czy jej wartość jest nadal dostępna w pewnym punkcie programu (technika ta jest również nazywana krojeniem w analizie oprogramowania). Znalazłem również tylko niektóre artykuły, które używają tego terminu (i ogólnie problem osiągalności) dla aplikacji wielowątkowych .

Zasadniczo widać pewną korelację między CC a osiągalnością: wraz ze wzrostem CC stosunek krawędzi do węzłów również wzrasta, a nawet w przypadku wykresu ukierunkowanego, w którym kierunek krawędzi jest również ważny, można spekulować, że wzrost liczba krawędzi ostatecznie prowadzi do zwiększenia dostępnych ścieżek na wykresie, a tym samym do zwiększenia osiągalności poprzez bezpośrednie lub pośrednie połączenia między węzłami. Tak więc odpowiedź brzmi: tak .

Z drugiej strony pojęcie osiągalności w środowisku wielowątkowym wymaga analizy tak zwanego supergraftu - i nie jest to takie trywialne. Wzrost CC (zwany tutaj „ złożonością synchronizacji ”) może prowadzić do wyższego prawdopodobieństwa zakleszczenia w oprogramowaniu, a tym samym zmniejszyć osiągalność niektórych węzłów / segmentów kodu. Dlatego też „Nie” jest tutaj poprawną odpowiedzią .

Alexander Galkin
źródło
1

Nie znam osiągalności, ale jeśli jest to miara ścieżek kodu, których nigdy nie można wykonać, złożoność cykliczna powinna być czymś w rodzaju górnej granicy tego.

alex
źródło
0

Mogą istnieć pewne statystyki na ten temat, ale powiedziałbym, że nie ma korelacji, ponieważ jedna nie zależy od drugiej i istnieje również wybór w projektowaniu systemu oprogramowania, który można to wyeliminować.

Jeśli chodzi o dane ze świata rzeczywistego, może istnieć silna korelacja, ale może to wynikać ze źle zaprojektowanych systemów oprogramowania, które nie eliminują tej korelacji. Może to być przypadkowa korelacja z powodu braku wiedzy na temat teorii grafów.

Rudolf Olah
źródło
1
Jednym zależnym od drugiego jest związek przyczynowy, a nie korelacja.
JeffO