Il modo più veloce per determinare il minimo non zero

Question

Avendo una matrice di 4 interi per esempio, come si può determinare che è minimo non zero - nel modo più veloce?

Answer 1

C'è una soluzione parallela a questo problema, ma probabilmente non ne vale la pena.

Prima definiamo un'operazione xchg(m, n) su un array un:

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n]) 

Questa operazione smista 'm' due elementi e 'n' in ordine ascendente se entrambi contengono valori diversi da zero, o swap loro se il valore nell'elemento 'm' è zero.

Poi si esegue una serie di cinque tali operazioni come segue:

xchg(0,2) xchg(1,3) 
xchg(0,1) xchg(2,3) 
xchg(1,2) 

Gli accoppiati xchg operazioni possono essere eseguite in parallelo, riducendo il costo di tempo del 40% per un esecuzione strettamente sequenziale. Al termine, tutti gli elementi diversi da zero dell'array verranno ordinati in ordine crescente. L'elemento di valore più piccolo sarà in [0]. Se quel valore è zero, non ci sono valori diversi da zero nella matrice.

Questa soluzione sfrutta il parallelismo inerente fornita da reti di ordinamento (http://en.wikipedia.org/wiki/Sorting_network), ma una scansione sequenziale di 4 elementi usa anche non più di tre operazioni di confronto, e richiede cruciale metà molti storage scrive su media:

scansione sequenziale

int v = a[0] 
for (n = 1; n < 4; n++) { 
    if ((a[n] < v && a[n] != 0) || v == 0) v = a[n] 
} 

Answer 2

Dipende dall'ingresso. Se la matrice non è ordinata, sarà necessario scorrere l'intero array. Se l'array è ordinato, devi solo eseguire il ciclo finché non trovi qualcosa che non è zero: è molto più breve.

Answer 3

A meno che non si mantenga il valore minimo quando gli elementi vengono aggiunti all'array o si mantiene l'array in un ordine ordinato, non vedo altra soluzione se non per iterare ogni membro per determinare il valore minimo.

Non esiste un modo "veloce" di testare ciascun membro.

Generalmente suggerisco di non ottimizzare qualcosa a meno che non si dimostri effettivamente lento. La vecchia regola del tuo programma spende il 90% delle volte in cui il 10% del codice è generalmente valido. Così pure le regole che i programmatori hanno il 99,99% di probabilità di ottimizzare il codice non in quel 10%.

un profilo del proprio codice - profilo il codice - il profilo del tuo codice

Answer 4

Bene il modo più veloce per codificare è std::min({a,b,c,d}).

Su una nota più seria: se l'applicazione è un collo di bottiglia su qualcosa come prendere il minimo di molti valori, una soluzione migliore potrebbe essere quella di trovare un modo per suddividere l'attività di ricerca minima in parti e inviare alla GPU (o molti thread), che possono quindi eseguire molti calcoli di ricerca minimi contemporaneamente.

Il parallelismo probabilmente sarebbe di aiuto più che cercare di scrivere una funzione minima in assembly.

Answer 5

Se stiamo pensando di micro-ottimizzazioni, quindi potenzialmente potrebbe essere più veloce per calcolare min(min(a,b),min(c,d)) invece di min(min(min(a,b),c),d) su un moderno processore out-of-order, a causa delle dipendenze meno sequenziali: nel primo il processore può calcolare min(a,b) e min(c,d) indipendentemente in parallelo, se ha unità di esecuzione sufficienti disponibili. Ciò presuppone che il processore abbia un'istruzione di movimento condizionale, in modo che il calcolo di min non richieda la diramazione.