Gibt es einen Zusammenhang zwischen Komplexität und Erreichbarkeit?

18

Ich habe kürzlich die zyklomatische Komplexität (McCabe) und die Erreichbarkeit von Software an der Uni untersucht. Heute sagte mein Dozent, dass es keine Korrelation zwischen den beiden Metriken gibt, aber ist dies wirklich der Fall?

Ich denke, es würde definitiv eine gewisse Korrelation geben, da weniger komplexe Programme (von den wenigen, die wir uns angesehen haben) hinsichtlich der Erreichbarkeit „bessere“ Ergebnisse zu haben scheinen.

Kennt jemand einen Versuch, die beiden Metriken zusammen zu betrachten, und wenn nicht, was wäre ein guter Ort, um Daten zu Komplexität und Erreichbarkeit für eine große (ish) Anzahl von Programmen zu finden?

Saladin Akara
quelle

Antworten:

2

Ich habe kürzlich die zyklomatische Komplexität (McCabe) und die Erreichbarkeit von Software an der Uni untersucht. Heute sagte mein Dozent, dass es keine Korrelation zwischen den beiden Metriken gibt, aber ist dies wirklich der Fall?

Eigentlich ja und nein.

Zuallererst wird die McCabe-Metrik für die zyklomatische Komplexität in einem Kontrollflussdiagramm berechnet, in dem Sie Ihren Quellcode in ein gerichtetes Diagramm abstrahieren, wobei Basisblöcke oder Anweisungen die Knoten und die Übergänge zwischen ihnen sind (entweder durch normalen Kontrollfluss nach unten) oder im Falle von konditionierten Sprüngen und Schleifen) Kanten. Die zyklomatische Komplexität kann hier grob als die Differenz zwischen der Anzahl der Kanten und der Anzahl der Knoten angesehen werden (wenn Sie davon ausgehen, dass Ihr gesamtes Programm keinen isolierten Code hat, dh Ihr Graph ist verbunden).

CC = E - N

Das Problem der Erreichbarkeit ist ein häufiges Problem in der Graphentheorie, das sich folgendermaßen ausdrücken lässt: Ist bei zwei Knoten A und B der Knoten B von Knoten A aus erreichbar, dh kann man B von A aus erreichen und die Kanten des Graphen korrekt verfolgen? Richtung? Es ist also wieder die Metrik, die auf das Kontrollflussdiagramm und nicht auf den Code anwendbar ist.

Es gibt verschiedene Möglichkeiten, dieses Problem auf das Kontrollflussdiagramm anzuwenden . Eine Möglichkeit ist die sogenannte "Variablen-Erreichbarkeitsanalyse", dh die Analyse bestimmt für die angegebene Variable, ob ihr Wert an einem bestimmten Programmpunkt noch verfügbar ist (diese Technik wird in der Softwareanalyse auch als Slicing bezeichnet). Ich habe auch nur einige Artikel gefunden, die diesen Begriff (und allgemein das Erreichbarkeitsproblem) für Multithread-Anwendungen verwenden .

Grundsätzlich kann man eine Korrelation zwischen dem CC und der Erreichbarkeit erkennen: Mit der Zunahme des CC nimmt auch das Verhältnis der Kanten zu den Knoten zu, und selbst bei einem gerichteten Graphen, bei dem die Richtung der Kante ebenfalls wichtig ist, kann man diese Zunahme spekulieren Die Anzahl der Kanten führt schließlich zu einer Erhöhung der verfügbaren Pfade im Graphen und damit zu einer Erhöhung der Erreichbarkeit entweder über direkte oder indirekte Verbindungen zwischen den Knoten. So ist die Antwort Ja hier.

Andererseits erfordert der Begriff der Erreichbarkeit in einer Umgebung mit mehreren Threads die Analyse eines sogenannten Supergraphen - und dies ist nicht so trivial. Eine Erhöhung der CC (hier " Synchronisationskomplexität " genannt) kann zu einer höheren Wahrscheinlichkeit eines Deadlocks in der Software führen und dadurch die Erreichbarkeit bestimmter Knoten / Codesegmente verringern. Daher ist "Nein" auch hier eine gültige Antwort .

Alexander Galkin
quelle
1

Ich kenne die Erreichbarkeit nicht, aber wenn es sich um ein Maß für Codepfade handelt, das niemals ausgeführt werden kann, sollte die zyklomatische Komplexität eine Art Obergrenze dafür sein.

Alex
quelle
0

Möglicherweise gibt es Statistiken dazu, aber ich würde sagen, dass es keine Korrelation gibt, da die eine nicht von der anderen abhängt und die Auswahl beim Entwurf eines Softwaresystems so ist, dass Sie dies beseitigen können.

In Bezug auf Daten der realen Welt kann eine starke Korrelation bestehen, die jedoch auf schlecht konzipierte Softwaresysteme zurückzuführen sein kann, die diese Korrelation nicht beseitigen. Es könnte sich um eine zufällige Korrelation handeln, da die Graphentheorie nicht ausreichend bekannt ist.

Rudolf Olah
quelle
1
Eins hängt vom anderen ab, ist Kausalität, nicht Korrelation.
JeffO