Quale istruzione if richiede meno calcoli?

-3

Ho

if (!b && c || a && c)
  //do action a
else 
  //...

A causa di alcune relazioni interne tra a, b e c. !b && c || a && c si dimostra equivalente a (! a && b) || c .

Mi chiedo solo che (! a && b) || c sia più semplice di !b && c || a && c ? Puoi provarlo? Supponiamo che le possibilità che a, b, c siano True o False siano uguali.

I non chiedono quale stile è migliore . Sto chiedendo quale affermazione ha una complessità computazionale inferiore . Proprio come chiedere l'ordinamento rapido e il Bubble Sort, che ha una complessità computazionale inferiore. Non risponderai dipende, è correlato al compilatore e all'hardware perché alcuni hardware hanno istruzioni speciali per Bubble Sort. Spero di sentire nlog (n) e n ^ 2.

    
posta Gqqnbig 30.08.2013 - 09:51
fonte

4 risposte

8

un buon ottimizzatore farà la differenza qui moot

puoi pensare a come funziona il cortocircuito:

con if ((!b && c) || (a && c)) ottieni

if(b)goto OR2;
if(c)goto then_lbl;
OR2:
if(!a)goto else_lbl;
if(!c)goto else_lbl;
then_lbl://...

mentre con if((! a && b) || c) (l'equivalente effettivo) ottieni

if(a) goto OR2;
if(b) goto then_lbl;
OR2:
if(!c) goto else_lbl;
then_lbl://..

quindi non c'è alcuna differenza reale (si passa sempre attraverso 2 o 3 rami)

Ma ripeterò il mio punto: questo tipo di micro ottimizzazione è assolutamente inutile di cui preoccuparsi a meno che non faccia parte di un collo di bottiglia dimostrabile e la maggior parte delle volte il problema < em> non è un'istruzione if malformata

qui troverai che la leggibilità supera la velocità

    
risposta data 30.08.2013 - 10:17
fonte
2

Sei sicuro che sia

(! a && b)

anziché

!(a && b)

In caso contrario, le parentesi non sono necessarie e causano solo confusione.

In ogni caso, generalmente meno operazioni hai per il computer, e in entrambe le condizioni AND o OR è meglio mettere il "più semplice" prima, il tuo modo più efficace di scrivere questo per il computer (non necessariamente il lettore ) sarebbe:

c || b && ! a

Questo presuppone la precedenza degli operatori in stile C per gli operatori logici.

    
risposta data 30.08.2013 - 10:03
fonte
2

Le due affermazioni hanno la stessa complessità computazionale . Entrambi vengono eseguiti in un tempo costante (in termini di complessità), che può essere scritto O (1). Poiché il numero di stati di input è finito (8), difficilmente potrebbe essere altrimenti.

Se a , b e c sono espressioni generali anziché variabili, !b && c || a && c potrebbe causare il c da valutare due volte. Se c non è idempotente (ad esempio se l'esecuzione di c una seconda volta non fa necessariamente ciò che ha fatto la prima volta), tutte le scommesse sono disattivate. Le due espressioni che proponi inoltre non eseguono a , b e c nello stesso ordine in tutti i casi, quindi se il loro tempo di esecuzione dipende dall'ordine in cui sono chiamate, di nuovo, tutte le scommesse sono disattivate .

Se ciò che ti stai chiedendo non è, in realtà, la complessità computazionale (che si occupa delle misure asintotica degli importi di calcolo) ma esatto il numero di passaggi di calcolo, quindi la risposta è che non esiste una risposta generale. Il numero esatto di passaggi di calcolo dipende dal modello di calcolo scelto. Per l'analisi asintotica, la scelta del modello è per lo più irrilevante: qualsiasi modello ragionevole fornisce lo stesso risultato (o talvolta ci sono alcune scelte ragionevoli del modello, e devi dire quale stai usando). Se vuoi un'analisi più accurata, devi fornire un modello dettagliato.

In questo caso è completamente inutile perfezionare l'analisi perché la differenza pratica si basa su molti fattori che non possono essere prontamente previsti, tra cui:

  • quale codice macchina genera il compilatore (che dipende dal compilatore, dalla versione del compilatore, dalle impostazioni di ottimizzazione, dalla CPU di destinazione e dal codice circostante);
  • il modello esatto della CPU (poiché questo sarà influenzato dalla quantità di prefetching, dalla previsione del ramo, dalla profondità delle istruzioni e delle pipeline di dati, ecc.);
  • quale altro codice è stato eseguito prima (poiché questo influenza lo stato delle pipeline, della cache, del predittore del ramo, ecc.).
risposta data 30.08.2013 - 14:37
fonte
1

Non posso davvero rispondere perché

if (!b && c || a && c)

non è uguale a

if ((! a && b) || c)

Le tabelle di verità per ciascuno sono sotto, output abc:

000 0
001 1
010 0
011 0
100 0
101 1
110 0
111 1

questo non corrisponde a quanto sopra

000 0
001 1
010 1
011 1
100 0
101 1
110 0
111 1

programma di test

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int a,b,c;


int main ( void )
{
    for(a=0;a<2;a++)
    for(b=0;b<2;b++)
    for(c=0;c<2;c++)
    {
        printf("%u%u%u ",a,b,c);
        if (!b && c || a && c)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    printf("\n");

    for(a=0;a<2;a++)
    for(b=0;b<2;b++)
    for(c=0;c<2;c++)
    {
        printf("%u%u%u ",a,b,c);
        if ((! a && b) || c)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    return(0);
}

Aggiungi altre parentesi per migliorare l'ordine delle operazioni e / o pubblicare un'equazione equivalente, quindi possiamo parlare di come differiscono per complessità.

Questo è equivalente

    if (c && (!(!a && b)))

nota l'opinione di clang su questa sintassi:

fun.c:5:12: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if (!b && c || a && c) return(1);
        ~~~^~~~ ~~
fun.c:5:12: note: place parentheses around the '&&' expression to silence this
      warning
    if (!b && c || a && c) return(1);
           ^
        (      )
fun.c:5:22: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if (!b && c || a && c) return(1);
                ~~ ~~^~~~
fun.c:5:22: note: place parentheses around the '&&' expression to silence this
      warning
    if (!b && c || a && c) return(1);
                     ^
                   (     )

Usando arm come target di test, la risposta non sarà deterministica BTW, è il compilatore e il target e il sistema dipendente da cui è più veloce, meno il calcolo, ecc. Guarda in superficie con un braccio e le sue funzioni di set di istruzioni la prima soluzione con gcc è pulita e deterministica (nessun ramo).

Ovviamente questo cambierà con ogni compilatore e target e anche con qualunque codice circonda quell'istruzione if. (nota la versione di gcc e clang / llvm può / creerà risultati diversi).

unsigned int bool1 ( unsigned int a, unsigned int b, unsigned int c )
{
    if (!b && c || a && c) return(1);
    return(0);
}

unsigned int bool2 ( unsigned int a, unsigned int b, unsigned int c )
{
    if (c && (!(!a && b))) return(1);
    return(0);
}

//gcc

//00000000 <bool1>:
   //0: e2900000    adds    r0, r0, #0
   //4: 13a00001    movne   r0, #1
   //8: e3510000    cmp r1, #0
   //c: 03800001    orreq   r0, r0, #1
  //10: e3520000    cmp r2, #0
  //14: 03a00000    moveq   r0, #0
  //18: 12000001    andne   r0, r0, #1
  //1c: e12fff1e    bx  lr

//00000020 <bool2>:
  //20: e3520000    cmp r2, #0
  //24: 0a000005    beq 40 <bool2+0x20>
  //28: e2711001    rsbs    r1, r1, #1
  //2c: 33a01000    movcc   r1, #0
  //30: e3500000    cmp r0, #0
  //34: 01a00001    moveq   r0, r1
  //38: 13810001    orrne   r0, r1, #1
  //3c: e12fff1e    bx  lr
  //40: e1a00002    mov r0, r2
  //44: e12fff1e    bx  lr

//clang

//bool1:                                  @ @bool1
    //cmp   r1, #0
    //bne   .LBB0_2
    //cmp   r2, #0
    //movne r0, #1
    //movne pc, lr
//.LBB0_2:                                @ %lor.lhs.false
    //cmp   r2, #0
    //movne r2, #1
    //cmp   r0, #0
    //movne r0, #1
    //and   r0, r0, r2
    //mov   pc, lr

//bool2:                                  @ @bool2
    //mov   r3, r0
    //cmp   r2, #0
    //beq   .LBB1_2
    //mov   r0, #1
    //cmp   r3, #0
    //movne pc, lr
    //cmp   r1, #0
    //movne r0, #0
    //b .LBB1_3
//.LBB1_2:                                @ %if.end
    //mov   r0, #0
//.LBB1_3:                                @ %return
    //mov   pc, lr
    
risposta data 14.09.2013 - 15:58
fonte

Leggi altre domande sui tag