Memahami Kompleksitas Siklomatik

Saya baru saja menemukan Kompleksitas Cyclomatik dan saya ingin mencoba memahaminya dengan lebih baik.

Apa sajakah contoh pengkodean praktis dari berbagai faktor yang masuk ke dalam penghitungan kompleksitas? Khususnya, untuk persamaan Wikipedia M = E − N + 2P, saya ingin lebih memahami arti dari masing-masing istilah berikut:

• E = jumlah tepi grafik
• N = jumlah node dari grafik
• P = jumlah komponen yang terhubung

Saya menduga bahwa E atau N mungkin merupakan jumlah poin keputusan (jika, jika tidak, untuk, foreach, dll) dalam satu blok kode, tetapi saya tidak yakin yang mana atau apa yang ditandakan oleh pihak lain. Saya juga menduga bahwa P merujuk ke pemanggilan fungsi dan instantiasi kelas, tetapi tidak ada definisi yang jelas yang bisa saya lihat. Jika seseorang dapat menjelaskan sedikit lebih banyak dengan masing-masing contoh kode yang jelas, itu akan membantu.

Sebagai tindak lanjut, apakah Kompleksitas Siklomatik berkorelasi langsung dengan jumlah tes unit yang diperlukan untuk cakupan jalur 100% ? Sebagai contoh, apakah metode dengan kompleksitas 4 mengindikasikan bahwa diperlukan 4 tes unit untuk mencakup metode itu?

Akhirnya, apakah ekspresi reguler memengaruhi Kompleksitas Siklomatik, dan jika ya, bagaimana?

Mengenai rumus: node mewakili status, tepi mewakili perubahan status. Di setiap program, pernyataan membawa perubahan dalam status program. Setiap pernyataan berurutan diwakili oleh edge, dan status program setelah (atau sebelum ...) eksekusi pernyataan adalah node.

Jika Anda memiliki pernyataan percabangan ( ifmisalnya) - maka Anda memiliki dua node keluar, karena negara dapat berubah dalam dua cara.

Cara lain untuk menghitung Nomor Kompleksitas Siklomatik (CCN) adalah menghitung berapa banyak "wilayah" dalam grafik eksekusi yang Anda miliki (di mana "wilayah independen" adalah lingkaran yang tidak mengandung lingkaran lain). Dalam hal ini CCN akan menjadi jumlah wilayah independen ditambah 1 (yang akan persis sama dengan yang diberikan rumus sebelumnya).

CCN digunakan untuk cakupan percabangan , atau cakupan jalur , yang sama. CCN sama dengan jumlah jalur percabangan yang berbeda secara teoritis dimungkinkan dalam aplikasi berulir tunggal (yang mungkin termasuk cabang seperti " if x < 2 and x > 5 then", tetapi itu harus ditangkap oleh kompiler yang baik sebagai kode yang tidak terjangkau). Anda harus memiliki setidaknya jumlah kasus uji yang berbeda (bisa lebih karena beberapa kasus pengujian mungkin mengulang jalur yang dicakup oleh yang sebelumnya, tetapi tidak kurang dengan asumsi setiap kasus mencakup satu jalur). Jika Anda tidak dapat menutupi jalur dengan kemungkinan kasus pengujian - Anda menemukan kode yang tidak dapat dijangkau (walaupun Anda harus benar-benar membuktikan kepada diri sendiri mengapa hal itu tidak dapat dijangkau, mungkin beberapa bersarang x < 2 and x > 5bersembunyi di suatu tempat).

Seperti untuk ekspresi reguler - tentu saja mereka mempengaruhi, seperti potongan kode lainnya. Namun, CCN dari konstruksi regex mungkin terlalu tinggi untuk dicakup dalam uji unit tunggal, dan Anda dapat mengasumsikan bahwa mesin regex telah diuji, dan mengabaikan potensi percabangan ekspresi untuk kebutuhan pengujian Anda (kecuali jika Anda menguji mesin regex, tentu saja).

Beberapa komentar tentang ini yang saya iseng tulis ...

Khususnya, untuk persamaan Wikipedia M = E - N + 2P

Persamaan itu sangat salah .

Untuk beberapa alasan, McCabe memang menggunakannya dalam makalah aslinya ("Ukuran Kompleksitas", Transaksi IEEE pada Rekayasa Perangkat Lunak, Vo. SE-2, No.4, Desember 1976), tetapi tanpa membenarkannya dan setelah benar-benar mengutip yang benar rumus di halaman pertama, yaitu

v (G) = e - v + p

(Di sini, elemen rumus telah dilabel ulang)

Secara khusus, McCabe merujuk buku C.Berge, Graphs dan Hypergraphs (disingkat menjadi G&HG). Langsung dari buku itu :

Definisi (halaman 27 di bawah G&HG):

Angka siklomatik v (G) dari grafik G (tidak terarah) (yang mungkin memiliki beberapa komponen yang terputus) didefinisikan sebagai:

v (G) = e - v + p

di mana e = jumlah tepi, v = jumlah simpul, p = jumlah komponen yang terhubung

Teorema (halaman 29 di atas G&HG) (tidak digunakan oleh McCabe):

Angka siklomatik v (G) dari grafik G sama dengan jumlah maksimum siklus independen

Sebuah siklus adalah urutan simpul mulai dan berakhir pada simpul yang sama, dengan masing-masing dua simpul berturut-turut di urutan berdekatan satu sama lain dalam grafik.

Secara intuitif, sebuah set siklus adalah independen jika tidak ada siklus dapat dibangun dari yang lain dengan melapiskan lapisan.

Teorema (halaman 29 tengah G&HG) (sebagaimana digunakan oleh McCabe):

Dalam grafik G yang sangat terhubung, angka siklomatik sama dengan jumlah maksimum dari sirkuit bebas linear.

Sebuah sirkuit adalah siklus tanpa pengulangan simpul dan tepi diperbolehkan.

Grafik terarah dikatakan sangat terhubung jika setiap titik dapat dicapai dari setiap titik lainnya dengan melewati tepi sesuai arah yang ditentukan.

Perhatikan bahwa di sini kami beralih dari grafik tidak terarah ke grafik yang sangat terhubung (yang diarahkan ... Berge tidak membuat ini sepenuhnya jelas)

McCabe sekarang menerapkan teorema di atas untuk memperoleh cara sederhana untuk menghitung "Nomor Kompleksitas McCabe" (CCN) sebagai berikut:

Diberikan grafik terarah yang mewakili "lompat topologi" dari suatu prosedur (grafik aliran instruksi), dengan titik yang ditunjuk mewakili titik masuk yang unik dan titik yang ditunjuk mewakili titik keluar yang unik (titik titik keluar mungkin perlu "dibangun" dengan menambahkannya jika ada beberapa pengembalian), buat grafik yang sangat terhubung dengan menambahkan tepi terarah dari titik keluar titik ke titik masuk titik, sehingga membuat titik masuk titik terjangkau dari titik lain.

McCabe sekarang berpendapat (agak membingungkan saya bisa mengatakan) bahwa angka siklomatik dari grafik aliran instruksi yang dimodifikasi "sesuai dengan gagasan intuitif kami tentang 'jumlah minimum lintasan'", dan karenanya kami akan menggunakan angka itu sebagai ukuran kompleksitas.

Keren, jadi:

Jumlah kompleksitas siklomatik dari grafik aliran instruksi yang dimodifikasi dapat ditentukan dengan menghitung sirkuit "terkecil" dalam grafik yang tidak diarahkan. Ini tidak terlalu sulit dilakukan oleh manusia atau mesin, tetapi menerapkan teorema di atas memberi kita cara yang lebih mudah untuk menentukannya:

v (G) = e - v + p

jika seseorang mengabaikan directionality of the edge.

Dalam semua kasus, kami hanya mempertimbangkan satu prosedur tunggal, jadi hanya ada satu komponen yang terhubung di seluruh grafik, dan karenanya:

v (G) = e - v + 1.

Dalam hal seseorang mempertimbangkan grafik asli tanpa menambahkan tepi "keluar-ke-entri" , ia memperoleh:

ṽ (G) = ẽ - v + 2

sebagai ẽ = e - 1

Mari kita ilustrasikan dengan menggunakan contoh McCabe dari makalahnya:

Di sini kita memiliki:

• e = 10
• v = 6
• p = 1 (satu komponen)
• v (G) = 5 (kami jelas menghitung 5 siklus)

Rumus untuk nomor siklomatik mengatakan:

v (G) = e - v + p

yang menghasilkan 5 = 10 - 6 +1 dan benar!

"Nomor kompleksitas siklomatik McCabe" seperti yang diberikan dalam makalahnya adalah

5 = 9 - 6 + 2 (tidak ada penjelasan lebih lanjut diberikan dalam makalah tentang bagaimana)

yang kebetulan benar (menghasilkan v (G)) tetapi karena alasan yang salah, yaitu kita menggunakan:

ṽ (G) = ẽ - v + 2

dan karenanya ṽ (G) = v (G) ... Fiuh!

Tetapi apakah ukuran ini bagus?

Dalam dua kata: Tidak terlalu

• Tidak sepenuhnya jelas bagaimana menetapkan "grafik aliran instruksi" dari suatu prosedur, terutama jika penanganan pengecualian dan rekursi masuk dalam gambar. Perhatikan bahwa McCabe menerapkan idenya ke kode yang ditulis dalam FORTRAN 66 , sebuah bahasa tanpa rekursi, tanpa pengecualian dan struktur eksekusi langsung.
• Fakta bahwa prosedur dengan keputusan dan prosedur dengan loop menghasilkan CCN yang sama bukanlah pertanda baik.

• Yang kurang baik adalah kenyataan bahwa forloop dan whileloop ditangani dengan cara yang sama (perhatikan bahwa dalam C, seseorang dapat menyalahgunakan foruntuk mengekspresikan a whiledengan cara lain; di sini saya berbicara tentang for (int i=0;i<const_val;i++)loop ketat ). Kita tahu dari ilmu komputer teoretis bahwa dua konstruksi ini menghasilkan kekuatan komputasi yang sama sekali berbeda: fungsi primitif-rekursif jika Anda hanya dilengkapi dengan for, fungsi parsial μ-rekursif jika Anda dilengkapi while.
• Eksperimen yang dilakukan para ahli menilai kompleksitas kode menunjukkan bahwa CCN tidak menangkap gagasan "kompleksitas kode" serta langkah-langkah lain, khususnya ilmu perangkat lunak Halstead dan ukuran fungsi kognitif Shao and Wangs (yang terakhir tampaknya adalah pemenang), lihat Penerapan tiga metrik kompleksitas kognitif, Konferensi Internasional 2012 tentang Kemajuan dalam TIK untuk Daerah Berkembang, 12-15 Desember 2012
• Verifikasi empiris menunjukkan bahwa (setidaknya untuk kode matang), CCN sangat berkorelasi linier dengan LOC (baris kode), yaitu CCN secara alami meningkat dengan panjang prosedur dan Anda mungkin juga menggunakan jumlah LOC untuk mengekspresikan kompleksitas. Ukuran yang lebih baik daripada CCN absolut mungkin CCN / LOC. Lihat khususnya: Metrik kompleksitas siklikat ditinjau kembali - DSpace @ MIT dan Peran empirisme dalam meningkatkan keandalan perangkat lunak masa depan

Sebagai tindak lanjut, apakah Kompleksitas Siklomatik berkorelasi langsung dengan jumlah tes unit yang diperlukan untuk cakupan jalur 100%?

Ya, pada dasarnya. Ini juga merupakan ide yang baik untuk menggunakan kompleksitas siklomatik sebagai indikator kapan harus melakukan refactor. Dalam pengalaman saya, testability dan reusability sangat meningkat untuk CC yang lebih rendah (walaupun Anda harus praktis - jangan over-refactor, dan beberapa metode akan memiliki CC yang tinggi karena sifatnya - tidak selalu masuk akal untuk mencoba dan memaksanya) menurunkan).

Akhirnya, apakah ekspresi reguler memengaruhi Kompleksitas Siklomatik, dan jika ya, bagaimana?

Ya, jika Anda ingin tepat, meskipun sebagian besar alat analisis kode tampaknya tidak mempertimbangkannya dengan cara itu. Ekspresi reguler hanyalah mesin keadaan terbatas, jadi saya menduga CC mereka dapat dihitung dari grafik FSM, tetapi itu akan menjadi angka yang cukup besar.