Em relação a complexidade de algoritmos, observei que existem diversas citações sobre complexidade ciclomática. O que é complexidade ciclomática? Em qual situação é importante analisar essa complexidade?
-
2Veja na wikipedia ou na wikipedia em inglês.– Victor StafusaCommented 29/03/2017 às 17:01
-
@VictorStafusa minha avó dizia que o wikipedia qualquer pessoa pode colocar qualquer coisa. Pensando nisso, eu prefiro saber daqui dos auto qualificados usuários do nosso SOpt; É quase que óbvio que a maioria das perguntas não só sobre terminologia tem lá no wikipedia, porque tem que ter aqui então? A tag é inútil?– vianaCommented 29/03/2017 às 17:06
-
1Não é nada disso. É verdade que qualquer um pode editar na wikipedia, mas isso não a desmerece, ainda assim o conteúdo de lá é normalmente (mas nem sempre) muito bom (assim como ocorre aqui). Ocorre que não tenho tempo para te dar uma resposta completa e detalhada (quem tiver, que siga em frente e escreva uma), mas a wikipedia já te dá um caminho e se você (ou outra pessoa) tiver com pressa para saber, dá para dar uma olhada lá. Além disso, isso também serve para definir um ponto de referência, qualquer resposta por aqui que seja inferior ao que está lá deveria ser melhorada.– Victor StafusaCommented 29/03/2017 às 17:10
-
@VictorStafusa isso é fato, as vezes as respostas aceitas aqui são bem inferiores. Mas a minha intenção é que fique registrado também aqui no SO, para também futuras referências.– vianaCommented 29/03/2017 às 17:29
2 Respostas
É uma medida de complexidade de um algoritmo onde é considerado os caminhos independentes que o algoritmo pode tomar. Quanto maior a complexidade ciclomática mais difícil de acompanhar o código, de dar manutenção, testar e fazer cobertura total.
A complexidade ciclomática aumenta sempre que existe um branch, mas algumas formas de branch podem gerar caminhos mais difíceis de acompanhar do que outros. Quanto mais linear, mais fácil é acompanhar o código.
Uma saída da função não deixa de ser um branch e conta para aumentar a complexidade ciclomática, portanto não existe função de CC 0.
Por isso usar vários return
ou eventualmente o uso do goto
pode aumentar ou diminuir a complexidade ciclomática dependendo de como forem usados, ainda que possa prejudicar outro aspecto.
Funções grandes tendem a ter maior complexidade ciclomática. É muito raro conseguir fazer algo grande sem branches.
A análise passa for representar o fluxo de execução através de um grafo. Um exemplo pego da Wikipedia:
Esse código tem CC 3 já que existem 2 branches típicos (um laço e um condicional) e 1 ponto de saída.
O desenvolvedor médio só precisa saber que deve manter a complexidade baixa simplificando os caminhos possíveis. Isso facilita muito seu trabalho e diminui a quantidade de problemas que podem ocorrer. Questões mais matemáticas são úteis para cientistas da computação ou engenheiros que precisam trabalhar com desenvolvimento mais formal ou rotinas muito otimizadas.
Um ponto a se considerar é que quebrar uma função em várias pode diminuir a CC desta função, mas não diminui a CC do algoritmo como um todo. Pode até aumentar. Algumas pessoas podem dizer que pelo menos fica mais fácil testar, e isso até é verdade para o teste individualizado que tem pouco valor, você ainda precisa testar todas situações e isso tem que considerar os resultados produzidos pelas funções auxiliares.
Problemas como um todo tem um limite do que dá para reduzir a CC. O que o desenvolvedor pode fazer é diminuir onde há CC em exagero, o desnecessário.
Em qual situação é importante analisar essa complexidade?
Em qualquer situação que não seja um código trivial e talvez descartável seria bom pensar sobre isso e ver se pode simplificar algo.
Existem ferramentas para medir a complexidade ciclomática do seu código em diversas linguagens, algumas até sugerem uma refatoração que pode simplificar. Então você não precisa perder tempo fazendo manualmente.
Um exemplo que mostra até concretamente como ela faz a conta.
Outras métricas
Reforço que ela sozinha não é uma boa indicação de qualidade de código. Você pode diminuir a CC e o código ficar pior. Você pode optar pelo polimorfismo e passar ter decisões intrínsecas e a execução passar ter mais diferenças de execução.
Algo me chamou atenção estudando o assunto e não ficou tão claro se a complexidade de algoritmo é sobre a quantidade caminhos possíveis ou a quantidade de decisões a serem consideradas. Vi materiais divergentes sobre isso, quando ficava ambíguo por usar termos que ninguém sabe exatamente o que é aquilo, a fórmula é boa mas você não sabe o que é cada elemento da fórmula.
Se a CC considera apenas os blocos de código diferentes de acordo com o que vê escrito então acho uma medida menos importante.
Se considera a quantidade de decisões diferentes para decidir se tomará um caminho me parece mais importante.
Nem sei se isso está oficialmente correto, mas se estiver errado eu prefiro ficar com o "errado" porque ele faz mais sentido, é mais lógico, é que as pessoas podem pensar: "se tem um if
então há um branch e a CC sobe 1". Não poderia ser bem assim.
Em condições normais no mínimo 1 sobe mesmo, mas se o if
for true
ou false
já determinado pelo código sem depender da execução ele deveria subir 0.
Usando a mesma lógica, se você tiver uma condição mais complexa ali no if
ou até mesmo em expressão fora dele, a complexidade pode subir mais, e pode até mesmo se tornar exponencial. Só o fato de usar um operador de concatenação de comparações como o and
ou or
já faz um simples if
ter dois branches, então um if
com 30 and
s faz a CC ir para perto de 1 bilhão. Por que isso acontece? Por que no fundo cada subcondição é uma decisão separada, é como se fosse um if
novo, mas está tudo concatenado.
E aí um laço poderia variar de acordo com a quantidade de interações possíveis. Mas isso está mais para complexidade de algoritmo.
Isso pode não ser CC, mas é mais importante para seu código. Inclusive porque é muito estranho você ter 10 if
s cujo bloco de execução faz a mesma coisa e se você coloca tudo junto em um único if
a complexidade mudar.
Mais recentemente ouvi falar em Complexidade cognitiva. Não vi muito material tão confiável sobre isso (vi esse), mas tem softwares medindo esse tipo de coisa e considera tudo isso que eu falei. Me parece uma medida mais adequada, ainda que eu não esteja falando que é a mesma coisa.
É óbvio que uma medida que diz que a complexidade é de 1 bilhão ajuda pouco se ela não pode ser reduzida.
Conclusão
Não estou dizendo que a complexidade cognitiva é melhor porque me parece que ela tenha seus defeitos também. Todas são úteis para dar uma indicador, mas precisa entender a limitação de cada uma. Só ter a consciência que existem diversas medidas e elas devem ser observadas quando está codificando e não fazer tudo no estilo "bumba meu boi" já é um avanço que todo programador deve seguir.
Complexidade ciclomática ilustrada:
Pensa em como nesse caso iria ficar o grafo que o @Maniero exemplificou ali acima. :-)
-
4Até foi interessante colocar isso, porque há o mito que se você tiver vários
ifs
não aninhados, ou se colocar tudo isso com&&
, porque no fundo é uma coisa só, diminui a complexidade ciclomática, mas não diminui nada, a quantidade de branches é a mesma. Só fica mais legível. Mesmo mais legível, com um únicoif
(na verdade precisa de dois) a CC desse código continuaria sendo 13 (fiz de cabeça rapidinho, posso ter errado). OU seja, isso é curioso, mas não ilustra bem a CC.– Maniero ♦Commented 31/03/2017 às 12:23 -
Concordo! É que eu não achei uma imagem onde além dos
ifs
haviam tambémelseifs
,elses
ecases
(na verdade, acho que quem fizer um desenho desses vai ser internado depois, essas coisas afetam a sanidade), que aí sim faria com que a CC fosse alterada. De qualquer forma, é uma imagem, como você disse, curiosa, e divertida para o tópico. :-)– taqCommented 1/04/2017 às 13:27 -
Para complementar, 13 (se for, não conferi) já é um número meio estranho (pelo menos IMHO) ... aqui tem uns exemplos de métricas: stackoverflow.com/questions/1364946/…– taqCommented 1/04/2017 às 13:44
-
Como eu disse, posso ter feito alguma conta errada, mas porque 13 seria estranho?– Maniero ♦Commented 1/04/2017 às 13:48
-
Aqui tem tem artigo bem legal onde definem 10 como o valor bom (eu ainda acho menos que isso aceitável ...) e 15 como um "tomara que valha a pena se você sabe o que está fazendo": mccabe.com/pdf/mccabe-nist235r.pdf De qualquer forma, em termos de legibilidade, manutenção e eficiência de código eu prefiro números menores.– taqCommented 1/04/2017 às 13:59