Ho un'implementazione Quicksort banale che va sotto:Che magia usa `std :: sort` internamente che lo rende molto più veloce?
template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end)
{
if (begin != end)
{
const auto pivot = *(begin + distance(begin, end)/2);
const IteratorType sep = std::partition(begin, end, [pivot](typename IteratorType::value_type v){ return (v < pivot); });
if (sep != begin)
{
quicksort(begin, sep);
}
if (sep != end)
{
quicksort(sep + 1, end);
}
}
}
test su un array di elementi 1000000 dura circa per sempre (6300 ms) prima volte di morire di ricorsione, mentre std::sort
prende come 30 ms.
Sicuramente non mi aspetto che la mia pessima implementazione sia veloce quanto std::sort
ma come può esserci una differenza così grande?
Capisco std::sort
utilizza qualcosa di più complicato di un semplice quicksort (credo sia un introsortale) che impedisce di andare troppo lontano nel livello di ricorsione e roba del genere. Ma ancora, c'è qualcosa di ovvio che mi manca che potrebbe spiegare una differenza così grande?
Variare la dimensione dello scam mostra che il fattore di differenza non è costante, in realtà sembra crescere come n²
.
L'implementazione per libstdC++ inizia nella riga 5207 di [std_algo.h] (http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l05207). –
@bamboon: In realtà ho letto questa domanda (e le sue risposte). Non sono sicuro che sia esattamente simile. La mia preoccupazione principale riguarda la spiegazione delle differenze a livello di implementazione piuttosto che a livello funzionale. – ereOn
Bene, avete un'implementazione quicksort standard piuttosto che ha anche il runtime di caso peggiore O (n^2) in cui potreste intercettare. Inoltre, la domanda potrebbe essere più adatta per http://codereview.stackexchange.com/. – inf