Comment optimiser quicksort
je suis en train de travailler sur un efficace quicksort algo. Cela fonctionne bien, mais prend beaucoup de temps à exécuter quand le nombre d'éléments est énorme, et certaines sections du tableau sont pré-triées. Je cherchais L'article de Wikipedia sur quicksort, et j'y ai trouvé cette écrit:
pour s'assurer qu'au maximum L'Espace o(log N) est utilisé, recurse d'abord dans la plus petite moitié du tableau, et utilise un appel de queue pour recurse dans l'autre.
utilisez le tri d'insertion, qui a un facteur constant plus petit et est donc plus rapide sur de petits réseaux, pour les invocations sur de tels réseaux plus petits (c.-à-d. lorsque la longueur est inférieure à un seuil t déterminé expérimentalement). Cela peut être mis en œuvre en laissant de tels tableaux non triés et en exécutant un tri d'insertion simple passe à la fin, parce que tri d'insertion traite presque triés tableaux efficacement. Une sorte d'insertion séparée de chaque petit segment au fur et à mesure qu'ils sont identifiés Ajoute les frais généraux de démarrage et d'arrêt de nombreuses petites sortes, mais évite effort inutile de comparer les clés à travers les nombreuses limites de segment, les clés qui seront dans l'ordre en raison du fonctionnement du processus de quicksort. Il améliore également l'utilisation du cache.
je recommence pour les deux partitions. Une idée de comment mettre en œuvre le premier conseil? Ce que l'on entend par recurse d'abord dans la petite moitié du tableau, et d'utiliser une queue appel récursif dans les autres? Et deuxièmement, comment puis-je mettre en œuvre un insertion-sort dans quicksort? Il sera toujours améliorer l'efficacité, ou seulement lorsque certaines sections du tableau sont pré-triées? Si c'est le deuxième cas, alors bien sûr je n'ai aucun moyen de savoir quand cela se produira. Alors Quand dois-je inclure le insertion-sort?
6 réponses
dans Quick-sort, vous choisissez un pivot aléatoire qui délimite le tableau à deux demi, la plupart des chances que l'un peut être plus petit,
par exemple de Tableau de taille 100, pivot délimite le tableau 40 / 60, le 40 est la plus petite taille.
supposons que vous décidez de votre taille de seuil pour utiliser le tri d'insertion à 10, vous devez continuer recursively split the array par pivot, chaque fois que l'une des moitiés devient plus petite ou égale à 10, vous pouvez utiliser le tri d'insertion qui se comporte comme O (n) sur les tableaux de petite taille.
tenir compte du fait que le tri d'insertion se comportera mal si votre tableau est trié à l'envers (dans le pire des cas).
en ce qui concerne le truc de la récursion, vous n'avez besoin que de modifier le cas d'arrêt de la récursion rapide- > Taille du tableau <= 10 arrêt de la récursion et de trier l'ensemble du tableau (qui est beaucoup plus petit dans cette étape de la récursion) en utilisant l'insertion de tri.
par recursion de la queue, ils signifient faire tout ce dont vous avez besoin avec le première moitié, puis invoquer tri d'insertion pour la plus petite moitié comme une dernière méthode, il est utilisé pour économiser de l'espace.
Quick-sort()
choose a pivot
move the smaller elements from left
move the bigger elements from right
quick-sort on the bigger half of the array
if half is less then X
only then do an insertion sort on the other half <- this is a tail recursion insertion sort
else
quick sort on this half also
d'après ce que je vois, la deuxième optimisation suggère de ne pas utiliser le tri d'insertion pour chaque pas de récursion, mais rappelez-vous les index pour lesquels la contrainte est faite, puis d'invoquer le tri d'insertion dans un lot concaténant les éléments à partir de toutes les tranches, ce qui assurera d'améliorer l'utilisation du cache , mais est un peu plus difficile à implémenter,
il y a plusieurs façons de rendre le quicksort standard plus efficace. Pour mettre en œuvre la première astuce de votre post, vous devriez écrire quelque chose comme:
void quicksort(int * tab, int l, int r)
{
int q;
while(l < r)
{
q = partition(tab, l, r);
if(q - l < r - q) //recurse into the smaller half
{
quicksort(tab, l, q - 1);
l = q + 1;
} else
{
quicksort(tab, q + 1, r);
r = q - 1;
}
}
}
j'Espère que c'est assez clair. Prochaine étape serait de mettre en place votre propre pile (ou d'utiliser certains de la langue que vous utilisez) au lieu d'utiliser les appels récursifs. Exemple (pseudo) code:
void quicksort2(int * tab, int l, int r)
{
int le, ri, q;
init stack;
push(l, r, stack);
while(!empty(stack))
{
//take the top pair of values from the stack and set them to le and ri
pop(le, ri, stack);
if(le >= ri)
continue;
q = partition(tab, le, ri);
if(q - le < ri - q) //smaller half goes first
{
push(le, q - 1, stack);
push(q + 1, ri, stack);
} else
{
push(q + 1, ri, stack);
push(le, q - 1, stack);
}
}
delete stack;
}
alors vous pouvez procéder à la mise en œuvre de l'autre conseil de votre poteau. Pour ce faire, vous devrait mettre une constante arbitraire, appelons-la CUT_OFF, à environ 20. Cela indiquera à votre algorithme quand il doit passer à l'insertion tri. Il devrait être assez facile (une question d'ajouter un IF-statement) de modifier l'exemple précédent de sorte qu'il passe à l'insertion trier après qu'il a atteint un point de coupure donc je vous laisse à cela.
Toutefois, si vos données sont déjà pré-triés, vous pourriez envisager d'utiliser un autre algorithme complètement. De mon expérience, série naturelle de fusion tri implémenté sur une liste liée est un très bon choix, si vos données sont pré-triées.
j'ai écrit il y a quelque temps un algorithme basé sur quicksort que vous pouvez trouver là (en fait c'est un algorithme de sélection, mais peut être utilisé un algorithme de tri aussi):
leçons que j'ai tirées de cette expérience sont les suivants:
- ajustez soigneusement la boucle de partition de votre algorithme. C'est souvent sous-estimé, mais vous obtenez une augmentation significative de la performance si vous prenez soin d'écrire des boucles que le compilateur/CPU sera en mesure de pipeline logiciel. Cela seul a conduit à une victoire d'environ 50% dans CPU cyles.
- le codage à la main de petites sortes vous donne un gain de performance majeur. Lorsque le nombre d'éléments à trier dans une partition est inférieur à 8, ne vous donnez pas la peine d'essayer de revenir en arrière, mais plutôt d'implémenter un tri codé dur en utilisant juste des ifs et des swaps (jetez un coup d'oeil à la fonction fast_small_sort dans ce code). Cela peut conduire à une victoire d'environ 50% dans les cycles CPU donnant au quicksort la même performance pratique qu'un "sort de fusion"bien écrit.
- passer du temps à choisir une meilleure valeur de pivot lorsqu'un" mauvais " choix de pivot est détecté. Ma mise en œuvre commence par l'utilisation d'un algorithme "médian de médiane" pour la sélection de pivot chaque fois qu'une sélection de pivot conduit à un côté étant en dessous de 16% des éléments restants à trier. Ceci est un stratégie d'atténuation pour le pire rendement rapide, et aider à s'assurer que dans la pratique la limite supérieure est aussi O(N*log(n)) au lieu de O(N^2).
- Optimiser pour les tableaux avec beaucoup de valeurs égales (si nécessaire). Si les tableaux à trier ont beaucoup de valeurs égales, cela vaut la peine de les optimiser car cela conduira à une mauvaise sélection des pivots. Dans mon code je le fais en comptant tous les tableau entrées sont égales à la valeur pivot. Cela me permet de traiter le pivot et toutes les valeurs égales dans le tableau d'une manière plus rapide, et ne dégrade pas la performance quand il n'est pas applicable. il s'agit d'une autre stratégie d'atténuation pour la performance du pire cas, elle aide à réduire l'utilisation de la pile du pire cas en réduisant le niveau de récursion max d'une manière drastique.
j'espère que ça aidera, Laurent.
vous pouvez jeter un oeil à TimSort, qui pour des données non complètement aléatoires exécute mieux que quicksort (ils ont la même complexité asymptotique, mais TimSort a des constantes plus faibles)
j'ai récemment trouvé cette optimisation. Il fonctionne plus vite que std:: sort. Il utilise le tri de sélection sur les petits tableaux et la médiane-de-3 comme élément de partitionnement.
Voici mon implémentation C++:
const int CUTOFF = 8;
template<typename T>
bool less (T &v, T &w)
{
return (v < w);
}
template<typename T>
bool eq (T &v, T &w)
{
return w == v;
}
template <typename T>
void swap (T *a, T *b)
{
T t = *a;
*a = *b;
*b = t;
}
template<typename T>
void insertionSort (vector<T>& input, int lo, int hi)
{
for (int i = lo; i <= hi; ++i)
{
for (int j = i; j > lo && less(input[j], input[j-1]); --j)
{
swap(&input[j], &input[j-1]);
}
}
}
template<typename T>
int median3 (vector<T>& input, int indI, int indJ, int indK)
{
return (less(input[indI], input[indJ]) ?
(less(input[indJ], input[indK]) ? indJ : less(input[indI], input[indK]) ? indK : indI) :
(less(input[indK], input[indJ]) ? indJ : less(input[indK], input[indI]) ? indK : indI));
}
template <typename T>
void sort(vector<T>& input, int lo, int hi)
{
int lenN = hi - lo + 1;
// cutoff to insertion sort
if (lenN <= CUTOFF)
{
insertionSort(input, lo, hi);
return;
}
// use median-of-3 as partitioning element
else if (lenN <= 40)
{
int median = median3(input, lo, lo + lenN / 2, hi);
swap(&input[median], &input[lo]);
}
// use Tukey ninther as partitioning element
else
{
int eps = lenN / 8;
int mid = lo + lenN / 2;
int mFirst = median3(input, lo, lo + eps, lo + eps + eps);
int mMid = median3(input, mid - eps, mid, mid + eps);
int mLast = median3(input, hi - eps - eps, hi - eps, hi);
int ninther = median3(input, mFirst, mMid, mLast);
swap(&input[ninther], &input[lo]);
}
// Bentley-McIlroy 3-way partitioning
int iterI = lo, iterJ = hi + 1;
int iterP = lo, iterQ = hi + 1;
for (;; )
{
T v = input[lo];
while (less(input[++iterI], v))
{
if (iterI == hi)
break;
}
while (less(v, input[--iterJ]))
{
if (iterJ == lo)
break;
}
if (iterI >= iterJ)
break;
swap(&input[iterI], &input[iterJ]);
if (eq(input[iterI], v))
swap(&input[++iterP], &input[iterI]);
if (eq(input[iterJ], v))
swap(&input[--iterQ], &input[iterJ]);
}
swap(&input[lo], &input[iterJ]);
iterI = iterJ + 1;
iterJ = iterJ - 1;
for (int k = lo + 1; k <= iterP; ++k)
{
swap(&input[k], &input[iterJ--]);
}
for (int k = hi ; k >= iterQ; --k)
{
swap(&input[k], &input[iterI++]);
}
sort(input, lo, iterJ);
sort(input, iterI, hi);
}
la récursion de la queue consiste à transformer un appel récursif en boucle. Pour QuickSort, il serait quelque chose comme:
QuickSort(SortVar)
Granularity = 10
SortMax = Max(SortVar)
/* Put an element after the last with a higher key than all other elements
to avoid that the inner loop goes on forever */
SetMaxKey(SortVar, SortMax+1)
/* Push the whole interval to sort on stack */
Push 1 SortMax
while StackSize() > 0
/* Pop an interval to sort from stack */
Pop SortFrom SortTo
/* Tail recursion loop */
while SortTo - SortFrom >= Granularity
/* Find the pivot element using median of 3 */
Pivot = Median(SortVar, SortFrom, (SortFrom + SortTo) / 2, SortTo)
/* Put the pivot element in front */
if Pivot > SortFrom then Swap(SortVar, SortFrom, Pivot)
/* Place elements <=Key to the left and elements >Key to the right */
Key = GetKey(SortVar, SortFrom)
i = SortFrom + 1
j = SortTo
while i < j
while GetKey(SortVar, i) <= Key; i = i + 1; end
while GetKey(SortVar, j) > Key; j = j - 1; end
if i < j then Swap(SortVar, i, j)
end
/* Put the pivot element back */
if GetKey(SortVar, j) < Key then Swap(SortVar, SortFrom, j)
if j - SortFrom < SortTo - j then
/* The left part is smallest - put it on stack */
if j - SortFrom > Granularity then Push SortFrom j-1
/* and do tail recursion on the right part */
SortFrom = j + 1
end
else
/* The right part is smallest - put it on stack */
if SortTo - j > Granularity then Push j+1 SortTo
/* and do tail recursion on the left part */
SortTo = j - 1
end
end
end
/* Run insertionsort on the whole array to sort the small intervals */
InsertionSort(SortVar)
return
en outre, il n'y a aucune raison d'appeler InsertionSort sur les petits intervalles, parce que lorsque QuickSort est terminé le tableau est grossièrement trié, de sorte qu'il n'y a que de petits intervalles à trier. Et c'est le cas parfait pour InsertionSort.
si vous n'avez pas de pile, vous pouvez utiliser la récursion à la place - mais gardez la queue la récursivité:
QuickSort(SortVar, SortFrom, SortTo)
Granularity = 10
/* Tail recursion loop */
while SortTo - SortFrom >= Granularity
/* Find the pivot element using median of 3 */
Pivot = Median(SortVar, SortFrom, (SortFrom + SortTo) / 2, SortTo)
/* Put the pivot element in front */
if Pivot > SortFrom then Swap(SortVar, SortFrom, Pivot)
/* Place elements <=Key to the left and elements >Key to the right */
Key = GetKey(SortVar, SortFrom)
i = SortFrom + 1
j = SortTo
while i < j
while GetKey(SortVar, i) <= Key; i = i + 1; end
while GetKey(SortVar, j) > Key; j = j - 1; end
if i < j then Swap(SortVar, i, j)
end
/* Put the pivot element back */
if GetKey(j) < Key then Swap(SortVar, SortFrom, j)
if j - SortFrom < SortTo - j then
/* The left part is smallest - recursive call */
if j - SortFrom > Granularity then QuickSort(SortVar, SortFrom, j-1)
/* and do tail recursion on the right part */
SortFrom = j + 1
end
else
/* The right part is smallest - recursive call */
if SortTo - j > Granularity then QuickSort(SortVar, j+1, SortTo)
/* and do tail recursion on the left part */
SortTo = j - 1
end
end
/* Run insertionsort on the whole array to sort the small intervals */
InsertionSort(SortVar)
return