Est-ce que le quicksort avec la médiane de trois aléatoire fait sensiblement mieux que le quicksort aléatoire ?

Question

Je répondais juste à une question sur les différentes approches pour choisir la partition dans une implémentation quicksort et j'ai trouvé une question à laquelle je ne sais honnêtement pas comment répondre. C'est un peu lourd en maths, et ce n'est peut-être pas le bon site pour poser cette question, donc si elle doit être déplacée, faites-le moi savoir et je serai heureux de la transférer ailleurs.

Il est bien connu qu'une implémentation de quicksort qui choisit ses pivots uniformément au hasard finira par s'exécuter en temps O(n lg n) (il existe une belle preuve de cela sur Wikipédia ). Cependant, en raison du coût de la génération de nombres aléatoires, de nombreuses implémentations de quicksort ne choisissent pas les pivots de manière aléatoire, mais s'appuient plutôt sur une approche de type "médiane des trois" dans laquelle trois éléments sont choisis de manière déterministe et parmi lesquels la médiane est choisie comme pivot. Cette approche est connue pour dégénérer en O(n 2 ) dans le pire des cas (voir ce grand papier sur la façon de générer ces entrées dans le pire des cas, par exemple).

Maintenant, supposons que nous moissonneuse-batteuse ces deux approches en choisissant trois éléments aléatoires dans la séquence et en utilisant leur médiane comme choix du pivot. Je sais que cela garantit également un temps d'exécution moyen de O(n lg n) en utilisant une preuve légèrement différente de celle pour le quicksort aléatoire régulier. Cependant, je n'ai aucune idée de ce qu'est le facteur constant devant le terme n lg n dans cette implémentation particulière du quicksort. Pour le tri rapide aléatoire régulier, Wikipedia indique que le temps d'exécution réel du tri rapide aléatoire nécessite au maximum 1,39 n lg n comparaisons (en utilisant lg comme logarithme binaire).

Ma question est la suivante : quelqu'un connaît-il un moyen de dériver le facteur constant pour le nombre de comparaisons effectuées en utilisant un quicksort aléatoire "median-of-three" ? ? Si nous allons encore plus généralement, existe-t-il une expression pour le facteur constant sur quicksort en utilisant une approche aléatoire de la médiane de k ? Je suis curieux parce que je pense qu'il serait fascinant de voir s'il y a un "sweet spot" de cette approche qui fait moins de comparaisons que d'autres implémentations aléatoires de quicksort. Je veux dire, ne serait-il pas cool de pouvoir dire que le quicksort aléatoire avec un choix de pivot médian-de-six aléatoire fait le moins de comparaisons ? Ou être capable de dire de manière concluante que vous devriez juste choisir un élément pivot au hasard ?

Answer 1

Voici une dérivation heuristique de la constante. Je pense qu'elle peut être rendue rigoureuse, avec beaucoup plus d'efforts.

Soit P une variable aléatoire continue dont les valeurs sont comprises dans [0, 1]. Intuitivement, P est la fraction des valeurs inférieures au pivot. Nous cherchons à trouver la constante c telle que

c n lg n = E [n + c P n lg (P n) + c (1 - P) n lg ((1 - P) n)].

Un peu d'algèbre plus tard, nous avons

c = 1/ E [-P lg P - (1 - P) lg (1 - P))].

En d'autres termes, c est l'inverse de l'entropie attendue de la distribution de Bernoulli de moyenne P. Intuitivement, pour chaque élément, nous devons le comparer aux pivots d'une manière qui donne environ lg n bits d'information.

Lorsque P est uniforme, la fdp de P est 1. La constante est

In[1]:= -1/NIntegrate[x Log[2, x] + (1 - x) Log[2, 1 - x], {x, 0, 1}]

Out[1]= 1.38629

Lorsque le pivot est une médiane de 3, la fdp de P est 6 x (1 - x). La constante est

In[2]:= -1/NIntegrate[6 x (1 - x) (x Log[2, x] + (1 - x) Log[2, 1 - x]), {x, 0, 1}]

Out[2]= 1.18825

Answer 2

La constante pour le quicksort aléatoire habituel est facile à calculer car la probabilité que deux éléments distants de k positions soient comparés est exactement 2/(k+1) : la probabilité que l'un de ces deux éléments soit choisi comme pivot avant n'importe lequel des k-1 éléments entre eux. Malheureusement, rien d'aussi astucieux ne s'applique à votre algorithme.

J'hésite à répondre à votre question en gras parce que je puede répondre à votre question "sous-jacente" : asymptotiquement parlant, il n'y a pas de "point idéal". Le coût total ajouté du calcul des médianes de k éléments, même O(n 1 - ε ), est linéaire, et la constante pour le terme n log n diminue lorsque le tableau est divisé de manière plus égale. Le piège est bien sûr les constantes sur le terme linéaire qui sont spectaculairement impraticables, soulignant l'un des inconvénients de l'analyse asymptotique.

---

Sur la base de mes commentaires ci-dessous, je suppose que k = O(n α ) pour 0 < α < 1 est le "sweet spot".

Answer 3

Si l'état initial de l'ensemble est ordonné de manière aléatoire, vous obtiendrez exactement le même facteur constant pour le choix aléatoire de trois éléments pour calculer la médiane que pour le choix déterministe de trois éléments.

Le motif du tirage au sort serait que la méthode déterministe donnerait un résultat plus mauvais que la moyenne. Si la méthode déterministe donne une bonne médiane, vous ne pouvez pas l'améliorer en choisissant des éléments au hasard.

Ainsi, la méthode qui donne le meilleur résultat dépend des données d'entrée, elle ne peut pas être déterminée pour chaque ensemble possible.

Le seul moyen sûr de réduire le facteur constant est d'augmenter le nombre d'éléments que vous utilisez pour calculer la médiane, mais à un moment donné, le calcul de la médiane sera plus coûteux que ce que vous gagnerez en obtenant une meilleure valeur médiane.

Answer 4

Oui, c'est vrai. Bentley et McIlroy, auteurs de l'ouvrage C de la bibliothèque standard qsort fonction ont écrit dans leur article, Ingénierie d'une fonction de tri les numéros suivants :

• 1.386 n lg n comparaisons moyennes en utilisant le premier, le milieu ou un pivot aléatoire
• 1,188 n lg n comparaisons moyennes utilisant une médiane de 3 pivots
• 1.094 n lg n comparaisons moyennes utilisant une médiane de 3 médianes pivot

Selon le document ci-dessus :

Notre code final choisit donc le m la médiane des premier, moyen et dernier éléments d'un tableau de taille moyenne. et la pseudo-médiane de neuf éléments régulièrement espacés d'un grand tableau. tableau.

Answer 5

Juste une idée : Si vous utilisez le médiane des trois et que vous trouvez qu'elle est meilleure, pourquoi ne pas utiliser une médiane des cinq o médiane des onze approche ? Et pendant que vous y êtes, peut-être que l'on peut penser à une médiane de n l'optimisation... hmmm... Ok, c'est évidemment une mauvaise idée (puisque vous devriez trier votre séquence pour cela...).

Fondamentalement, pour choisir votre élément pivot comme le médiane de m éléments, vous triez ces m éléments, n'est-ce pas ? Par conséquent, je suppose simplement que l'une des constantes que vous recherchez est "2" : En triant d'abord 3 éléments pour choisir votre pivot, vous exécutez combien de comparaisons supplémentaires ? Disons que c'est 2. Vous faites cela à l'intérieur du quicksort, encore et encore. Une conclusion de base serait que le médiane-de-3 est donc deux fois plus lent que le quicksort aléatoire simple.

Mais qu'est-ce qui marche pour vous ici ? Que vous obtenez une meilleure répartition des dispositifs et des conquêtes, et que vous êtes mieux protégé contre le cas dégénéré (un peu).

Donc, retour à ma fameuse question du début : Pourquoi ne pas choisir l'élément pivot dans un médiane de m m étant 5, 7, n/3, etc. Il doit y avoir un le point idéal où le tri de la m est pire que le gain obtenu grâce au meilleur comportement de division et de conquête et au tri rapide. Je suppose que ce point idéal est présent très tôt - il faut d'abord lutter contre le facteur constant d'augmentation du nombre d'éléments. 2 comparaisons si vous choisissez médiane-de-3 . Cela vaut la peine d'être expérimenté, je l'admets, mais je ne serais pas trop exigeant quant au résultat :-) Mais si je me trompe, et que le gain est énorme : ne vous arrêtez pas à 3 !