int vs float efficienza aritmetica in Java

Question

Sto scrivendo un'applicazione che utilizza l'algoritmo Dijkstra per trovare percorsi minimi nel grafico. I pesi dei nodi e degli spigoli del grafico sono numeri float, quindi l'algoritmo esegue molti aritmetici su numeri mobili. Potrei ottenere un tempo di esecuzione migliore se converto tutto il peso in int s? Le operazioni aritmetiche int sono più veloci in Java e quelle mobili?

Ho provato a scrivere un semplice benchmark per verificarlo, ma non sono soddisfatto dei risultati ottenuti. Forse il compilatore ha ottimizzato alcune parti del programma, quindi i risultati non mi sembrano buoni.

---

EDIT:

Il problema che sto cercando di risolvere è nel campo Information Retrieval. L'applicazione dovrebbe mostrare le risposte a una query posta come un insieme di parole chiave.

La mia struttura dati è un grafico orientato ponderato. Dato un insieme di nodi foglia, devo trovare un albero più piccolo che colleghi questi nodi e mostri la risposta all'utente. I pesi sono assegnati da una funzione di ponderazione basata parzialmente sulla tecnica tf/idf. L'utente non sa quali pesi assegnare ai nodi e ai bordi vuole solo vedere le risposte rilevanti per la query che ha posto. Non sono richiesti risultati esatti, solo una possibilità per enumerare le risposte in base al loro peso. Solo l'uso nativo della funzione di ponderazione (come ho accennato è basato su tf/idf) dà pesi flottanti quindi ho usato i float finora.

Spero che questo aggiunga un po 'di background alla domanda.

Answer 1

Come sempre con questo tipo di cose, è necessario impostare alcuni obiettivi di rendimento, quindi configurare l'app per vedere se li soddisfa.

Spesso si possono trovare risultati sorprendenti; che il tempo impiegato non è affatto influenzato dal tipo numerico di base o che il tuo algoritmo non è ottimale.

E per quanto riguarda le ottimizzazioni del compilatore, rappresentano una parte reale e valida dell'ottimizzazione delle prestazioni.

Se l'utilizzo di tipo A è teoricamente più veloce rispetto all'utilizzo di tipo B, ma il compilatore può ottimizzare il tipo B per essere più veloce in uno scenario reale, è una prova preziosa, non una fonte di dissapointment.

Answer 2

per operazioni semplici int è più veloce, tuttavia con int è possibile che si debba fare più lavoro per ottenere lo stesso risultato. per esempio.

come float

float f = 15 * 0.987; 

come int

int i = 15 * 987/1000; 

La divisione supplementare significa il funzionamento int può richiedere più tempo.

Answer 3

Non credo.

Float è 4 byte. E l'Int in java è anch'esso a 4 byte.

Perché non utilizzare la data (java.util.Date) per ottenere il tempo di esecuzione?

È possibile definire un grafico che è proprio 100000 nodi. Quindi calcola.

Answer 4

Se si desidera confrontare i pesi, è preferibile che fluisca a int.

Answer 5

Generalmente non si deve preoccupare di una scelta tra int e float per motivi di prestazioni.

Ecco un estratto dalla Appendice di Java Puzzlers:

-virgola mobile aritmetica è inesatta. Non utilizzare virgola mobile dove sono richiesti risultati esatti; invece, utilizzare un tipo integrale o BigDecimal. Preferire double a float.

Se non avete una buona ragione, si dovrebbe in genere preferiscono double a float se è necessario utilizzare un'operazione in virgola mobile. Se si desidera ottenere il risultato esatto, andare avanti e utilizzare BigDecimal; sarà più lento dal momento che non è un primitivo, ma se la profilazione non dimostra che non è accettabile, questa è spesso l'opzione migliore.

Se è necessario utilizzare l'operazione in virgola mobile, tentare di ottimizzare questo utilizzando int è sconsigliato. È probabile che si tratti di un'ottica prematura e complicherà inutilmente il codice. Scrivilo nel modo più naturale e più leggibile. Non complicare inutilmente il tuo codice per ottenere un leggero miglioramento delle prestazioni.

Se in realtà non è necessario il funzionamento in virgola mobile, utilizzare in ogni caso int o long.

Answer 6

Penso che le prestazioni dipendano molto dall'algoritmo e dalla piattaforma su cui è in esecuzione il software.

Se si eseguono calcoli matrix/array su una piattaforma X86, il runtime potrebbe ottimizzarlo per utilizzare SSE, che è un set di istruzioni esteso solo float/double.

Su altre piattaforme il runtime potrebbe ottimizzare su OpenCL (non credo che qualcuno lo faccia al momento, ma potrebbe succedere :). Non ho idea di cosa corre più veloce su tale piattaforma e in quali condizioni. Potrebbe essere semplicemente che OpenCL sia ottimizzato per un carico di lavoro intero.

In queste circostanze concluderei che non è utile ottimizzare il tipo di dati (float o int) a questo punto e solo ottimizzare la leggibilità del codice.

Se il codice è altamente critico per le prestazioni e si sa esattamente su quale hardware il sistema sarà in esecuzione ora e in futuro, è possibile testare carichi di lavoro tipici con vari algoritmi e selezionare quello che meglio soddisfa le proprie esigenze.

Ma in generale, è sufficiente utilizzare un algoritmo che è possibile comprendere, mantenere il codice leggibile e, quindi, il conteggio degli errori basso. Il codice veloce non vale più di tanto se i risultati non sono corretti :)

Answer 7

Le sottrazioni di numeri interi sono ~ 2,5 volte più veloci delle doppie sottrazioni, sulla mia macchina. Le moltiplicazioni intere tuttavia sono solo ~ 1,5 volte più veloci delle doppie moltiplicazioni.

Il seguente test funziona su dati casuali, che potrebbero impedire l'ottimizzazione del compilatore.

// test whether int subs are faster than double subs 
public void compareIntAndFloatSubtraction(){ 

    int N = 100000; // input array size 
    int k = 100000; // number of mathematical operations performed on each element 

    // generate random data 
    int[] ints = new int[N]; 
    double[] doubles = new double[N]; 
    Random r = new Random(1l); 
    for (int i = 0; i < N; i++) { 
     ints[i] = r.nextInt(); 
     doubles[i] = r.nextDouble(); 
    } 

    // measure integer subtractions 
    long before = System.currentTimeMillis(); 
    for (int i = 1; i < N; i++) { 
     for (int j = 0; j < k; j++) { 
      ints[i] -= ints[i-1]; // referring to another element might prevent from optimization also 
     } 
    } 
    System.out.println(String.format("time needed for int subs [ms]: %s", System.currentTimeMillis()-before)); 

    // measure double subtractions 
    before = System.currentTimeMillis(); 
    for (int i = 1; i < N; i++) { 
     for (int j = 0; j < k; j++) { 
      doubles[i] -= doubles[i-1]; 
     } 
    } 
    System.out.println(String.format("time needed for double subs [ms]: %s", System.currentTimeMillis()-before)); 

}