Apakah kompleksitas NPath lebih dari enam belas octillion realistis? Atau sudahkah saya merusak alatnya?

13

Saya baru saja mengukur sebagian besar kode PHP (1153 baris) menggunakan PHPMD ( http://phpmd.org/ ) dan ia memberi tahu saya bahwa kode tersebut memiliki kompleksitas NPath 16244818757303403077832757824.

Itu terlihat seperti angka yang sangat besar bagi saya, menunjukkan bahwa mungkin PHPMD telah rusak dalam beberapa cara. Apakah mungkin sepotong kode yang ditulis oleh manusia memiliki kompleksitas NPath yang begitu tinggi? Kompleksitas siklomatik adalah 351.

Dua kemungkinan detail penting -

  1. Ini adalah kode prosedural, dicampur dengan HTML, dan PHPMD hanya akan mengukur kode berorientasi objek. Untuk menyiasatinya, saya membungkus seluruh file dalam satu kelas dengan satu fungsi - ini mewakili cara penggunaannya.

  2. File ini terdiri dari serangkaian pernyataan switch bersarang, dan di dalamnya ada banyak pernyataan if..else - jadi tentu saja cukup rumit.

Edit

Saya ingin mengklarifikasi bahwa saya tidak mempertanyakan apakah PHPMD berbohong kepada saya. Saya tahu bahwa kode ini berantakan, saya hanya ingin tahu apakah mungkin kode apa pun menjadi sangat buruk. Sepertinya jawabannya adalah ya, itu sangat mungkin.

Jez
sumber
2
Saya tidak tahu apakah Anda merusak alat, tetapi # 2 menunjukkan bahwa kode itu mungkin bisa sedikit refactored.
LindaJeanne
1
@ LindaJeanne saya setuju. Saya hanya ingin tahu persis berapa banyak kekacauan yang terjadi.
Jez
2
WordPress ' WP_Query::get_posts()memiliki kompleksitas NPath sebesar 1,435 Quindecillion pada 2013. Ini bahkan lebih buruk saat ini ...
fuxia
@toscho itu informasi favorit saya yang baru. Terima kasih!
Jez

Jawaban:

24

Ini sepenuhnya mungkin. Mari kita asumsikan kita memiliki 35 konstruksi kasus sakelar yang masing-masing terdiri dari 10 kasus, yang akan memberi kita kompleksitas siklomatik kasar sebanyak 350 ketika setiap sakelar terjadi satu demi satu. Switch pertama memberi kita 10 jalur. Switch kedua memberi kita 10 jalur independen, sehingga kita memiliki 10 · 10 jalur sampai di sini. Dengan sakelar ketiga, kita mendapatkan 10 · 10 · 10 = 10³ jalur, dan seterusnya sampai kita mendapatkan total 10 35 jalur! Ini bahkan lebih tinggi daripada hasil Anda 1,6 · 10 28 jalur, yang mungkin karena faktor percabangan yang berbeda, dan karena pernyataan aliran kontrol bersarang yang mengurangi jumlah jalur melalui kode Anda.

Sebagai skenario terburuk untuk diberikan kompleksitas cyclomatic c, kita bisa memiliki maksimal 2 c jalur asiklik melalui kode (di sini: 2 351 = 4,6 · 10 105 ).

Penilaian alat ini jelas: kode yang Anda hadapi adalah kekacauan yang rumit, tidak dapat diuji, dan tidak dapat dipelihara. Pertimbangkan untuk memecahnya menjadi lebih kecil, fungsi-fungsi independen, dan mengabstraksikan pengulangan. Misalnya Anda dapat memisahkan generasi HTML dari logika utama skrip PHP Anda.

amon
sumber
14
Terima kasih untuk analisisnya. Saya merasa perlu untuk menunjukkan bahwa itu bukan kode saya ... tetapi, seperti yang sering terjadi, itu tampaknya masalah saya bagi saya.
Jez
1
@ Jo, jika itu adalah penghiburan, Anda tidak berada dalam posisi yang unik.
Daniel Hollinrake
5

Menurut uraian ini , kompleksitas NPath adalah eksponensial dalam kompleksitas siklomatik.

Mengambil pernyataan sederhana jika, jika Anda memiliki dua pernyataan ini, itu pada dasarnya 4 rute melalui kode Anda yang sesuai dengan empat kemungkinan kombinasi benar / salah untuk dua kondisi pernyataan. Tambahkan pernyataan if lainnya dan Anda mendapatkan 8.

Dengan kata lain, jika semua kompleksitas siklomatik dan NPath Anda berasal dari daftar panjang pernyataan if, maka penyamaan Anda akan menjadi NPath = 2^cyclomatic. Membandingkannya dengan angka Anda, 2 ^ 351 = 4,6 * 10 ^ 105, jauh, jauh lebih tinggi daripada kompleksitas NPath yang Anda laporkan.

Saya tidak tahu berapa banyak PHPMD lakukan untuk menghindari penghitungan jalur yang sebenarnya tidak mungkin (misalnya dua kondisional yang sama-sama eksklusif mengevaluasi ke true). Mungkin analisis manual akan mengungkapkan bahwa banyak jalur sebenarnya tidak mungkin, sehingga kode ditulis dengan cara yang mengembang metrik NPath. Untuk melanjutkan di atas, jika Anda memiliki daftar 351 jika pernyataan, tetapi dapat memverifikasi bahwa hanya satu yang benar-benar dimasukkan, Anda dapat mengubahnya menjadi sebuah rantai pernyataan if ... else, yang menjadikan kompleksitas NPath Anda turun dari 4,6 * 10 ^ 105 hingga 353.

Tetapi dengan hanya informasi dalam pertanyaan Anda, tidak tahu berapa banyak penyederhanaan semacam itu dapat dilakukan atau sudah dilakukan oleh PHPMD, jumlahnya tampak realistis.

Ben Aaronson
sumber