Complessità ciclomatica (complessità)

Question

Ho un programma per trovare la distanza / percorso più breve e ho ottenuto una risposta corretta ma ricevo un problema, ad esempio "La funzione 'shortestPath' ha una complessità di 9. Il massimo consentito è 6." Questo è l'algoritmo:

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

Come ridurre la complessità della funzione shortestPath?

Answer 1

Complessità ciclomatica

è una misura del numero di possibili percorsi attraverso un codice. Ad esempio, ifun'istruzione con una clausola, ad esempio, if (foo) {}ha due percorsi, uno se foo è vero e uno se falso. In qualsiasi punto in cui il codice può diramarsi, i rami vengono contati come parte della complessità ciclomatica.

Purtroppo il modo in cui la complessità viene sommata differisce, quindi senza sapere come è stata calcolata la metrica non esiste un modo semplice per dare una risposta. Il meglio che puoi fare è ridurre il numero di possibili rami nel codice.

Migliorare il codice

Guardando il tuo codice c'è molto spazio per ridurre il numero di filiali.

La funzione shortestCostNodenon è necessaria poiché il collegamento più breve in un nodo non ha alcuna influenza sul risultato finale. Il collegamento più breve potrebbe portarti al percorso più lungo. La ricerca del collegamento più breve non migliora la selezione sequenziale dei nodi.

shortestCostNodeè la principale fonte di complessità nella tua soluzione, randomizza efficacemente la tua ricerca. Per questo motivo devi tenere traccia del percorso che hai percorso in modo da non finire per ripetere lo stesso percorso, questo aggiunge molto bagaglio.

Se cerchi sistematicamente tutti i percorsi possibili in ordine (tenendo traccia di dove non sei stato) elimini la necessità di tracciare dove sei stato e puoi quindi rimuovere molto codice.

Usa una pila per cercare un albero

Poiché la ricerca del percorso più breve implica viaggiare lungo sentieri e poi tornare indietro al ramo non percorso più vicino, una pila è il modo migliore per tenere traccia dei tuoi progressi.

Si inizia da un nodo, si spinge tutti i percorsi e il costo fino a quel momento in una pila, quindi si apre un percorso e si sposta lungo quel percorso fino al nodo successivo aggiungendo il costo come si fa. Quindi fai lo stesso per il nodo successivo.

Quando si raggiunge un nodo finale si controlla la distanza e se è la più breve fino ad ora si salva quella distanza e il percorso percorso. Quindi apri il passaggio successivo del percorso dalla pila finché tutti i percorsi non sono stati controllati.

Uno stack ricorsivo

Il modo più semplice (ma non il più veloce) per implementare uno stack è tramite la ricorsione.

Così si finisce con una funzione qualcosa di simile

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

La funzione ha una complessità Ciclomatica di circa 5.

Si noti che la funzione segue solo i percorsi mentre la distanza percorsa è inferiore al percorso più breve trovato già trovato. Ciò significa che potrebbe non essere necessario controllare tutti i percorsi fino alla fine.

C'è anche molto spazio per miglioramenti (in termini di complessità e prestazioni), ma poiché non hai definito molto sulla struttura possibile dei grafici, non ha senso andare oltre.

Answer 2

const vs let

Per prima cosa vorrei applaudire l'uso di constin alcuni luoghi. Tuttavia, ci sono luoghi in cui constpotrebbe essere utilizzato al posto di let- ad esempio per optimalPath, poiché non viene mai riassegnato. Si consiglia di utilizzare per impostazione predefinita conste quindi passare a letquando si ritiene necessario il riassegnazione. Questo aiuta a evitare riassegnazioni accidentali e altri bug .

Aggiunta a optimalPath

Invece di chiamare push()per aggiungere elementi optimalPathe quindi chiamare reverse, il unshift()metodo può essere utilizzato per aggiungere elementi all'inizio della matrice, eliminando la necessità di invertire la matrice.

Iterando in shortestCostnode()

Notare la documentazione MDN per Array.prototype.reduce()- per parametroinitialValue

initialValue Optional
Un valore da utilizzare come primo argomento per la prima chiamata dicallback. Se noninitialValueviene fornitono, il primo elemento dell'array verrà utilizzato comeaccumulatorvaloreinizialeeverràignorato comecurrentValue. Chiamare reduce () su un array vuoto senza uninitialValuegenererà un fileTypeError.

Ciò significa che invece di passare nullper il valore iniziale, il valore potrebbe essere omesso per utilizzare il primo valore come valore iniziale di loweste salterebbe quella prima iterazione. Ciò eliminerebbe quindi la necessità di verificare lowest === nulltale ifcondizione.

Memoizzazione

Una possibile ottimizzazione consiste nel memorizzare i risultati - ad esempio, se shortestCostNode()mai viene chiamato con argomenti duplicati, memorizzare il valore di ritorno calcolato in modo che possa essere cercato nelle chiamate successive e restituito senza dover ricalcolare il valore.

Iterazione su articoli per bambini

Per il ciclo all'interno del whileciclo

for (let n in children) {

      if (children.hasOwnProperty(n)) {

considera l'utilizzo di un for...ofciclo combinato conObject.entries(children)

Quindi non è necessario verificare se la proprietà esiste in children(invece che più in alto nella catena del prototipo)

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

Questo usa constinvece di `let perché i valori non devono essere riassegnati all'interno del ciclo.

Un nome più appropriato per nsarebbe key:

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