Quanto spesso ti preoccupi di quanti casi devono essere elaborati?

StackOverflow https://stackoverflow.com/questions/172831

Domanda

Se si dispone di quanto segue: 

$var = 3; // we'll say it's set to 3 for this example
if ($var == 4) {
    // do something
} else if ($var == 5) {
    // do something
} else if ($var == 2) {
    // do something
} else if ($var == 3) {
    // do something
} else {
    // do something
}

Se si dice che l'80% delle volte $ var è 3, ti preoccupi del fatto che siano passati 4 casi prima di trovare il caso vero?

Sto pensando a un piccolo sito non è un grosso problema, ma che dire di quando se la dichiarazione verrà eseguita 1000 volte di secondo al secondo?

Sto lavorando in PHP, ma penso che la lingua non abbia importanza.

È stato utile?

Soluzione

Ecco come l'abbiamo fatto quando scrivevo software per sistemi radar. (La velocità conta nel radar. È uno dei pochi posti in cui "tempo reale" significa in realtà "reale" invece di "veloce".)

[Passerò alla sintassi di Python, è più facile per me e sono sicuro che puoi interpretarlo.] 

if var <= 3:
    if var == 2:
        # do something
    elif var == 3:
        # do something
    else: 
        raise Exception
else:
    if var == 4:
        # do something
    elif var == 5:
        # do something
    else:
        raise Exception

Le tue dichiarazioni if ??formano un albero anziché un elenco semplice. Mentre aggiungi le condizioni a questo elenco, ti muovi nel centro dell'albero. La sequenza piatta dei confronti n richiede, in media, n / 2 passaggi. L'albero conduce a una sequenza di confronti che prende i confronti log ( n ).

Altri suggerimenti

Beh, credo che quasi sempre , la leggibilità di, diciamo, avere valori ordinati numericamente avrebbe la precedenza su tutti i piccoli benefici che potresti ottenere riducendo il numero di istruzioni di confronto.

Detto questo, come per tutte le ottimizzazioni:

  1. Fallo funzionare
  2. Misuralo
  3. Se è abbastanza veloce, lasciarlo da solo
  4. Se è troppo lento, POI ottimizzarlo

Oh, e probabilmente userei un interruttore / caso fin dall'inizio! ; -)

Un caso classico di ciò che accadeva (con letteralmente 5 opzioni come nel tuo post) era in ffmpeg, nella funzione decode_cabac_residual. Questo è stato piuttosto importante, poiché la profilazione (molto importante - non ottimizzare prima della profilazione!) Ha dimostrato che contava un aumento del 10-15% del tempo impiegato nella decodifica video H.264. L'istruzione if controllava una serie di istruzioni calcolate in modo diverso per i vari tipi di residui da decodificare - e, sfortunatamente, si perdeva troppa velocità a causa delle dimensioni del codice se la funzione veniva duplicata 5 volte per ciascuno dei 5 tipi di residuo. Quindi, invece, è stata utilizzata una catena if.

La profilazione è stata eseguita su molti flussi di test comuni per ordinarli in termini di probabilità; la parte superiore era la più comune, la parte inferiore la meno. Ciò ha dato un piccolo guadagno di velocità.

Ora, in PHP, sospetto che ci sia molto meno del guadagno di velocità di stile di basso livello che otterresti in C, come nell'esempio sopra.

L'uso di un'istruzione switch / case è sicuramente la strada da percorrere qui.

Questo dà al compilatore (interprete) la possibilità di utilizzare una tabella di salto per arrivare al ramo giusto senza dover fare confronti N. Pensa a creare una matrice di indirizzi indicizzata come 0, 1, 2, .. quindi può semplicemente cercare quella corretta nella matrice in una sola operazione.

Inoltre, poiché l'overhead è meno sintetico in un'istruzione case, è anche più facile da leggere.

Aggiornamento: se i confronti sono adatti per un'istruzione switch, questa è un'area in cui le ottimizzazioni guidate dal profilo possono aiutare. Eseguendo una build PGO con carichi di test realistici, il sistema può generare informazioni sull'utilizzo delle filiali e quindi utilizzarle per ottimizzare il percorso intrapreso.

Invece di rispondere alla domanda PHP, risponderò un po 'più in generale. Non si applica direttamente a PHP in quanto passerà attraverso una sorta di interpretazione.

Molti compilatori possono convertire in e da blocchi if-elif-elif -... per cambiare i blocchi se necessario e i test nelle parti elif sono abbastanza semplici (e il resto della semantica sembra essere compatibile). Per 3-4 test non c'è necessariamente nulla da guadagnare usando una tabella di salto.

Il motivo è che il predittore di rami nella CPU è davvero bravo a prevedere cosa succede. In effetti, l'unica cosa che succede è una pressione leggermente maggiore sul recupero delle istruzioni, ma difficilmente sarà sconvolgente per il mondo.

Nel tuo esempio, tuttavia, la maggior parte dei compilatori riconoscerebbe che $ var è una costante 3 e quindi sostituisce $ var con 3 nei blocchi if..elif ... Questo a sua volta rende le espressioni costanti in modo che siano piegate su true o false. Tutti i falsi rami vengono eliminati dall'eliminatore del codice morto e viene eliminato anche il test del vero. Ciò che rimane è il caso in cui $ var == 3. Non puoi fare affidamento sul fatto che PHP sia così intelligente. In generale non è possibile eseguire la propagazione di $ var ma potrebbe essere possibile da alcuni siti di chiamata.

Potresti provare ad avere una matrice di blocchi di codice, in cui chiami. Quindi tutti i blocchi di codice hanno lo stesso sovraccarico.

Perl 6: 

our @code_blocks = (
  { 'Code Block 0' },
  { 'Code Block 1' },
  { 'Code Block 2' },
  { 'Code Block 3' },
  { 'Code Block 4' },
  { 'Code Block 5' },
);

if( 0 <= $var < @code_blocks.length ){
  @code_blocks[$var]->();
}

Se il codice deve eseguire test aggiuntivi, verrà sicuramente eseguito più lentamente. Se le prestazioni sono fondamentali in questa sezione di codice, dovresti mettere prima i casi più comuni.

Normalmente concordo con la misura "quot, quindi ottimizzazione " metodo quando non sei sicuro che le prestazioni saranno abbastanza veloci, ma se il codice deve semplicemente essere eseguito il più velocemente possibile E la correzione è facile come riordinare i test, quindi renderei il codice veloce ora e farei un po 'di misurazione dopo che vai a vivere per assicurarti che il tuo presupposto (ad es. che 3 accadrà l'80% delle volte) sia effettivamente corretto.

Con il codice in cui si tratta puramente di un'analisi dell'uguaglianza, lo sposterei in un interruttore / caso, in quanto fornisce prestazioni migliori. 

$var = 3; // we'll say it's set to 3 for this example
switch($var)
 {
   case 4:
      //do something
      break;
   case 5:
      //do something
      break;
   case:
      //do something when none of the provided cases match (same as using an else{ after the elseif{
 }

ora, se stai facendo confronti più complicati, li anniderei nello switch o userei semplicemente elseif.

Nei linguaggi orientati agli oggetti, se un'opzione fornisce if massicci, significa che dovresti semplicemente spostare il comportamento (ad es. i blocchi // do qualcosa ) sull'oggetto contenente il valore.

/ p>

Solo tu puoi dire se la differenza di prestazioni nell'ottimizzare l'ordine o nel riordinarlo in effetti in un albero binario, farebbe una differenza significativa. Ma ho il sospetto che dovrai avere milioni di volte al secondo, non migliaia, per preoccuparti di pensarci anche in PHP (e ancora di più in alcune altre lingue).

Time it. Guarda quante volte al secondo puoi eseguire la precedente istruzione if / else if / else senza che sia stata intrapresa alcuna azione e $ var non sia una delle scelte.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top