Cyclomatic Complexity (kompleksitas)

Question

Saya memiliki program untuk menemukan jarak / jalur terpendek dan saya mendapat jawaban yang benar tetapi saya mendapatkan masalah yaitu, "Fungsi 'shortestPath' memiliki kompleksitas 9. Maksimum yang diizinkan adalah 6." Inilah algoritmanya:

const graph = {
  start: { A: 5, D: 8 },
  A: { B: 9, C: 3 },
  D: { C: 4, E: 6 },
  C: { B: 5, E: 2 },
  B: { end: 7 },
  E: { end: 4 },
  end: {}
};

function shortestCostNode(costs, processed) {
  return Object.keys(costs).reduce((lowest, node) => {
    if (lowest === null || costs[node] < costs[lowest]) {
      if (!processed.includes(node)) {
        lowest = node;
      }
    }
    
    return lowest;
  }, null);
}

// this function returns the minimum cost and path to reach end
function shortestPath(graph) {
  // track lowest cost to reach each node
  const costs = Object.assign({ end: Infinity }, graph.start);
  
  const parents = { end: null };
  
  for (let child in graph.start) {
    parents[child] = 'start';
  }
  
  const processed = [];
  let node = shortestCostNode(costs, processed);
  
  while (node) {
    let cost = costs[node];
    let children = graph[node];
    
    for (let n in children) {
      if (children.hasOwnProperty(n)) {
        let newCost = cost + children[n];
        
        if (!costs[n] || costs[n] > newCost) {
          costs[n] = newCost;
          parents[n] = node;
        }
      }
    }
    
    processed.push(node);
    node = shortestCostNode(costs, processed);
  }

  let optimalPath = ["end"];
  let parent = parents.end;
  
  while (parent) {
    optimalPath.push(parent);
    parent = parents[parent];
  }
  
  optimalPath.reverse();

  const result = {
    distance: costs.end,
    path: optimalPath
  };
  return result;
}

Bagaimana cara mengurangi kompleksitas Fungsi shortestPath?

Answer 1

Kompleksitas siklomatik

adalah ukuran jumlah jalur yang mungkin melalui beberapa kode. Misalnya ifpernyataan dengan satu klausa misalnya if (foo) {}memiliki dua jalur, Satu jika foo benar dan satu jika salah. Setiap titik di mana kode dapat bercabang, cabang dihitung sebagai bagian dari kompleksitas siklomatik.

Sayangnya bagaimana kompleksitas dijumlahkan berbeda sehingga tanpa mengetahui bagaimana metrik dihitung, tidak ada cara mudah untuk memberikan jawaban. Hal terbaik yang dapat Anda lakukan adalah mengurangi jumlah kemungkinan cabang dalam kode.

Memperbaiki kode

Melihat kode Anda dan ada banyak ruang untuk mengurangi jumlah cabang.

Fungsi shortestCostNodeini tidak diperlukan karena link terpendek dalam sebuah node tidak berpengaruh pada hasil akhir. Tautan terpendek mungkin akan membawa Anda ke jalur terpanjang. Mencari tautan terpendek tidak ada perbaikan dalam memilih node secara berurutan.

shortestCostNodeadalah sumber utama kerumitan dalam solusi Anda, yang secara efektif mengacak pencarian Anda. Karena itu, Anda harus melacak jalur mana yang telah Anda lalui sehingga Anda tidak mengulangi jalur yang sama, ini menambah banyak bagasi.

Jika Anda secara sistematis mencari semua jalur yang mungkin secara berurutan (melacak di mana Anda belum pernah pergi), Anda menghilangkan kebutuhan untuk melacak di mana Anda pernah berada dan dengan demikian dapat menghapus banyak kode.

Gunakan tumpukan untuk mencari pohon

Karena pencarian untuk jalur terpendek melibatkan perjalanan di sepanjang jalan dan kemudian mundur ke cabang terdekat yang tidak dilintasi, tumpukan adalah cara terbaik untuk melacak kemajuan Anda.

Anda mulai di sebuah node, mendorong semua jalur dan biaya sejauh ini ke tumpukan, lalu meletuskan satu jalur dan bergerak di sepanjang jalur tersebut ke node berikutnya dengan menambahkan biaya seperti yang Anda lakukan. Kemudian lakukan hal yang sama untuk node berikutnya.

Ketika Anda mencapai titik akhir Anda kemudian memeriksa jarak dan jika itu adalah yang terpendek sejauh ini Anda menyimpan jarak itu dan jalur yang ditempuh. Kemudian pop langkah jalur berikutnya dari tumpukan sampai semua jalur telah diperiksa.

Tumpukan rekursif

Cara termudah (tetapi bukan yang tercepat) untuk mengimplementasikan tumpukan adalah melalui rekursi.

Jadi Anda berakhir dengan fungsi seperti

function shortestPath(graph) {
    const result = {distance: Infinity}, endName = "end";
    function followPath(node, totalDist = 0, path = ["start"]) {
        for (const [name, length] of Object.entries(node)) {
            const distance = totalDist + length;
            if (distance < result.distance) {
                if (name === endName) {  
                    Object.assign(result, {distance, path: [...path, endName]}); 
                } else {
                    path.push(name);
                    followPath(graph[name], distance, path);
                    path.pop();
                }
            }
        }
    }
    followPath(graph.start);
    return result;
}

Fungsi tersebut memiliki kompleksitas Cyclomatic sekitar 5.

Perhatikan bahwa fungsi hanya mengikuti jalur sementara jarak yang ditempuh kurang dari jalur terpendek yang sudah ditemukan. Ini berarti Anda mungkin tidak perlu memeriksa semua jalur sampai akhir.

Ada juga banyak ruang untuk perbaikan (dalam hal kompleksitas dan kinerja), tetapi karena Anda belum banyak mendefinisikan tentang struktur grafik yang mungkin, tidak ada gunanya melangkah lebih jauh.

Answer 2

const vs. let

Pertama, saya ingin memuji penggunaan constdi beberapa tempat. Namun ada tempat di mana constbisa digunakan sebagai pengganti let- misalnya untuk optimalPath, karena tidak pernah ditugaskan kembali. Disarankan untuk menggunakan default constdan kemudian beralih ke letsaat penugasan ulang dianggap perlu. Ini membantu menghindari penugasan ulang yang tidak disengaja dan bug lainnya .

Menambah optimalPath

Alih-alih memanggil push()untuk menambahkan item ke optimalPathdan kemudian memanggil reverse, unshift()metode ini dapat digunakan untuk menambahkan item ke awal larik, yang menghilangkan kebutuhan untuk membalik larik.

Iterasi masuk shortestCostnode()

Perhatikan dokumentasi MDN untuk Array.prototype.reduce()- untuk parameterinitialValue

initialValue Optional
Nilai yang akan digunakan sebagai argumen pertama untuk panggilan pertama daricallback. Jika tidakinitialValuediberikan, elemen pertama dalam larik akan digunakan sebagai nilai awalaccumulatordan dilewati sebagaicurrentValue. Memanggil reduce () pada array kosong tanpa sebuahinitialValuekemauan akan menampilkan fileTypeError.

Ini berarti bahwa alih-alih meneruskan nullnilai awal, nilai tersebut dapat dihilangkan untuk menggunakan nilai pertama sebagai nilai awal lowestdan akan melewati iterasi pertama tersebut. Hal ini kemudian akan menghilangkan kebutuhan untuk memeriksa lowest === nulldalam ifkondisi.

Memoisasi

Pengoptimalan yang mungkin dilakukan adalah dengan mengingat hasil - misalnya jika shortestCostNode()pernah dipanggil dengan argumen duplikat, simpan nilai hasil yang dihitung sehingga dapat dicari pada panggilan berikutnya dan dikembalikan tanpa perlu menghitung ulang nilainya.

Iterasi item anak-anak

Untuk loop di dalam whileloop

for (let n in children) {

      if (children.hasOwnProperty(n)) {

pertimbangkan untuk menggunakan for...ofloop yang digabungkan denganObject.entries(children)

Maka tidak perlu memeriksa apakah properti itu ada children(bukan yang lebih tinggi dalam rantai prototipe)

for (const [n, child] of Object.entries(children)) {

Itu menggunakan constalih-alih `biarkan karena nilai tidak perlu ditetapkan kembali dalam loop.

Nama yang lebih tepat nadalah key:

for (const [key, child] of Object.entries(children)) {