Mi chiedo quale sarebbe l'algoritmo più veloce per questo. Ho 8 interi tra 0 e 3000 e ho bisogno di ordinarli. Sebbene siano presenti solo 8 numeri interi, questa operazione verrà eseguita milioni di volte.Qual è l'algoritmo di ordinamento più veloce per un numero ridotto di numeri interi?
Per soli 8 numeri interi e dato che l'intervallo è molto maggiore di 8, l'ordinamento di inserimento è probabilmente il migliore. Provalo per cominciare, e se il profiling indica che non è il collo di bottiglia, allora lascia.
(A seconda di molti fattori, il punto di interruzione in base al quale l'ordinamento rapido diventa migliore rispetto all'ordinamento di inserimento è in genere compreso tra 5 e 10 elementi).
Il più veloce sarebbe semplicemente scrivere un sacco di istruzioni if per confrontarle per determinare il loro ordine esatto. Ciò eliminerà il sovraccarico che ogni algoritmo di ordinamento ha.
Esattamente quello che stavo per suggerire. –
In realtà, vieni a pensarci ... quale sarebbe "l'algoritmo" per ottenere il minor numero di IF? O_O –
Si chiama rete di smistamento e credo che le reti di ordinamento ottimali siano conosciute per otto elementi. – templatetypedef
Una buona fonte per confrontare gli alghi di smistamento è http://www.sorting-algorithms.com/. Si noti che anche lo stato dell'ordine iniziale influisce sui risultati. Ma comunque per 8 interi anche un semplice bubble sort dovrebbe fare il lavoro.
Il modo più veloce è un sorting network implementato nell'hardware. Salvo che, il modo più veloce è determinato solo dalla misurazione. Cercherei
std::sort,if dichiarazioni ein quell'ordine , perché è l'ordine più facile a quello più difficile (cerca di ottenere l'ordinamento per inserimento la prima volta ...) finché non trovi qualcosa che è mantenibile una volta che gli otto costanti risultano avere il valore nove.
Inoltre, l'ordinamento di bolle, la selezione merita e l'ordinamento di shell merita di essere notificato. Non ho mai effettivamente implementato quelli perché hanno una cattiva reputazione, ma potresti provarli.
Una rete di smistamento è particolarmente efficace se si dispone di SIMD. –
@Paul R: Suppongo di sì. MMX, ecc. Hanno istruzioni di confronto a coppie? –
Confronto verticale (registro-a-registro), sì. Confronto orizzontale (confronta alto/basso all'interno del registro), n. – greyfade
Per numeri interi positivi, il tipo più veloce è conosciuto come pallottoliere sort- è O (n)
http://en.wikipedia.org/wiki/Abacus_sort
Se avete solo pochissimi elementi, quindi è improbabile che si noterà alcuna differenza di prestazioni dalla scelta di un particolare algoritmo.
Un'implementazione software di questo algoritmo è O (S), dove S è la somma di tutti gli interi. Nel caso in esame, questa è una cattiva idea. –
La seguente citazione da Bentley et al., Ingegneria funzione una sorta potrebbe essere interessante:
vari miglioramenti per inserzione, tra cui la ricerca binaria, svolgimento del ciclo, e la manipolazione n = 2 come un caso speciale, non era disponibile. Il codice più semplice è stato il più veloce.
(enfasi mia.)
Ciò suggerisce che normale inserzione senza modifiche fantasia effettivamente sarebbe un buon punto di partenza.Come ha notato Peter, otto elementi sono davvero un po 'complicati perché si trova esattamente nella gamma che di solito segna il punto di interruzione tra l'inserimento e il quicksort.
Per numeri molto piccoli di int, bubble sort può essere molto veloce. L'ordinamento a bolle con confronti numerici può essere scritto con un overhead molto basso e per il piccolo n, le effettive differenze di velocità tra O (n log n) e O (n^2) vengono eliminate.
Ecco un'implementazione di una rete tipo merging odd-even in C99 (spiacente per la lingua "sbagliato"):
#define CMP_SWAP(i, j) if (a[i] > a[j]) \
{ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
void sort8_network(int *a)
{
CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7);
CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7);
CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5);
CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5);
CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6);
}
ho cronometrato sulla mia macchina contro insertion sort
void sort8_insertion(int *a)
{
for (int i = 1; i < 8; i++)
{
int tmp = a[i];
int j = i;
for (; j && tmp < a[j - 1]; --j)
a[j] = a[j - 1];
a[j] = tmp;
}
}
Per circa 10 milioni di specie (esattamente 250 volte tutte le 40320 possibili permutazioni), la rete di sorta ha preso 0,39 secondi, mentre insertion sort ha preso 0,88 secondi. Mi sembra che entrambi siano abbastanza veloci. (Le cifre inlcude circa 0,04 secondi per generare le permutazioni.)
La rete di smistamento è "ottimale"? Voglio dire, sono 19 confronti il minimo assoluto necessario per ordinare 8 elementi? – dariopy
@dariopy: per una rete di ordinamento nel senso comune (ovvero il codice implementato solo utilizzando la macro 'CMP_SWAP' sopra), è minimo. Potresti scrivere una serie di istruzioni * nidificate * se in un modo in cui ciascun confronto determina quali ulteriori confronti vengono effettuati, quindi in qualche modo tenendo conto dei risultati di confronti precedenti. Il codice non userebbe più un numero fisso di confronti, ma potrebbe accontentarsi di un massimo di 16 confronti (un minimo di 7). Tuttavia, la funzione sarebbe molto lunga e dubito che sarebbe più veloce. –
Avete profilato il codice per dimostrare che il tipo è un collo di bottiglia? Se non è un collo di bottiglia, accelerarlo non ti farà guadagnare molto. Ordinare otto interi brevi è abbastanza veloce.
In generale, std :: sort() sarà più veloce di qualsiasi altra cosa si può scrivere, a meno che non sei un vero guru di smistamento.
ho eseguito una libreria di algoritmi di ordinamento contro tutte le permutazioni di {0, 429, 857, 1286, 1714, 2143, 2571, 3000}.
Il più veloce erano:
name time stable in-place
AddressSort 0.537 No No
CenteredLinearInsertionSort 0.621 Yes No
CenteredBinaryInsertionSort 0.634 Yes No
BinaryInsertionSort 0.639 Yes Yes
...
QuickSort 0.650 No Yes
...
BubbleSort 0.802 Yes Yes
Per ulteriori informazioni su AddressSort vedere http://portal.acm.org/citation.cfm?id=320834
Per gli interi, si potrebbe provare radix-tipo. E 'acceso).
Anni dopo) per un massimo di 32 ingressi, vedere Sorting network generator. Per 8 ingressi, dà 19 swaps, come la risposta di Sven Marnach:
o--^--^--------^--------------------------o
| | |
o--v--|--^--^--|--^--^--------------------o
| | | | | |
o--^--v--|--v--|--|--|--^--------^--------o
| | | | | | |
o--v-----v-----|--|--|--|--^--^--|--^--^--o
| | | | | | | | |
o--^--^--------v--|--v--|--|--|--v--|--v--o
| | | | | | |
o--v--|--^--^-----v-----|--|--|-----v-----o
| | | | | |
o--^--v--|--v-----------v--|--v-----------o
| | |
o--v-----v-----------------v--------------o
There are 19 comparators in this network,
grouped into 7 parallel operations.
[[0,1],[2,3],[4,5],[6,7]]
[[0,2],[1,3],[4,6],[5,7]]
[[1,2],[5,6],[0,4],[3,7]]
[[1,5],[2,6]]
[[1,4],[3,6]]
[[2,4],[3,5]]
[[3,4]]
dipende molto su ciò che i valori sono, e il loro ordine iniziale (e sull'attuazione concreta dell'algoritmo, la piattaforma, .. .). Alla fine dovrai misurare e confrontarti. –
Quanto è importante l'ordinamento 'più veloce '. Con così pochi numeri farà davvero poca differenza. Quindi, a meno che non si tratti di qualcosa di iper sensibile alla velocità, inizierei con quello che è il modo più semplice per ordinare 8 elementi. –
Se l'operazione verrà eseguita milioni di volte, forse una cosa da fare sarebbe eseguire più operazioni di ordinamento con numeri interi in parallelo. N core potrebbero produrre un aumento di velocità N volte ... –