Evita le istruzioni in cicli Nested FOR

2

Per favore perdonami se questa è una domanda doppia. Ho due loop nidificati che eseguiranno l'iterazione per circa mn volte (la complessità è di circa 3k).

All'interno di questi cicli for, ho 3 Se le condizioni si basano su ciò che faccio certe operazioni. Sto provando a vedere se ci sono dei modi per evitare queste condizioni se le condizioni all'interno del ciclo for saranno eseguite per mn volte.

Di seguito è riportato lo scheletro dell'attuazione esistente:

var conditionA = <set conditions for A>
var conditionB = <set conditions for B>
var conditionC = <set conditions for C>

foreach (var x in X)
{
  foreach (var y in Y)
  {
    if (conditionA)
    {
      //computeA ..makes use of x and y
    }
    if (conditionB)
    {
      //computeB..makes use of x and y
    }
    if (conditionC)
    {
      //computeC..makes use of x and y
    }
  } //end of inner foreach
} 

Come puoi vedere che tutte e 3 le condizioni sono determinate prima di foreach , c'è un modo in cui posso eliminare le istruzioni IF ridondanti ad ogni iterazione?

    
posta learntogrow-growtolearn 22.03.2018 - 07:45
fonte

2 risposte

8

Un modo per evitare quei if s all'interno dei loop è di metterli all'esterno, decidendo quali funzioni chiamare in anticipo:

//set the values of conditionA, conditionB and conditionC;

functionA = conditionA ? computeA : noOp
functionB = conditionB ? computeB : noOp
functionC = conditionC ? computeC : noOp

foreach (var x in X)
{
    foreach (var y in Y)
    {
        functionA(x,y)
        functionB(x,y)
        functionC(x,y)
    }
}

Naturalmente, non c'è garanzia che questo sarà più veloce, ma "soddisfa il brief".

In alternativa, se desideri chiamare le funzioni solo se necessario, crea un insieme di funzioni da chiamare in anticipo e ciclicale ogni volta:

//set the values of conditionA, conditionB and conditionC;

Collection functions;
if (conditionA) functions += computeA
if (conditionB) functions += computeB
if (conditionC) functions += computeC

foreach (var x in X)
{
    foreach (var y in Y)
    {
        foreach (var f in functions)
        {
            f(x,y)
        }
    }
}

Questo approccio rischia di essere più lento anche se si aggiunge la creazione di un iteratore per le funzioni nm volte al processo. Ovviamente, stai evitando di effettuare chiamate di funzioni non necessarie ed evitando controlli superflui. Quindi in alcune situazioni, potrebbe anche essere più veloce.

    
risposta data 22.03.2018 - 08:29
fonte
3

Ci sono molti modi. Ecco un ordinato:

if (conditionA)
{
    foreach (var x in X)
    {
        foreach (var y in Y)
        {
            //computeA ..makes use of x and y
        }
    }
}

if (conditionB)
{
    foreach (var x in X)
    {
        foreach (var y in Y)
        {
            //computeB ..makes use of x and y
        }
    }
}

if (conditionC)
{
    foreach (var x in X)
    {
        foreach (var y in Y)
        {
            //computeC ..makes use of x and y
        }
    }
}

Questo presuppone che non ci siano dipendenze, effetti collaterali o altri motivi per preoccuparsi dell'ordine di esecuzione dei calcoli o delle condizioni.

Se stai pensando che sia inefficiente ti faccio notare che il tuo originale è O (n 2 ) mentre questo è O (3n 2 ) che è il stessa complessità sotto Big O. Non lasciare che pensieri di efficienza ti intrappolino in un codice difficile da leggere.

L'ho promesso in ordine così eccolo qui:

if (conditionA)
{
    A a = computeA(X, Y);
}
if (conditionB)
{
    B b = computeB(X, Y);
}
if (conditionC)
{
    C c = computeC(X, Y);
}

La cosa interessante di questo è che rende davvero ovvio un problema di inizializzazione.

    
risposta data 22.03.2018 - 08:17
fonte

Leggi altre domande sui tag