Есть ли связь между сложностью и достижимостью?

18

Я недавно изучал цикломатическую сложность (McCabe) и доступность программного обеспечения в университете. Сегодня мой лектор сказал, что между этими двумя показателями нет корреляции, но так ли это на самом деле?

Я думаю, что определенно будет некоторая корреляция, поскольку менее сложные программы (из немногих, на которые мы смотрели), похоже, имеют «лучшие» результаты с точки зрения достижимости.

Кто-нибудь знает о каких-либо попытках взглянуть на эти две метрики вместе, и если нет, то что было бы хорошим местом для поиска данных как по сложности, так и по достижимости для большого числа программ?

Саладин Акара
источник

Ответы:

2

Я недавно изучал цикломатическую сложность (McCabe) и доступность программного обеспечения в университете. Сегодня мой лектор сказал, что между этими двумя показателями нет корреляции, но так ли это на самом деле?

На самом деле и да, и нет.

Прежде всего, чтобы напомнить вам, показатель McCabe для цикломатической сложности рассчитывается на графе потока управления, где вы абстрагируете свой исходный код в ориентированный граф с базовыми блоками или операторами, являющимися узлами, и переходами между ними (либо с помощью обычного потока управления вниз или в случае условных скачков и петель) являющихся ребрами. Цикломатическая сложность здесь может быть примерно (если вы считаете, что вся ваша программа не имеет изолированного кода, то есть ваш граф связан), если рассматривать разницу между числом ребер и числом узлов.

CC = E - N

Проблема достижимости - это общая проблема в теории графов, которая может быть выражена следующим образом: для двух узлов A и B это узел B, достижимый из узла A, то есть можно ли достичь B, начиная с A и следуя правильно по краям графа направление? Итак, снова метрика применима к графу потока управления, а не к коду.

Есть несколько способов применить эту проблему к графу потока управления . Одним из способов является так называемый «анализ достижимости переменной», означающий, что для данной переменной анализ определяет, доступно ли ее значение в определенной программной точке (этот метод также называется нарезкой в ​​программном анализе). Я также нашел только некоторые статьи, которые используют этот термин (и вообще проблему достижимости) для многопоточных приложений .

По сути, можно увидеть некоторую корреляцию между CC и достижимостью: с увеличением CC соотношение ребер и узлов также увеличивается, и даже в случае ориентированного графа, где также важно направление ребра, можно предположить, что увеличение число ребер в конечном итоге приводит к увеличению доступных путей в графе и, следовательно, к увеличению достижимости либо через прямые, либо через косвенные соединения между узлами. Итак, ответ здесь - да .

С другой стороны, понятие достижимости в многопоточной среде требует анализа так называемого суперграфа - и это не так тривиально. Увеличение CC (называемое здесь « сложностью синхронизации ») может привести к более высокой вероятности взаимоблокировки в программном обеспечении и тем самым снизить достижимость определенных узлов / сегментов кода. Поэтому «Нет» и здесь является правильным ответом .

Александр Галкин
источник
1

Я не знаком с достижимостью, но если это мера путей кода, которые никогда не могут быть выполнены, цикломатическая сложность должна быть своего рода верхней границей этого.

Алекс
источник
0

Может быть некоторая статистика по этому вопросу, но я бы сказал, что нет никакой корреляции, потому что одно не зависит от другого, и есть также выбор в разработке системы программного обеспечения, так что вы можете устранить это.

С точки зрения данных реального мира, может быть сильная корреляция, но это может быть связано с плохо разработанными программными системами, которые не устраняют эту корреляцию. Это может быть случайная корреляция из-за незнания теории графов.

Рудольф Олах
источник
1
Один зависит от другого - это причинно-следственная связь, а не корреляция.
ДжеффО