Cyclomatic Complexity (phức tạp)

Question

Tôi có một chương trình để tìm khoảng cách / đường đi ngắn nhất và tôi đã nhận được câu trả lời đúng nhưng tôi gặp sự cố tức là "Hàm 'Đường ngắn nhất' có độ phức tạp là 9. Tối đa được phép là 6." Đây là thuật toán:

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

Làm thế nào để giảm độ phức tạp của Hàm shortestPath?

Answer 1

Phức tạp cyclomatic

là thước đo số lượng đường dẫn có thể có thông qua một số mã. Ví dụ, một ifcâu lệnh với một mệnh đề, ví dụ: if (foo) {}có hai đường dẫn, Một nếu foo là đúng và một nếu sai. Bất kỳ điểm nào mà mã có thể phân nhánh, các nhánh được tính là một phần của độ phức tạp chu kỳ.

Thật không may, độ phức tạp được tính toán khác nhau như thế nào nên nếu không biết cách tính số liệu này thì không có cách nào dễ dàng để đưa ra câu trả lời. Điều tốt nhất bạn có thể làm là giảm số lượng nhánh có thể có trong mã.

Cải thiện mã

Nhìn vào mã của bạn và có nhiều chỗ để giảm số lượng chi nhánh.

Hàm shortestCostNodekhông cần thiết vì liên kết ngắn nhất trong một nút không ảnh hưởng đến kết quả cuối cùng. Liên kết ngắn nhất cũng có thể đưa bạn đến con đường dài nhất. Tìm kiếm liên kết ngắn nhất không cải thiện được việc chọn các nút tuần tự.

shortestCostNodelà nguồn phức tạp chính trong giải pháp của bạn, nó ngẫu nhiên hóa tìm kiếm của bạn một cách hiệu quả. Bởi vì điều này, bạn phải theo dõi con đường bạn đã đi để bạn không lặp lại cùng một con đường, điều này làm tăng thêm rất nhiều hành lý.

Nếu bạn tìm kiếm một cách có hệ thống tất cả các con đường có thể có theo thứ tự (theo dõi nơi bạn chưa đến), bạn sẽ loại bỏ nhu cầu theo dõi nơi bạn đã đến và do đó có thể loại bỏ rất nhiều mã.

Sử dụng ngăn xếp để tìm kiếm cây

Vì việc tìm kiếm con đường ngắn nhất liên quan đến việc đi dọc theo các con đường và sau đó quay trở lại nhánh chưa được khám phá gần nhất, một ngăn xếp là cách tốt nhất để theo dõi tiến trình của bạn.

Bạn bắt đầu tại một nút, đẩy tất cả các đường dẫn và chi phí vào một ngăn xếp, sau đó bật một đường dẫn và di chuyển dọc theo đường dẫn đó đến nút tiếp theo, thêm chi phí như bạn làm. Sau đó, làm tương tự cho các nút tiếp theo.

Khi bạn đến một điểm cuối, bạn kiểm tra khoảng cách và nếu nó là ngắn nhất cho đến nay, bạn sẽ lưu khoảng cách đó và quãng đường đã đi. Sau đó bật bước đường dẫn tiếp theo từ ngăn xếp cho đến khi tất cả các đường dẫn đã được kiểm tra.

Một ngăn xếp đệ quy

Cách đơn giản nhất (nhưng không phải là nhanh nhất) để triển khai ngăn xếp là thông qua đệ quy.

Vì vậy, bạn kết thúc với một chức năng giống như

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

Hàm có độ phức tạp Cyclomatic khoảng 5.

Lưu ý rằng hàm chỉ đi theo các đường dẫn trong khi khoảng cách đã đi nhỏ hơn đường đi ngắn nhất đã tìm thấy. Điều này có nghĩa là bạn có thể không cần phải kiểm tra tất cả các đường dẫn đến cùng.

Cũng có rất nhiều chỗ để cải thiện (về độ phức tạp và hiệu suất), nhưng vì bạn chưa xác định nhiều về cấu trúc đồ thị có thể có, nên không có điểm nào để đi xa hơn.

Answer 2

const vs let

Trước tiên, tôi muốn hoan nghênh việc sử dụng constở một số nơi. Tuy nhiên, constcó những nơi có thể được sử dụng thay vì let- ví dụ: optimalPathvì nó không bao giờ được gán lại. Bạn nên mặc định sử dụng constvà sau đó chuyển sang sử dụng letkhi thấy cần thiết. Điều này giúp tránh tình cờ chuyển nhượng lại và các lỗi khác .

Thêm vào optimalPath

Thay vì gọi push()để thêm các mục vào optimalPathrồi gọi reverse, unshift()phương thức này có thể được sử dụng để thêm các mục vào đầu mảng, điều này giúp loại bỏ sự cần thiết phải đảo ngược mảng.

Lặp lại trong shortestCostnode()

Lưu ý tài liệu MDN cho Array.prototype.reduce()- cho tham sốinitialValue

InitialValue Optional
Một giá trị để sử dụng làm đối số đầu tiên cho lệnh gọi đầu tiên củacallback. Nếu khônginitialValuecung cấp, phần tử đầu tiên trong mảng sẽ được sử dụng làmaccumulatorgiá trịban đầuvà được bỏ qua nhưcurrentValue. Gọi Reduce () trên một mảng trống không có dấuinitialValuesẽ ném ra aTypeError.

Điều này có nghĩa là thay vì chuyển nullcho giá trị ban đầu, giá trị có thể bị bỏ qua để sử dụng giá trị đầu tiên làm giá trị ban đầu lowestvà nó sẽ bỏ qua lần lặp đầu tiên đó. Điều này sau đó sẽ loại bỏ sự cần thiết phải kiểm tra lowest === nulltrong ifđiều kiện đó .

Ghi nhớ

Một tối ưu hóa khả thi là ghi nhớ kết quả - ví dụ: nếu shortestCostNode()từng được gọi với các đối số trùng lặp thì hãy lưu trữ giá trị trả về đã tính toán để có thể tra cứu trong các lần gọi tiếp theo và trả về mà không cần tính toán lại giá trị.

Lặp lại các mục con

Đối với vòng lặp trong whilevòng lặp

for (let n in children) {

      if (children.hasOwnProperty(n)) {

xem xét sử dụng một for...ofvòng lặp kết hợp vớiObject.entries(children)

Sau đó, không cần phải kiểm tra xem thuộc tính có tồn tại hay không children(thay vì lên cao hơn trong chuỗi nguyên mẫu)

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

Điều đó sử dụng constthay vì `let vì các giá trị không cần phải được gán lại trong vòng lặp.

Tên thích hợp hơn nsẽ là key:

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