Zyklomatische Komplexität verstehen

11

Ich bin kürzlich auf Cyclomatic Complexity gestoßen und möchte versuchen, es besser zu verstehen.

Was sind einige praktische Codierungsbeispiele für die verschiedenen Faktoren, die zur Berechnung der Komplexität beitragen? Insbesondere für die Wikipedia-Gleichung von M = E − N + 2Pmöchte ich besser verstehen, was jeder der folgenden Begriffe bedeutet:

  • E = Anzahl der Kanten des Diagramms
  • N = Anzahl der Knoten des Graphen
  • P = Anzahl der angeschlossenen Komponenten

Ich vermute, dass entweder E oder N die Anzahl der Entscheidungspunkte (wenn, sonst wenn, für, für jeden usw.) in einem Codeblock ist, aber ich bin mir nicht ganz sicher, welcher der beiden oder was der andere bedeutet. Ich vermute auch, dass P sich auf Funktionsaufrufe und Klasseninstanziierungen bezieht, aber es gibt keine klare Definition, die ich sehen kann. Wenn jemand mit einigen klaren Codebeispielen ein wenig mehr Licht ins Dunkel bringen könnte, wäre dies hilfreich.

Als Follow-up, hat die zyklomatische Komplexität direkt Korrelat zu der Anzahl der Unit - Tests , die für 100% Pfadüberdeckung ? Zeigt beispielsweise eine Methode mit einer Komplexität von 4 an, dass 4 Komponententests erforderlich sind, um diese Methode abzudecken?

Beeinflussen reguläre Ausdrücke die zyklomatische Komplexität, und wenn ja, wie?

VirtuosiMedia
quelle
Ich habe festgestellt, dass Sie das Originalpapier von McCabe bei Wikipedia erhalten können und Google Books das Buch liefert, das McCabe für sein Originalpapier verwendet hat. Interessanterweise werden Sie dann feststellen, dass McCabe den ursprünglichen Satz falsch verwendet hat (und auch verwirrend erklärt, da er mit einem ungerichteten Graphen beginnen sollte und es nicht notwendig ist, ihn überhaupt stark zu verbinden), aber die Zahlen kommen trotzdem korrekt heraus ( Die richtige Formel wäre M = E + 1-N + P, aber da P immer 1 ist, passt es ...) Der Gedanke kommt auf, dass die moderne "Ausnahmebehandlung" einen Schraubenschlüssel in die Werke dieser Metrik wirft.
David Tonhofer
... und was ist mit rekursiven Aufrufen (möglicherweise über eine Funktionskette). Verschmilzt man die Funktionsgraphen? Wie wäre es mit einem Kurzschluss von booleschen Operatoren wie "&&". Geschützte Operatoren wie "ref? .X", die null ergeben, wenn ref null ist? Na ja, es ist nur eine andere Metrik. Aber es gibt hier einige Arbeiten für ein kleines Universitätsprojekt.
David Tonhofer

Antworten:

8

In Bezug auf die Formel: Knoten repräsentieren Zustände, Kanten repräsentieren Zustandsänderungen. Anweisungen bringen in jedem Programm Änderungen in den Programmstatus. Jede aufeinanderfolgende Anweisung wird durch eine Kante dargestellt, und der Status des Programms nach (oder vor ...) der Ausführung der Anweisung ist der Knoten.

Wenn Sie ( ifzum Beispiel) eine Verzweigungsanweisung haben, kommen zwei Knoten heraus, da sich der Status auf zwei Arten ändern kann.

Eine andere Möglichkeit, die Cyclomatic Complexity Number (CCN) zu berechnen, besteht darin, zu berechnen, wie viele "Regionen" in Ihrem Ausführungsdiagramm vorhanden sind (wobei "unabhängige Region" ein Kreis ist, der keine anderen Kreise enthält). In diesem Fall ist der CCN die Anzahl der unabhängigen Regionen plus 1 (was genau der Anzahl entspricht, die Sie in der vorherigen Formel erhalten haben).

Der CCN wird verwendet für Verzweigungsabdeckung oder Pfadabdeckung, welche das gleiche ist. Das CCN entspricht der Anzahl verschiedener Verzweigungspfade, die theoretisch in einer einzelnen Thread-Anwendung möglich sind (die Verzweigungen wie " if x < 2 and x > 5 then" enthalten können, die jedoch von einem guten Compiler als nicht erreichbarer Code abgefangen werden sollten). Sie müssen mindestens so viele verschiedene Testfälle haben (kann mehr sein, da einige Testfälle möglicherweise Pfade wiederholen, die von vorherigen abgedeckt wurden, aber nicht weniger, vorausgesetzt, jeder Fall deckt einen einzelnen Pfad ab). Wenn Sie einen Pfad nicht mit einem möglichen Testfall abdecken können, haben Sie nicht erreichbaren Code gefunden (obwohl Sie sich selbst beweisen müssen, warum er nicht erreichbar ist, wahrscheinlich x < 2 and x > 5lauern einige verschachtelte Codes irgendwo).

Was reguläre Ausdrücke betrifft - natürlich wirken sie sich wie jeder andere Code aus. Die CCN des Regex-Konstrukts ist jedoch wahrscheinlich zu hoch, um sie in einem einzelnen Komponententest abzudecken. Sie können davon ausgehen, dass die Regex-Engine getestet wurde, und das Verzweigungspotenzial der Ausdrücke für Ihre Testanforderungen ignorieren (es sei denn, Sie testen Ihre Regex-Motor natürlich).

littleadv
quelle
2
+1: Eigentlich müssen Sie darauf vertrauen, dass die Regex-Engine getestet wurde. Wenn Sie es nicht vertrauen, bekommen ein , dass Sie tun Vertrauen.
S.Lott
"Der CCN entspricht der Anzahl der verschiedenen Ausführungspfade, die in einer einzelnen Thread-Anwendung möglich sind." Dies ist falsch, da der CCN nur auf der Topologie des Codes basiert und nicht auf seiner Bedeutung . Ein guter Prozentsatz dieser Pfade kann möglicherweise nicht ausgeführt werden, da sie einen Eingabestatus erfordern, der nicht festgelegt werden kann (einige x sind beispielsweise 5 und auch weniger als 2). Ehrlich gesagt halte ich es für pervers, das CCN zu verwenden, um zu entscheiden, welche Testfälle ausgeführt werden sollen. CCN ist eine Nummer, die dem Entwickler mitteilt, dass Sie hier möglicherweise über Bord gegangen sind. Bitte überlegen Sie, ob Sie ein Refactoring durchführen möchten. Und selbst dann kann es gute Gründe für eine hohe CCN geben.
David Tonhofer
1
@ David hat einen Satz hinzugefügt, um das zu adressieren. CCN ist eine Zweigstellenabdeckung und es gibt nie gute Gründe für eine hohe CCN auf einer niedrigeren Ebene (im Allgemeinen empfehle ich die Durchsetzung pro einzelner Funktion).
Littleadv
Zweigabdeckung und Pfadabdeckung sind nicht gleich. Die Zweigabdeckung zielt darauf ab, alle Zweige abzudecken, während die Pfadabdeckung darauf abzielt, alle Kombinationen von Zweigen abzudecken.
Mouviciel
13

Einige Bemerkungen dazu, die ich untätig schreibe ...

Speziell für die Wikipedia-Gleichung von M = E - N + 2P

Diese Gleichung ist sehr falsch .

Aus irgendeinem Grund verwendet McCabe es zwar in seiner Originalarbeit ("A Complexity Measure", IEEE Transactions on Software Engineering, Vo .. SE-2, Nr. 4, Dezember 1976), jedoch ohne es zu rechtfertigen und nachdem er tatsächlich das Richtige zitiert hat Formel auf der ersten Seite, die ist

v (G) = e - v + p

(Hier wurden die Formelelemente neu beschriftet)

Insbesondere verweist McCabe auf das Buch C.Berge, Graphs and Hypergraphs (im Folgenden als G & HG abgekürzt). Direkt aus diesem Buch :

Definition (Seite 27 unten in G & HG):

Die zyklomatische Zahl v (G) eines (ungerichteten) Graphen G (der mehrere getrennte Komponenten haben kann) ist definiert als:

v (G) = e - v + p

Dabei ist e = Anzahl der Kanten, v = Anzahl der Eckpunkte, p = Anzahl der verbundenen Komponenten

Satz (Seite 29 oben in G & HG) (nicht von McCabe verwendet):

Die zyklomatische Zahl v (G) eines Graphen G ist gleich der maximalen Anzahl unabhängiger Zyklen

Ein Zyklus ist eine Folge von Scheitelpunkten, die am gleichen Scheitelpunkt beginnen und enden, wobei jeweils zwei aufeinanderfolgende Scheitelpunkte in der Folge im Diagramm nebeneinander liegen.

Intuitiv eine Reihe von Zyklen ist unabhängig , wenn keine der Zyklen kann durch Überlagerung der von den anderen Bereichen ausgebildet sein.

Satz (Seite 29 Mitte von G & HG) (wie von McCabe verwendet):

In einem stark verbundenen Graphen G ist die zyklomatische Zahl gleich der maximalen Anzahl linear unabhängiger Schaltungen.

Eine Schaltung ist ein Zyklus, bei dem keine Wiederholungen von Eckpunkten und Kanten zulässig sind.

Ein gerichteter Graph wird als stark verbunden bezeichnet, wenn jeder Scheitelpunkt von jedem anderen Scheitelpunkt aus erreichbar ist, indem die Kanten in der angegebenen Richtung durchlaufen werden.

Beachten Sie, dass wir hier von ungerichteten Graphen zu stark verbundenen Graphen übergegangen sind (die gerichtet sind ... Berge macht dies nicht ganz klar).

McCabe wendet nun den obigen Satz an, um einen einfachen Weg abzuleiten, um eine "McCabe Cyclomatic Complexity Number" (CCN) folgendermaßen zu berechnen:

Bei einem gerichteten Graphen, der die "Sprungtopologie" einer Prozedur darstellt (der Befehlsflussgraph), wobei ein bestimmter Scheitelpunkt den eindeutigen Eintrittspunkt und ein bestimmter Scheitelpunkt den eindeutigen Austrittspunkt darstellt (der Austrittspunktscheitelpunkt muss möglicherweise "konstruiert" werden). Erstellen Sie ein stark verbundenes Diagramm, indem Sie eine gerichtete Kante vom Austrittspunktscheitelpunkt zum Eintrittspunktscheitelpunkt hinzufügen, um den Eintrittspunktscheitelpunkt von jedem anderen Scheitelpunkt aus erreichbar zu machen.

McCabe geht nun davon aus (ziemlich verwirrend, könnte ich sagen), dass die zyklomatische Zahl des modifizierten Befehlsflussgraphen "unserer intuitiven Vorstellung von 'minimaler Anzahl von Pfaden' entspricht", und deshalb werden wir diese Zahl als Komplexitätsmaß verwenden.

Cool, also:

Die zyklomatische Komplexitätszahl des modifizierten Befehlsflussgraphen kann durch Zählen der "kleinsten" Schaltungen in dem ungerichteten Graphen bestimmt werden. Dies ist für Mensch oder Maschine nicht besonders schwierig, aber die Anwendung des obigen Theorems gibt uns eine noch einfachere Möglichkeit, es zu bestimmen:

v (G) = e - v + p

wenn man die Richtwirkung der Kanten außer Acht lässt.

In allen Fällen betrachten wir nur eine einzelne Prozedur, sodass im gesamten Diagramm nur eine verbundene Komponente vorhanden ist.

v (G) = e - v + 1.

Wenn man das ursprüngliche Diagramm ohne die hinzugefügte "Exit-to-Entry" -Kante betrachtet , erhält man einfach:

ṽ (G) = ẽ - v + 2

als ẽ = e - 1

Lassen Sie uns anhand des Beispiels von McCabe aus seiner Arbeit veranschaulichen:

McCabes Beispiel

Hier haben wir:

  • e = 10
  • v = 6
  • p = 1 (eine Komponente)
  • v (G) = 5 (wir zählen eindeutig 5 Zyklen)

Die Formel für die zyklomatische Zahl lautet:

v (G) = e - v + p

was 5 = 10 - 6 + 1 ergibt und so richtig!

Die "McCabe Cyclomatic Complexity Number", wie in seiner Arbeit angegeben, ist

5 = 9 - 6 + 2 (in der Arbeit werden keine weiteren Erklärungen dazu gegeben, wie)

was zufällig richtig ist (es ergibt v (G)), aber aus den falschen Gründen, dh wir verwenden:

ṽ (G) = ẽ - v + 2

und damit ṽ (G) = v (G) ... Puh!

Aber ist diese Maßnahme gut?

In zwei Worten: Nicht sehr

  • Es ist nicht ganz klar, wie das "Anweisungsflussdiagramm" einer Prozedur erstellt werden soll, insbesondere wenn Ausnahmebehandlung und Rekursion ins Bild treten. Beachten Sie, dass McCabe seine Idee auf Code angewendet hat, der in FORTRAN 66 geschrieben wurde , einer Sprache ohne Rekursion, ohne Ausnahmen und mit einer einfachen Ausführungsstruktur.
  • Die Tatsache, dass eine Prozedur mit einer Entscheidung und eine Prozedur mit einer Schleife dieselbe CCN ergeben, ist kein gutes Zeichen.

Geben Sie hier die Bildbeschreibung ein

David Tonhofer
quelle
1
@ JayElston Guter Fang. In der Tat. Fest!
David Tonhofer
1
Big +1 für die Verknüpfung mit dem Originalpapier. Viele der zu dieser Zeit verfassten Artikel sind für jeden mittelständischen Programmierer gut lesbar und sollten gelesen werden.
Daniel T.
1

Korreliert die zyklomatische Komplexität im Anschluss direkt mit der Anzahl der Unit-Tests, die für eine 100% ige Pfadabdeckung erforderlich sind?

Ja im Grunde. Es ist auch eine gute Idee, die zyklomatische Komplexität als Indikator für den Zeitpunkt der Umgestaltung zu verwenden. Nach meiner Erfahrung erhöhen sich Testbarkeit und Wiederverwendbarkeit bei niedrigerem CC erheblich (obwohl Sie praktisch sein sollten - nicht überrefaktorieren, und einige Methoden haben aufgrund ihrer Natur einen hohen CC -, ist es nicht immer sinnvoll, zu versuchen, ihn zu erzwingen niedriger).

Beeinflussen reguläre Ausdrücke die zyklomatische Komplexität, und wenn ja, wie?

Ja, wenn Sie genau sein möchten, obwohl die meisten Code-Analyse-Tools sie auf diese Weise nicht zu berücksichtigen scheinen. Reguläre Ausdrücke sind nur endliche Zustandsmaschinen, daher schätze ich, dass ihr CC aus dem FSM-Diagramm berechnet werden könnte, aber es wäre eine ziemlich große Zahl.

Daniel B.
quelle
+1 - Ich vermute, dass die Berechnung des CC für RegExes keine lustige Aufgabe ist.
VirtuosiMedia