È buona pratica sostituire la divisione con la moltiplicazione quando possibile?

68

Ogni volta che ho bisogno di una divisione, ad esempio, il controllo delle condizioni, vorrei rifattorizzare l'espressione della divisione in moltiplicazione, ad esempio:

Versione originale:

if(newValue / oldValue >= SOME_CONSTANT)

Nuova versione:

if(newValue >= oldValue * SOME_CONSTANT)

Perché penso che possa evitare:

  1. Divisione per zero

  2. Overflow quando oldValue è molto piccolo

È giusto? C'è un problema con questa abitudine?

    
posta mmmaaa 03.01.2018 - 02:52
fonte

9 risposte

71

Due casi comuni da considerare:

Aritmetico intero

Ovviamente se usi l'aritmetica dei numeri interi (che tronca) otterrai un risultato diverso. Ecco un piccolo esempio in C #:

public static void TestIntegerArithmetic()
{
    int newValue = 101;
    int oldValue = 10;
    int SOME_CONSTANT = 10;

    if(newValue / oldValue > SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue > oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Output:

First comparison says it's not bigger.
Second comparison says it's bigger.

Aritmetica in virgola mobile

A parte il fatto che la divisione può produrre un risultato diverso quando divide per zero (genera un errore, mentre la moltiplicazione non lo fa), può anche causare errori di arrotondamento leggermente diversi e un risultato diverso. Semplice esempio in C #:

public static void TestFloatingPoint()
{
    double newValue = 1;
    double oldValue = 3;
    double SOME_CONSTANT = 0.33333333333333335;

    if(newValue / oldValue >= SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue >= oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Output:

First comparison says it's not bigger.
Second comparison says it's bigger.

Nel caso in cui non mi credi, qui c'è un Fiddle che puoi eseguire e vedere tu stesso.

Altre lingue potrebbero essere diverse; tenere presente, tuttavia, che C #, come molte altre lingue, implementa una libreria IEEE standard (IEEE 754) a virgola mobile, quindi dovresti ottenere gli stessi risultati in altri tempi di esecuzione standardizzati.

Conclusione

Se lavori campo verde , probabilmente stai bene.

Se si sta lavorando su un codice legacy e l'applicazione è un'applicazione finanziaria o di altro tipo sensibile che esegue operazioni aritmetiche ed è richiesta per fornire risultati coerenti, sii molto prudente quando cambi le operazioni. Se devi, assicurati di avere dei test unitari in grado di rilevare eventuali cambiamenti nell'aritmetica.

Se stai semplicemente facendo cose come contare gli elementi in una matrice o altre funzioni computazionali generali, probabilmente starai bene. Non sono sicuro che il metodo di moltiplicazione renda più chiaro il tuo codice.

Se stai implementando un algoritmo per una specifica, non cambierei nulla, non solo a causa del problema degli errori di arrotondamento, ma in modo che gli sviluppatori possano rivedere il codice e mappare ogni espressione alle specifiche per assicurarti che non ci sono difetti di implementazione.

    
risposta data 03.01.2018 - 05:43
fonte
25

Mi piace la tua domanda in quanto potenzialmente copre molte idee. Nel complesso, sospetto che la risposta sia dipende , probabilmente sui tipi coinvolti e sul possibile intervallo di valori nel tuo caso specifico.

Il mio istinto iniziale è quello di riflettere sullo stile , es. la tua nuova versione è meno chiara per il lettore del tuo codice. Immagino che dovrei pensare per un secondo o due (o forse più lungo) per determinare l'intenzione della tua nuova versione, mentre la tua vecchia versione è immediatamente chiara. La leggibilità è un attributo importante del codice, quindi c'è un costo nella tua nuova versione.

Hai ragione che la nuova versione evita una divisione per zero. Certamente non è necessario aggiungere una guardia (lungo le linee di if (oldValue != 0) ). Ma ha senso? La tua vecchia versione riflette un rapporto tra due numeri. Se il divisore è zero, il tuo rapporto non è definito. Questo potrebbe essere più significativo nella tua situazione, es. in questo caso non dovresti produrre un risultato.

La protezione dall'overflow è discutibile. Se sai che newValue è sempre più grande di oldValue , forse potresti fare quell'argomento. Tuttavia, potrebbero verificarsi casi in cui anche (oldValue * SOME_CONSTANT) supererà. Quindi non vedo molto guadagno qui.

Potrebbe esserci un argomento per ottenere prestazioni migliori perché la moltiplicazione può essere più veloce della divisione (su alcuni processori). Tuttavia, ci dovrebbero essere molti calcoli come questi per questo a un guadagno significativo, cioè. fai attenzione all'ottimizzazione prematura.

Riflettendo su quanto sopra, in generale non penso che ci sia molto da guadagnare con la tua nuova versione rispetto alla vecchia versione, in particolare vista la riduzione della chiarezza. Tuttavia ci possono essere casi specifici in cui vi è qualche vantaggio.

    
risposta data 03.01.2018 - 03:22
fonte
22

No.

Probabilmente chiamerei l'ottimizzazione prematura , in senso lato, indipendentemente dal fatto che tu stia ottimizzando per performance , come generalmente si intende la frase, o qualsiasi altra cosa che possa essere ottimizzata, come conteggio dei margini , lines del codice o, ancora più in generale, cose come "design".

L'implementazione di questo tipo di ottimizzazione come procedura operativa standard mette a rischio la semantica del tuo codice e potenzialmente nasconde i bordi. I casi limite che si ritiene possano eliminare in modo silenzioso potrebbero dover essere esplicitamente indirizzati comunque . Inoltre, è infinitamente più facile eseguire il debug dei problemi attorno ai bordi rumorosi (quelli che generano eccezioni) su quelli che falliscono silenziosamente.

E, in alcuni casi, è addirittura vantaggioso "de-ottimizzare" per motivi di leggibilità, chiarezza o chiarezza. Nella maggior parte dei casi, gli utenti non noteranno che hai salvato alcune righe di codice o cicli della CPU per evitare la gestione dei casi limite o la gestione delle eccezioni. D'altra parte, influenzerà le persone - i tuoi colleghi, per lo meno. (E anche, quindi, il costo per costruire e mantenere il software.)

Predefinito a qualsiasi cosa è più "naturale" e leggibile rispetto al dominio dell'applicazione e al problema specifico. Mantenerlo semplice, esplicito e idiomatico. Ottimizza come è necessario per i guadagni significativi o per raggiungere una soglia di usabilità legittima.

Nota anche: I compilatori spesso ottimizzare la divisione per te comunque - quando è sicuro per farlo.

    
risposta data 03.01.2018 - 06:45
fonte
12

Usa quello che è meno bacato e più logico.

Di solito , la divisione per variabile è comunque una cattiva idea, dato che solitamente il divisore può essere zero.
La divisione di una costante di solito dipende solo dal significato logico.

Ecco alcuni esempi per mostrare che dipende dalla situazione:

Divisione buona:

if ((ptr2 - ptr1) >= n / 3)  // good: check if length of subarray is at least n/3
    ...

Moltiplicazione non valida:

if ((ptr2 - ptr1) * 3 >= n)  // bad: confusing!! what is the intention of this code?
    ...

Moltiplicazione buona:

if (j - i >= 2 * min_length)  // good: obviously checking for a minimum length
    ...

Division bad:

if ((j - i) / 2 >= min_length)  // bad: confusing!! what is the intention of this code?
    ...

Moltiplicazione buona:

if (new_length >= old_length * 1.5)  // good: is the new size at least 50% bigger?
    ...

Division bad:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
    
risposta data 03.01.2018 - 10:28
fonte
3

Fare qualsiasi cosa "quando possibile" è molto raramente una buona idea.

La priorità numero uno dovrebbe essere la correttezza, seguita da leggibilità e manutenibilità. Sostituire ciecamente la divisione con la moltiplicazione quando possibile, spesso fallisce nel dipartimento di correttezza, a volte solo in casi rari e quindi difficili da trovare.

Fai ciò che è corretto e più leggibile. Se hai prove concrete che scrivere il codice nel modo più leggibile causi un problema di prestazioni, puoi prendere in considerazione la possibilità di cambiarlo. Care, matematica e recensioni di codice sono i tuoi amici.

    
risposta data 03.01.2018 - 19:47
fonte
1

Per quanto riguarda la leggibilità del codice, penso che in molti casi la moltiplicazione sia in realtà più leggibile. Ad esempio, se c'è qualcosa che devi controllare se newValue è aumentato del 5% o più sopra oldValue , allora 1.05 * oldValue è una soglia rispetto alla quale testare newValue , ed è naturale scrivere

    if (newValue >= 1.05 * oldValue)

Ma fai attenzione ai numeri negativi quando rifattori le cose in questo modo (sostituendo la divisione con la moltiplicazione o sostituendo la moltiplicazione con la divisione). Le due condizioni considerate sono equivalenti se è garantito che oldValue non sia negativo; ma supponiamo che newValue sia in realtà -13,5 e oldValue sia -10,1. Poi

newValue/oldValue >= 1.05

valuta true , ma

newValue >= 1.05 * oldValue

valuta falso .

    
risposta data 03.01.2018 - 13:01
fonte
1

Nota il famoso articolo Divisione per numeri invarianti che utilizzano la moltiplicazione .

Il compilatore sta effettivamente facendo moltiplicazione, se il numero intero è invariante! Non una divisione. Questo accade anche per la mancanza di potenza di 2 valori. La potenza di 2 divisioni utilizza ovviamente shift di bit e quindi è ancora più veloce.

Tuttavia, per gli interi non invarianti, è responsabilità dell'utente ottimizzare il codice. Assicurati prima di ottimizzare che stai davvero ottimizzando un vero collo di bottiglia e che la correttezza non è sacrificata. Fai attenzione all'overflow dei numeri interi.

Mi interessa la micro-ottimizzazione, quindi probabilmente darei un'occhiata alle possibilità di ottimizzazione.

Pensa anche alle architetture su cui gira il tuo codice. Soprattutto ARM ha una divisione estremamente lenta; devi chiamare una funzione per dividere, non ci sono istruzioni di divisione in ARM.

Inoltre, su architetture a 32 bit, la divisione a 64 bit non è ottimizzata, poiché I trovato .

    
risposta data 03.01.2018 - 16:51
fonte
1

Prendendo in considerazione il tuo punto 2, impedirà effettivamente l'overflow per un% co_de molto piccolo. Tuttavia se oldValue è anche molto piccolo allora il tuo metodo alternativo finirà con underflow, dove il valore non può essere rappresentato con precisione.

E viceversa, cosa succede se SOME_CONSTANT è molto grande? Hai gli stessi problemi, solo il contrario.

Se vuoi evitare (o minimizzare) il rischio di overflow / underflow, il modo migliore è verificare se oldValue è più vicino in grandezza a newValue o a oldValue . Puoi quindi scegliere l'operazione di divisione appropriata,

    if(newValue / oldValue >= SOME_CONSTANT)

o

    if(newValue / SOME_CONSTANT >= oldValue)

e il risultato sarà più accurato.

Per dividere per zero, nella mia esperienza non è quasi mai appropriato essere "risolto" in matematica. Se si dispone di uno split-by-zero nei controlli continui, quasi sicuramente si ha una situazione che richiede un'analisi e qualsiasi calcolo basato su questi dati non ha senso. Un controllo esplicito di divisione per zero è quasi sempre la mossa appropriata. (Nota che qui dico "quasi" qui, perché non pretendo di essere infallibile. Mi limiterò a notare che non ricordo di aver visto una buona ragione per questo in 20 anni di scrittura di software embedded, e di andare avanti .)

Tuttavia, se hai un rischio reale di overflow / underflow nella tua applicazione, probabilmente questa non è la soluzione giusta. Più probabilmente, dovresti generalmente controllare la stabilità numerica del tuo algoritmo, o forse semplicemente spostarti verso una rappresentazione di precisione più alta.

E se non hai un rischio provato di overflow / underflow, allora ti stai preoccupando di nulla. Ciò significa che letteralmente devi dimostrare che ne hai bisogno, con i numeri, nei commenti accanto al codice che spiegano al maintainer perché è necessario. Come principale ingegnere che esamina il codice di altre persone, se mi imbatto in qualcuno che sta compiendo uno sforzo extra per questo, personalmente non accetterei nulla di meno. Questo è un po 'l'opposto dell'ottimizzazione prematura, ma in genere avrebbe la stessa causa principale - l'ossessione per i dettagli che non fa differenza funzionale.

    
risposta data 05.01.2018 - 13:50
fonte
0

Incapsula l'aritmetica condizionale in metodi e proprietà significative. Non solo i buoni nomi ti diranno che "A / B" significa , controllo dei parametri & anche la gestione degli errori può nascondersi bene.

È importante sottolineare che, poiché questi metodi sono composti in una logica più complessa, la complessità estrinseca rimane molto gestibile.

Direi che la sostituzione della moltiplicazione sembra una soluzione ragionevole perché il problema è mal definito.

    
risposta data 04.01.2018 - 19:07
fonte

Leggi altre domande sui tag