Quale dei due è efficiente?

Question

Quale dei due è efficiente?

#1 da (3 voti)
#2 da (0 voti)

-4

Ho letto un blog in cui l'autore ha menzionato i due stili di codifica sottostanti.

Min e Max 1

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
if (x < min) min = X;
if (x > max) max = X; 
}

Min e Max 2

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int x : array) {
    if (x < min) min = X;
}
for (int x : array) {
    if (x > max) max = X;
}

Ma non hai mai concluso quale sia efficiente.

Qualcuno può indicare quale è efficiente e amp; perché?

optimization

posta penta 17.06.2017 - 17:27

fonte

2 risposte

Leggi altre domande sui tag optimization

La classe derivata può essere singleton? [chiuso] Perché questa app Android convalida il campo email su ogni cambio di carattere e non solo quando viene premuto il pulsante Salva?

score 3 · Answer 1

Entrambi hanno prestazioni O (N), vale a dire che scalano linearmente con la dimensione dell'array.

Tuttavia, e senza considerare se si tratta di un'ottimizzazione o meno, se la dimensione dell'array è significativa rispetto alle dimensioni della cache del processore, allora il primo avrà meno errori di cache, il che sarà considerevole fattore di prestazioni, poiché l'utilizzo della cache è un grosso problema per i processori moderni.

Quest'ultimo approccio effettuerà una scansione lineare della memoria due volte. Quindi, se l'array è sufficientemente grande, al primo passaggio, l'inizio dell'array verrà inserito nella cache, ma verrà eliminato dalle successive parti dell'array.

Il secondo passaggio dovrà quindi trascinare ancora una volta l'intero array attraverso la cache. Se il lavoro del secondo passaggio può sovrapporsi al lavoro del primo, verrà evitato questo ulteriore tiro attraverso il cache.

Per la migliore separazione delle preoccupazioni, dovremmo fare ognuna separatamente, ma sarebbe simile a questa:

int min = Integer.MAX_VALUE;
for (int x : array) {
    if (x < min) min = x;
}

int max = Integer.MIN_VALUE;
for (int x : array) {
    if (x > max) max = x;
}

e forse ognuno nel proprio metodo. (La differenza è che non inizializziamo min e max insieme, quindi facciamo min, quindi max.)

Tuttavia, se hai sempre bisogno della coppia insieme, potresti utilizzare il tuo primo approccio e non considererei nemmeno un'ottimizzazione rispetto a quest'ultimo approccio, dato il raggiungimento della coppia minima / massima come requisito.

score 0 · Answer 2

Quello che stai cercando di fare è chiamato "micro-ottimizzazione". Le micro-ottimizzazioni di solito non guadagnano molto; spesso si possono ottenere risparmi molto più grandi guardando le cose in un contesto più ampio.

Un esempio: inizio con un array vuoto. Quindi aggiungo diecimila numeri interi casuali alla fine dell'array, e dopo aver aggiunto ogni intero voglio conoscere l'elemento array più grande e più piccolo. La micro-ottimizzazione di trovare il massimo e il minimo di un array il più velocemente possibile può renderlo due volte più veloce, o forse cinque volte più veloce. L'ottimizzazione di livello superiore, ricordando il massimo e il minimo dell'array precedente e quindi confrontandoli con il nuovo valore aggiunto, lo rende 1.000 volte più veloce.