quicksort in C ++ è lento

StackOverflow https://stackoverflow.com/questions/1208766

  •  05-07-2019
  •  | 
  •  

Domanda

Ho 9 valori sotto forma di matrice e ho bisogno di calcolare la mediana da questi valori come parte di un processo di simulazione.

Uso quicksort in C ++ (ovvero qsort ()) che rallenta il processo (poiché questo processo viene ripetuto più volte).

Esiste un algoritmo di ordinamento migliore che potrei usare?

È stato utile?

Soluzione

L'ordinamento per ottenere una mediana è molto inefficiente. Puoi invece usare STL nth_element: 

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

Nota: nth_element modificherà il vettore / array v. Effettuare prima una copia se è necessario conservare l'originale.

Altri suggerimenti

Per favore, per favore, non raccomandare mai di ordinare le bolle tranne i masochisti!

Per valori piccoli, inserimento è il migliore, ed è buono per altre applicazioni (dati quasi ordinati di qualsiasi lunghezza).

Modifica: ripulisce la formattazione, enfatizzando la risposta suggerita.

Solo 9 valori? Quicksort è eccessivo.

Forse quando si lavora con set di dati più piccoli, è possibile utilizzare un ordinamento per inserzione, un ordinamento a bolle o altri semplici algoritmi di ordinamento.

Performance

L'ordinamento a bolle presenta la complessità peggiore e media sia & # 1054; (n & # 178;), dove n è il numero di elementi da ordinare. Esistono molti algoritmi di ordinamento con il caso peggiore o la complessità mediamente migliore di O (n log n). Anche altri algoritmi di ordinamento di & # 1054; (n & # 178;), come ordinamento di inserzione, tendono ad avere prestazioni migliori di ordinamento a bolle. Pertanto l'ordinamento a bolle non è un algoritmo di ordinamento pratico quando n è grande.

Tuttavia, garantito, non hai nemmeno dovuto ordinare per ottenere la mediana come altri hanno suggerito.

  1. Come uno menzionato, non è necessario ordinare completamente per ottenere una mediana.

  2. STL ha l'algoritmo sort che di solito può eseguire il confronto in linea. Ha anche un algoritmo più intelligente di quello garantito da qsort, con worstcase di O (NlgN).

L'uso di quicksort per soli 9 valori sarà piuttosto inefficiente. Per un campione di dimensioni così ridotte, è molto meglio utilizzare un ordinamento di selezione o un ordinamento sostitutivo ... in questi metodi di ordinamento c'è un sovraccarico minimo.

Quicksort e Mergesort brillano davvero quando le dimensioni del campione raggiungono una soglia, forse 50+.

In queste situazioni, scriverei il mio codice anziché utilizzare una funzione integrata.

L'algoritmo std :: sort () è quasi sempre preferibile a qsort (). In genere è più facile da usare e funziona più velocemente.

Se vuoi entrare nei dettagli, in realtà esiste una famiglia di algoritmi di ordinamento. Stroustrup scrive in Il linguaggio di programmazione C ++ che std :: sort spesso non è esattamente la cosa giusta da usare. In questo caso, std :: nth_element () è probabilmente quello che vuoi.

Non hai abbastanza valori per lavorare con Quicksort e dovresti usare algoritmi meno avanzati (es: Bubble sort, Insertion sort, ... spiegazione qui .

C'è un costo associato alla configurazione di Quicksort e quando non hai abbastanza valori, è inutile usare questa bestia.

Inserimento ordinamento ..

Su piccoli set di dati è possibile utilizzare algoritmi diversi per ottenere prestazioni ottimali. QuickSort brilla quando il set di dati cresce.

Esistono approcci diversi. È possibile utilizzare le strutture dati in cui si ordina al momento dell'inserimento e ci sono casi in cui si ordina il set di dati completo. Hai solo bisogno di trovare il tuo algoritmo ottimale.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top