Cyclomatic Complexity (ความซับซ้อน)

Question

ฉันมีโปรแกรมสำหรับค้นหาระยะทาง / เส้นทางที่สั้นที่สุดและฉันได้รับคำตอบที่ถูกต้อง แต่ฉันได้รับปัญหาคือ "ฟังก์ชัน 'shortestPath' มีความซับซ้อน 9 สูงสุดที่อนุญาตคือ 6" นี่คืออัลกอริทึม:

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;
}

จะลดความซับซ้อนของ Function ได้shortestPathอย่างไร?

Answer 1

ความซับซ้อนของวงจร

คือการวัดจำนวนเส้นทางที่เป็นไปได้โดยละเอียดบางรหัส ตัวอย่างเช่นifคำสั่งที่มีหนึ่งประโยคเช่นif (foo) {}มีสองเส้นทางหนึ่งถ้า foo เป็นจริงและอีกหนึ่งคำสั่งถ้าเท็จ จุดใดก็ตามที่รหัสสามารถแตกกิ่งก้านสาขาจะถูกนับเป็นส่วนหนึ่งของความซับซ้อนของวัฏจักร

น่าเสียดายที่ความซับซ้อนในการสรุปแตกต่างกันดังนั้นการที่ไม่รู้ว่าเมตริกคำนวณอย่างไรจึงไม่มีวิธีง่ายๆในการให้คำตอบ สิ่งที่ดีที่สุดที่คุณสามารถทำได้คือลดจำนวนสาขาที่เป็นไปได้ในรหัส

การปรับปรุงโค้ด

ดูรหัสของคุณแล้วมีที่ว่างมากมายที่จะลดจำนวนสาขา

shortestCostNodeไม่จำเป็นต้องใช้ฟังก์ชันนี้เนื่องจากลิงก์ที่สั้นที่สุดในโหนดไม่มีผลต่อผลลัพธ์สุดท้าย ลิงก์ที่สั้นที่สุดอาจนำคุณไปสู่เส้นทางที่ยาวที่สุดได้ การค้นหาลิงก์ที่สั้นที่สุดจะไม่มีการปรับปรุงในการเลือกโหนดตามลำดับ

shortestCostNodeเป็นแหล่งสำคัญของความซับซ้อนในโซลูชันของคุณโดยจะสุ่มการค้นหาของคุณอย่างมีประสิทธิภาพ ด้วยเหตุนี้คุณจึงต้องติดตามว่าคุณเดินทางไปในเส้นทางใดเพื่อที่คุณจะได้ไม่ต้องวนซ้ำเส้นทางเดิมสิ่งนี้จะเพิ่มสัมภาระจำนวนมาก

หากคุณค้นหาเส้นทางที่เป็นไปได้ทั้งหมดอย่างเป็นระบบตามลำดับ (ติดตามตำแหน่งที่คุณไม่เคยไป) คุณไม่จำเป็นต้องติดตามว่าคุณอยู่ที่ไหนและสามารถลบรหัสจำนวนมากได้

ใช้สแต็กเพื่อค้นหาต้นไม้

เนื่องจากการค้นหาเส้นทางที่สั้นที่สุดเกี่ยวข้องกับการเดินทางไปตามเส้นทางแล้วย้อนกลับไปยังสาขาที่ไม่ได้รับการสำรวจที่ใกล้ที่สุดกองซ้อนจึงเป็นวิธีที่ดีที่สุดในการติดตามความคืบหน้าของคุณ

คุณเริ่มต้นที่โหนดผลักพา ธ ทั้งหมดและต้นทุนไปยังสแต็กจากนั้นป๊อปพา ธ หนึ่งเส้นทางและย้ายไปตามเส้นทางนั้นไปยังโหนดถัดไปโดยเพิ่มต้นทุนตามที่คุณทำ จากนั้นทำเช่นเดียวกันสำหรับโหนดถัดไป

เมื่อคุณไปถึงจุดสิ้นสุดคุณจะตรวจสอบระยะทางและถ้ามันสั้นที่สุดเท่าที่คุณจะบันทึกระยะทางนั้นและเส้นทางที่เดินทาง จากนั้นเปิดขั้นตอนเส้นทางถัดไปจากสแต็กจนกว่าจะตรวจสอบเส้นทางทั้งหมด

สแต็กแบบเรียกซ้ำ

วิธีที่ง่ายที่สุด (แต่ไม่ใช่วิธีที่เร็วที่สุด) ในการใช้งานสแต็กคือการเรียกซ้ำ

ดังนั้นคุณจะได้ฟังก์ชั่นบางอย่างเช่น

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;
}

ฟังก์ชันนี้มีความซับซ้อนของ Cyclomatic ประมาณ 5

โปรดทราบว่าฟังก์ชันจะติดตามเส้นทางในขณะที่ระยะทางที่เดินทางน้อยกว่าเส้นทางที่สั้นที่สุดที่พบแล้ว ซึ่งหมายความว่าคุณอาจไม่จำเป็นต้องตรวจสอบเส้นทางทั้งหมดจนถึงจุดสิ้นสุด

นอกจากนี้ยังมีช่องว่างมากมายสำหรับการปรับปรุง (ในแง่ของความซับซ้อนและประสิทธิภาพ) แต่เนื่องจากคุณไม่ได้กำหนดโครงสร้างกราฟที่เป็นไปได้มากนักจึงไม่มีประเด็นใดที่จะต้องดำเนินการต่อไป

Answer 2

const เทียบกับ let

ก่อนอื่นขอปรบมือให้กับการใช้งานconstในบางสถานที่ อย่างไรก็ตามมีสถานที่ที่constสามารถใช้แทนได้letเช่นoptimalPathเนื่องจากไม่มีการกำหนดใหม่ ขอแนะนำให้ใช้ค่าเริ่มต้นconstจากนั้นเปลี่ยนไปใช้letเมื่อจำเป็นต้องมอบหมายใหม่ นี้จะช่วยให้หลีกเลี่ยงอุบัติเหตุอีกครั้งที่ได้รับมอบหมายและข้อบกพร่องอื่น ๆ

กำลังเพิ่มไปที่ optimalPath

แทนที่จะเรียกpush()เพื่อเพิ่มรายการเข้าไปoptimalPathแล้วเรียกreverseใช้unshift()วิธีนี้สามารถใช้เพื่อเพิ่มรายการไปยังจุดเริ่มต้นของอาร์เรย์ซึ่งไม่จำเป็นต้องย้อนกลับอาร์เรย์

วนซ้ำใน shortestCostnode()

หมายเหตุเอกสาร MDN สำหรับArray.prototype.reduce()- สำหรับพารามิเตอร์initialValue

initialValue Optional
ค่าที่จะใช้เป็นอาร์กิวเมนต์แรกสำหรับการเรียกครั้งแรกของcallback. ถ้าไม่มีinitialValueจะถูกส่งให้องค์ประกอบแรกในอาร์เรย์จะถูกนำมาใช้เป็นครั้งแรกมูลค่าและข้ามเป็นaccumulator currentValueการเรียกลด () บนอาร์เรย์ว่างโดยไม่มีinitialValueจะโยนTypeError.

ซึ่งหมายความว่าแทนที่จะส่งผ่านnullสำหรับค่าเริ่มต้นอาจละเว้นค่าเพื่อใช้ค่าแรกเป็นค่าเริ่มต้นlowestและจะข้ามการทำซ้ำครั้งแรกนั้นไป จากนั้นจะไม่จำเป็นต้องตรวจสอบlowest === nullในifเงื่อนไขนั้น

การบันทึก

การเพิ่มประสิทธิภาพที่เป็นไปได้คือการบันทึกผลลัพธ์ - เช่นหากshortestCostNode()เคยถูกเรียกด้วยอาร์กิวเมนต์ที่ซ้ำกันให้เก็บค่าที่คำนวณกลับมาเพื่อให้สามารถค้นหาในการโทรที่ตามมาและส่งคืนได้โดยไม่จำเป็นต้องคำนวณค่าใหม่

ทำซ้ำรายการเด็ก

สำหรับลูปภายในwhileลูป

for (let n in children) {

      if (children.hasOwnProperty(n)) {

พิจารณาใช้การfor...ofวนซ้ำร่วมกับObject.entries(children)

จากนั้นไม่จำเป็นต้องตรวจสอบว่ามีคุณสมบัติอยู่หรือไม่children(แทนที่จะสูงขึ้นในห่วงโซ่ต้นแบบ)

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

ที่ใช้constแทน `let เนื่องจากค่าไม่จำเป็นต้องกำหนดใหม่ภายในลูป

ชื่อที่เหมาะสมกว่าnคือkey:

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