Quindi, ho quattro numeri interi e ho bisogno di scoprire i due più bassi di questi quattro. Quale sarebbe il modo più efficace di farlo in C (o in qualsiasi altra lingua)?Ricerca di due valori minimi su quattro?
Modifica: Ho bisogno di un'implementazione fissa, per motivi di efficienza in quanto è un'operazione molto critica che verrà eseguita migliaia di volte.
Ecco un'implementazione efficace utilizzando sorting networks:
inline void Sort2(int *p0, int *p1)
{
if (*p0 > *p1)
{
const int temp = *p0;
*p0 = *p1;
*p1 = temp;
}
}
inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
Sort2(p0, p1);
Sort2(p2, p3);
Sort2(p0, p2);
Sort2(p1, p3);
Sort2(p1, p2);
}
Questo richiede solo 5 confronta e fino a 5 swaps. Puoi semplicemente ignorare i risultati per p2, p3.
Si noti che per un'applicazione con prestazioni elevate Sort2 può essere implementato senza rami in una o due istruzioni su alcune architetture.
Questo è meraviglioso, grazie. –
Si noti che la mia risposta è efficiente nel peggiore dei casi e più efficiente nel migliore dei casi, in termini di numero di confronti. – Hbcdev
@Hbcdev: sfortunatamente la vostra soluzione ha molti rami, mentre la soluzione di cui sopra può essere implementata senza rami. Il numero di confronti e swap può essere simile, ma i rami sono molto costosi quando sono male interpretati. –
Vorrei creare un array, ordinare e prendere i primi due valori.
o gli ultimi due a seconda di come hai risolto ;-) –
Penso che sia possibile ordinare l'array e selezionare i primi due elementi.
Basta scrivere un ciclo e tenere traccia dei valori minimi 2? Dovrebbe essere al massimo O (2N), che è la migliore complessità raggiungibile.
no, [un'altra risposta qui] (http://stackoverflow.com/a/12216412/849891) effettua solo 3 confronti nel 25% dei casi o giù di lì. –
sì, sì, scrivere tutti i confronti necessari l'uno sotto l'altro è davvero molto più veloce – Minion91
non si tratta di come scriverli, ma di trovare un ordine specifico di confronti. –
Il modo più efficiente? Cercando di evitare ulteriori passaggi, ho ottenuto questo (in pseudo-codice). Ciò eviterà qualsiasi confronto non necessario che otterrete con altre soluzioni più generali (in particolare quelle che non traggono vantaggio dalla natura transitiva delle operazioni di confronto).
Tenete presente che si tratta solo di efficienza, non mirando affatto a un codice bello.
if a<=b:
if b<=c:
# c too big, which of b and d is smaller?
if b<=d:
return (a,b)
else:
return (a,d)
else if b<=d:
# a and c both < b, and b < d
return (a,c)
else:
# b is > a, c and d. Down to just those three.
if a<=c:
if c<=d:
# a < c < d
return (a,c)
else:
# a and d both < c
return (a,d)
else if d<=a:
# Both c and d < a
return (c,d)
else:
# c < a < d
return (a,c)
else:
# b < a
if a<=c:
# c too big, which of a and d is smaller?
if a<=d:
return (a,b)
else:
return (b,d)
else if a<=d:
# b and c both < a, and a < d
return (b,c)
else:
# a is > b, c and d. Down to just those three.
if b<=c:
if c<=d:
# b < c < d
return (b,c)
else:
# b and d both < c
return (b,d)
else if d<=b:
# Both c and d < b
return (c,d)
else:
# c < b < d
return (b,c)
penso che questo ha un caso peggiore di 5 confronti e un caso migliore di 3 (ovviamente non c'è modo di farlo in meno di 3 confronto).
Puoi scappare con esattamente 4 confronti e massimo 4 scambi.
inline void swap(int* i, int* j) {
static int buffer;
buffer = *j;
*j = *i;
*i = buffer;
}
inline void sort2(int* a, int* s) {
if (*s < a[1])
swap(s,a+1);
if (*s < a[0]) // it is NOT sufficient to say "else if" here
swap(s,a);
}
inline void sort4(int* a) {
sort2(a,a+2);
sort2(a,a+3);
}
Il risultato sarà seduto il primo per le cellule, ma si noti che queste cellule non sono necessariamente ordinati! Sono solo gli elementi più piccoli.
questo non è ottimale. [un'altra risposta qui] (http://stackoverflow.com/a/12216412/849891) effettua solo 3 confronti nel 25% dei casi o giù di lì. –
@WillNess: Grazie. Fisso. – bitmask
si può realizzare con un massimo di 4 confronti:
a1 e più grande è essere a2a3 e più grande è essere a4Per vedere che questo è vero, si può visualizzate tutte le combinazioni di possibili ritorni:
(a1, a2) (a1, a3) (a1, a4)
(a2, a3) (a2, a4)
(a3, a4)
Non sono sicuro di ciò, quindi non lo invierò come risposta, ma un metodo di "forza bruta" per scansionare l'elenco per il valore più basso due volte, eliminando l'elemento selezionato nel primo passaggio sul secondo passaggio, sarebbe garantire non più di 5 confronti ... –
Penso che http://stackoverflow.com/a/12215020/705048 sarà difficile da battere per l'efficienza. Ma se lo usi, assicurati di commentarlo a fondo per il bene dei tuoi colleghi! – Hbcdev