2015-02-16 9 views
5

Sto usando nth_element per ottenere un valore (circa corretto) per un percentile di un vettore, in questo modo:Perché std :: nth_element restituisce vettori ordinati per vettori di input con N <33 elementi?

double percentile(std::vector<double> &vectorIn, double percent) 
{ 
    std::nth_element(vectorIn.begin(), vectorIn.begin() + (percent*vectorIn.size())/100, vectorIn.end()); 

    return vectorIn[(percent*vectorIn.size())/100]; 
} 

ho notato che per lunghezze Vectorin fino a 32 elementi, il vettore viene completamente allineati. A partire da 33 elementi non viene mai ordinato (come previsto).

Non sono sicuro se questo è importante ma la funzione è in un "codice Mat ++ (C++ Matlab-)" compilato tramite Matlab utilizzando "Microsoft Windows SDK 7.1 (C++)".

EDIT:

Vedere anche i sequenti istogramma delle lunghezze dei blocchi più lunga filtrate in vettori 1E5 passati alla funzione (vettori conteneva elementi casuali 1E4 e percentile casuale è stato calcolato). Notare il picco a valori molto piccoli.

Histogram of lengths of longes sorted blocks

+2

La funzione fa una sorta parziale, al fine di restituire il valore richiesto . Quanto di un ordinamento parziale lo fa fino all'implementazione. –

+0

No, non correlato a Mex, ma bella domanda. – chappjc

+0

Il picco sul lato sinistro della trama assomiglia molto all'istogramma della lunghezza della sottosequenza consecutiva più lunga in un vettore casuale. Ciò potrebbe corrispondere alla piccola frazione di valori percentuali scelti casualmente così vicini a una fine del vettore che la sottosequenza più lunga si trova nella parte del vettore mai toccata da nth_vector. Ma quella è solo una congettura. – rici

risposta

4

Questo può variare da implementazione standard per implementazione della libreria standard (e può dipendere da diversi fattori), ma in termini generali:

  • std :: nth_element è consentito di riorganizzare la contenitore di input come ritiene opportuno, a condizione che nth_element sia in posizione n e che il contenitore sia partizionato in posizione n.

  • Per i contenitori di piccole dimensioni, è in genere più veloce eseguire un ordinamento a inserimento completo rispetto a un quickselect, anche se non è scalabile.

Poiché gli autori della libreria standard di solito optare per la soluzione più veloce, la maggior parte delle implementazioni nth_element (e, per questo, ordinare implementazioni) utilizzano algoritmi personalizzati per piccoli ingressi (o per piccoli segmenti nella parte inferiore della ricorsione) , che può ordinare il contenitore in modo più aggressivo di quanto sembri necessario. Per i vettori di valori scalari, l'ordinamento di inserimento è estremamente veloce, poiché sfrutta al massimo la cache. Con le estensioni di streaming, è possibile accelerarlo ulteriormente eseguendo confronti paralleli.

Tra l'altro, è possibile salvare una piccola quantità di calcoli da solo calcolando l'iteratore soglia di una volta, che potrebbe essere più leggibile:

double percentile(std::vector<double> &vectorIn, double percent) 
{ 
    auto nth = vectorIn.begin() + (percent*vectorIn.size())/100; 
    std::nth_element(vectorIn.begin(), nth, vectorIn.end()); 
    return *nth; 
} 
+0

non può ancora votare, quindi prima di tutto: grazie. hai qualche commento sulla trama che ho aggiunto? –

+0

@stack_horst: bel grafico. Ma ci sono troppe variabili e non conosco i dettagli di Windows std :: implementation. Cerchi esecuzioni ordinate in tutto il vettore o solo fino al punto di partizione? Qual era l'intervallo del percentile casuale?ed è limitato alle percentuali intere? – rici

+0

sto cercando in tutto il vettore. i vettori di input 1e5 erano ciascuno con 1e4 valori doppi distribuiti casualmente tra 0 e 100 e il percentile era double rand tra 0 e 100. –