Pourquoi est-quicksort mieux que d'autres algorithmes de tri dans la pratique?

https://cs.stackexchange.com/questions/3

15-10-2019
|

Question

Dans un algorithme standard cours nous a enseigné que quicksort est O $ (n \ log n) $ en moyenne et O $ (n ^ 2) $ dans le pire des cas. En même temps, d'autres algorithmes de tri sont étudiés qui sont O $ (n \ log n) $ dans le pire des cas (comme mergesort et heapsort ), et même le temps linéaire dans le meilleur des cas (comme bubblesort ) mais avec des besoins supplémentaires de la mémoire.

Après un rapide coup d'œil à quelques fois plus en cours d'exécution il est naturel de dire que quicksort ne devrait pas être aussi efficace que d'autres.

En outre, considèrent que les élèves apprennent en cours de programmation de base qui récursion est pas vraiment bon en général, car il pourrait utiliser trop de mémoire, etc. Par conséquent (et même si ce n'est pas un argument réel), cela donne l'idée que quicksort peut-être pas vraiment bon car il est un algorithme récursif.

Pourquoi, alors, ne quicksort d'autres algorithmes de tri surclassent dans la pratique? Est-ce que cela a à voir avec la structure de données réelles ? Est-ce que cela a à voir avec les travaux de mémoire de façon dans les ordinateurs? Je sais que certains souvenirs sont beaucoup plus vite que d'autres, mais je ne sais pas si c'est la vraie raison de cette performance contre-intuitif (par rapport aux estimations théoriques).

Mise à jour 1: une réponse canonique dit que les constantes impliquées dans l'O $ (n \ log n) $ de l'affaire moyenne sont plus petits que les constantes impliquées dans d'autres $ O (n \ log n) $ algorithmes. Cependant, je dois encore voir une justification de ce fait, avec des calculs précis au lieu d'idées intuitives uniquement.

Dans tous les cas, il semble que la vraie différence se produit, car certaines réponses suggèrent, au niveau de la mémoire, où les mises en œuvre tirer parti de la structure interne des ordinateurs, en utilisant, par exemple, que la mémoire cache est plus rapide que la RAM. La discussion est déjà intéressant, mais je voudrais encore voir plus de détails en ce qui concerne la gestion de mémoire, car il semble que la réponse doit faire.

Mise à jour 2: Il y a plusieurs pages Web qui offrent une comparaison des algorithmes de tri, certains plus fantaisistes que d'autres (notamment sorting-algorithms.com ). Que nous diffusons une belle aide visuelle, cette approche ne répond pas à ma question.

La solution

Réponse courte

L'argument de l'efficacité du cache a déjà été expliqué en détail. En outre, il y a un argument intrinsèque, pourquoi Quicksort est rapide. Si elle est appliquée comme avec deux « pointeurs de passage », par exemple , les boucles internes ont un corps très petit. Comme cela est le code exécuté le plus souvent, ce paie.

Réponse longue

Tout d'abord,

Le Cas moyenne n'existe pas!

Comme meilleur et le pire des cas sont extrêmes qui se produisent rarement souvent dans la pratique, l'analyse moyenne de cas est fait. Mais toute analyse de cas moyen suppose une distribution des intrants ! Pour le tri, le choix typique est le modèle de permutation aléatoire (tacitement sur Wikipedia supposé).

Pourquoi $ O $ -Notation?

Rejeter constantes dans l'analyse des algorithmes est fait pour une raison principale: Si je suis intéressé par exacte fois en cours d'exécution, J'ai besoin des coûts (relatifs) de toutes les parties concernées les opérations de base (même en ignorant encore des problèmes de mise en cache, dans pipelining processeurs modernes ...). Analyse mathématique peut de nombre à quelle fréquence chaque instruction est exécutée, mais les temps en cours d'exécution d'instructions simples dépendent des détails du processeur, par exemple si une multiplication d'entiers de 32 bits prend autant de temps que l'addition.

Il y a deux façons de sortir:

Fixons modèle de machine.

Ceci est fait dans Don Knuth « The Art Programmation de l'ordinateur » pour un artificiel « ordinateur typique » inventé par l'auteur. Dans le volume 3, vous trouverez des résultats précis moyenne cas pour de nombreux algorithmes de tri, par exemple
- Quicksort: 11,667 $ (n + 1) \ ln (n) -1.74n-18,74 $
- Mergesort: 12,5 $ n \ ln (n) $
- Heapsort: 16 $ n \ ln (n) + 0,01 N $
- InsertionSort: 2.25n $ ^ 2 + 7.75n-3LN (n) $
  ^{[ ]}
Ces résultats indiquent que Quicksort est le plus rapide. Mais, il est prouvé que la machine artificielle de Knuth, cela ne signifie pas nécessairement quelque chose pour dire que votre PC x86. Notez également que les algorithmes se rapportent différemment pour les petites entrées:

^{[ ]}
Analyser abstraites les opérations de base .

À titre de comparaison en fonction de tri, cela est généralement swaps et comparaisons clés . Dans les livres de Robert Sedgewick, par exemple « algorithmes » , cette approche est poursuivie. Vous y trouvez
- Quicksort: $ 2n \ ln (n) $ comparaisons et $ \ frac13n \ ln (n) $ swaps en moyenne
- Mergesort: 1.44n $ \ ln (n) $ comparaisons, mais, jusqu'à 8.66n $ \ ln (n) $ des accès de tableau (mergesort n'est pas swap basée, donc nous ne pouvons compter que)
- InsertionSort:. $ \ Frac14n ^ 2 comparaisons $ et $ \ frac14n ^ 2 swaps de $ en moyenne
Comme vous le voyez, cela ne permet pas facilement des comparaisons d'algorithmes que l'analyse d'exécution exacte, mais les résultats sont indépendants les détails de la machine.

Autres distributions d'entrée

Comme indiqué plus haut, les cas sont toujours en moyenne par rapport à une distribution d'entrée, donc on pourrait considérer les autres que les permutations aléatoires. Par exemple. la recherche a été fait pour Quicksort avec des éléments égaux et il y a bel article sur la fonction de tri standard Java

Autres conseils

Il y a plusieurs points qui peuvent être faites en ce qui concerne cette question.

Quicksort est généralement rapide

Bien que Quicksort a pire cas $ O (n ^ 2) $ comportement, il est généralement rapide: en supposant la sélection de pivot aléatoire, il y a une très grande chance que nous sélectionnons un nombre qui sépare l'entrée en deux sous-ensembles de la même taille, ce qui est exactement ce que nous voulons avoir.

En particulier, même si nous choisissons un pivot qui crée un 10% -90% tous les 10 divisions (ce qui est une scission meh), et un élément 1 - $ n-1 $ élément fendu autrement (ce qui est le pire Split, vous pouvez obtenir), notre temps est en cours d'exécution encore O $ (n \ log n) $ (notez que cela ferait exploser les constantes à un point ce genre de fusion est probablement plus rapide si).

Quicksort est généralement plus rapide que la plupart des sortes

Quicksort est généralement plus rapide que les sortes qui sont plus lents que $ O (n \ log n) $ (par exemple, trier Insertion avec son O $ (n ^ 2) $ durée), tout simplement parce que pour les grands $ n $ leur fonctionnement fois exploser.

Une bonne raison pour laquelle Quicksort est si rapide dans la pratique par rapport à la plupart des autres $ O (n \ log n) $ algorithmes tels que Heapsort, est parce qu'il est relativement cache efficace. Son temps de fonctionnement est en fait $ O (\ frac {n} {B} \ log (\ frac {n} {B})) $, où $ B $ est la taille du bloc. Heapsort, d'autre part, n'a pas une telle accélération. Ce n'est pas du tout accès à la mémoire cache efficacement

La raison de cette efficacité du cache est qu'il balaye linéairement l'entrée et partitions linéairement l'entrée. Cela nous permet de tirer le meilleur parti de chaque chargement de cache que nous faisons comme nous le lisons chaque numéro nous charge dans le cache avant d'échanger ce cache pour un autre. En particulier, l'algorithme est cache-inconscient, ce qui donne de bonnes performances du cache pour tous les niveaux de cache, ce qui est une autre victoire.

L'efficacité du cache pourrait encore être améliorée à $ O (\ frac {n} {B} \ log _ {\ frac {M} {B}} (\ frac {n} {B})) $, où $ M $ est la taille de la mémoire principale, si l'on utilise k $ $ -way Quicksort. Notez que Mergesort a également le même cache-efficacité que Quicksort, et sa version k-way en fait a une meilleure performance (par des facteurs constants de plus faibles) si la mémoire est une contrainte sévère. Cela donne lieu au point suivant:. Nous devons comparer Quicksort à Mergesort sur d'autres facteurs

Quicksort est généralement plus rapide que Mergesort

Cette comparaison est tout à fait sur les facteurs constants (si l'on considère le cas typique). En particulier, le choix est entre un choix de suboptimale du pivot pour Quicksort par rapport à la copie de l'entrée entière pour Mergesort (ou la complexité de l'algorithme nécessaire pour éviter cette copie). Il se trouve que le premier est plus efficace. Il n'y a pas la théorie derrière tout cela, il se trouve être plus rapide

Notez que Quicksort effectuerez des appels plus récursives, mais l'allocation d'espace de pile est pas cher (presque libre en fait, aussi longtemps que vous ne soufflez pas la pile) et vous le réutiliser. L'attribution d'un bloc géant sur le tas (ou votre disque dur, si est $ n $ vraiment grand) est un peu plus cher, mais les deux sont $ O (\ log n) $ frais généraux pâle par rapport à la O $ (n) $ travail mentionné ci-dessus.

Enfin, notez que Quicksort est légèrement sensible à l'entrée qui se trouve être dans le bon ordre, dans ce cas, il peut sauter des swaps. Mergesort n'a pas de ces optimisations, ce qui rend également Quicksort un peu plus rapide par rapport à mergesort.

Utilisez le genre qui convient à vos besoins

En conclusion: aucun algorithme de tri est toujours optimale. Choisir selon vos besoins. Si vous avez besoin d'un algorithme qui est le plus rapide pour la plupart des cas, et ne vous dérange pas, il pourrait finir par être un peu lent dans de rares cas, et vous n'avez pas besoin stable sorte, utilisez Quicksort. Dans le cas contraire, utilisez l'algorithme qui convient le mieux à vos besoins.

Dans l'un des didacticiels de programmation à mon université, nous avons demandé aux étudiants de comparer les performances de tri rapide, mergesort, sorte d'insertion par rapport intégré list.sort Python (appelé Timsort ). Les résultats expérimentaux m'a surpris profondément depuis le haut-list.sort effectué beaucoup mieux que d'autres algorithmes de tri, même avec les instances qui ont fait facilement, quicksort accident de mergesort. Il est donc prématuré de conclure que la mise en œuvre habituelle quicksort est le meilleur dans la pratique. Mais je suis sûr qu'il ya beaucoup mieux mise en œuvre de quicksort, ou une version hybride de celui-ci sur le marché.

Ceci est un article de blog sympa David R. MacIver expliquant Timsort comme une forme de mergesort adaptatif.

Je pense que l'une des principales raisons pour lesquelles QuickSort est si rapide par rapport à d'autres algorithmes de tri est parce qu'il est convivial cache. Lorsque QS traite un segment d'un réseau, il accède à des éléments au début et à la fin du segment, et se dirige vers le centre du segment.

Alors, quand vous commencez, vous accédez au premier élément du tableau et un morceau de mémoire ( « emplacement ») est chargé dans le cache. Et lorsque vous essayez d'accéder au deuxième élément, il est (le plus probable) déjà dans le cache, il est donc très rapide.

D'autres algorithmes comme heapsort ne fonctionnent pas comme ça, ils sautent dans le tableau beaucoup, ce qui les rend plus lent.

D'autres ont déjà dit que la asymptotique moyenne exécution de Quicksort est meilleur (la constante) que celle des autres algorithmes de tri (dans certains contextes).

Qu'est-ce que cela veut dire? Supposons que toute permutation est choisi au hasard (en supposant une distribution uniforme). Dans ce cas, les méthodes de sélection de pivot typique fournissent des pivots dans l'attente diviser la liste / tableau à peu près la moitié; c'est ce qui nous amène jusqu'à $ \ cal {O} (n \ log n) $. Mais, en outre, fusion solutions partielles obtenues par récursion ne prend que constante de temps (par opposition au temps linéaire en cas de Mergesort). Bien sûr, séparant l'entrée en deux listes selon le pivot est dans le temps linéaire, mais il faut souvent quelques échanges réels.

Notez qu'il existe de nombreuses variantes de Quicksort (voir par exemple la thèse de Sedgewick). Ils se comportent différemment sur les différentes distributions d'entrée (uniforme, presque triée, presque triés à l'inverse, beaucoup de doublons, ...), et d'autres algorithmes pourraient être mieux pour certains.

Une autre valeur de fait noter que Quicksort est lent sur les entrées courtes par rapport aux algorithmes Simper avec moins de frais généraux. Par conséquent, les bonnes bibliothèques ne sont pas récursifs vers le bas pour les listes d'une longueur mais utilisera (par exemple) tri par insertion si la longueur d'entrée est inférieure à un certain $ k \ environ 10 $.

En comparaison à d'autres algorithmes de tri en fonction comparaison avec O $ (n \ logn) $ complexité du temps, est tri rapide souvent considéré comme mieux que d'autres algorithmes comme fusion tri, car il est un algorithme de tri en place. En d'autres termes, on n'a pas besoin de mémoire (beaucoup plus) pour stocker les membres du tableau.

ps: pour être précis, être mieux que d'autres algorithmes dépend la tâche. Pour certaines tâches, il pourrait être préférable d'utiliser d'autres algorithmes de tri.

Voir aussi:

Même si quicksort a un pire moment de l'exécution de cas de $ \ theta (n ^ 2) $, quicksort est considéré comme le meilleur de tri, car il est très efficace sur la moyenne: son temps de fonctionnement prévu est $ \ theta (n \ log n) $ où les constantes sont très faibles par rapport à d'autres algorithmes de tri. Ceci est la raison principale pour l'utilisation de tri rapide sur d'autres algorithmes de tri.

La deuxième raison est qu'il effectue le tri in-place et fonctionne très bien avec des environnements de mémoire virtuelle.

Mise à jour: : (Après son Janoma et les commentaires de Svick)

Pour illustrer ce mieux de me laisser donner un exemple en utilisant le tri par fusion (car Merge est en quelque sorte l'algorithme de tri suivant largement adopté après tri rapide, je pense) et vous dire où les constantes supplémentaires viennent de (au meilleur de ma connaissance et pourquoi je pense que rapide est meilleur genre):

Considérez le seqence suivant:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Si vous regardez bien soin comment la dernière étape se passe, en premier lieu 12 est comparé à 8 et 8 est plus petit donc il va d'abord. Maintenant 12 est de nouveau par rapport à 21 et 12 va suivant, et ainsi de suite et ainsi de suite. Si vous prenez la fusion finale à savoir 4 éléments avec 4 autres éléments, il engage beaucoup de comparaisons supplémentaires comme des constantes qui ne supporte pas lors de Tri rapide. Ceci est la raison pour laquelle tri rapide est préférable.

Mon expérience de travail avec les données du monde réel est que quicksort est un mauvais choix . Quicksort fonctionne bien avec des données aléatoires, mais les données du monde réel est le plus souvent pas aléatoire.

En 2008 j'ai suivi un bug logiciel suspendu jusqu'à l'utilisation de quicksort. Un peu plus tard, j'ai écrit implentations simples de tri par insertion, quicksort, trier tas et le tri par fusion et testé ces derniers. Mon tri par fusion a surclassé tous les autres tout en travaillant sur de grands ensembles de données.

Depuis lors, la fusion est en quelque sorte mon algorithme de tri de choix. Il est élégant. Il est simple à mettre en œuvre. Il est une sorte de stable. Il n'a pas dégénéré à un comportement quadratique comme quicksort fait. Je passe à l'insertion tri pour trier les petits tableaux.

A plusieurs reprises, je l'ai trouvé ma pensée auto qu'une mise en œuvre donnée fonctionne étonnamment bien pour quicksort seulement pour découvrir qu'il est en fait pas quicksort. Parfois, la mise en œuvre passe entre quicksort et un autre algorithme et parfois il ne se sert pas du tout quicksort. À titre d'exemple, les fonctions de qsort de glibc () fait usage tri par fusion. Seulement si l'allocation de l'espace de travail ne fait retomber à en place quicksort qui appelle un commentaire de code "l'algorithme plus lent"

Edit: Les langages de programmation tels que Java, Python et Perl utilisent également le tri par fusion, ou plus précisément un dérivé, comme Timsort ou tri par fusion pour les grands ensembles et tri par insertion pour les petits ensembles. (Java utilise également quicksort double pivot qui est plus rapide que quicksort ordinaire.)

1 - rapide est un peu inplace (. N'a pas besoin memmory supplémentaire, autre qu'une quantité constante)

2 -. rapide est un peu plus facile à mettre en œuvre que d'autres algorithmes de tri efficace

3 -. rapide a en quelque sorte plus petits facteurs constants dans le temps, il est en cours d'exécution que d'autres algorithmes de tri efficace

Mise à jour: Pour le tri par fusion, vous devez faire une « fusion », qui a besoin de tableau supplémentaire (s) pour stocker les données avant de fusionner; mais dans une sorte rapide, vous ne le faites pas. Voilà pourquoi tri rapide est en place. Il y a aussi quelques comparaisons supplémentaires effectuées pour la fusion qui augmentent les facteurs constants dans une sorte de fusion.

Dans quelles conditions est un algorithme de tri spécifique en fait le plus rapide d'un?

1) Lorsque mis en œuvre de manière parallèle dans le matériel, at-il besoin d'avoir un temps d'attente relativement bas tout en exigeant que quelques portes que possible? Oui -> utiliser un trieur Bitonic ou Doseur mergesort impair-pair, est temps d'attente $ \ theta (\ log (n) ^ 2) $ et le nombre de comparateurs et multiplexeurs est $ \ theta (n \ cdot \ log (n) ^ 2) $.

2) Combien de valeurs différentes chaque élément peut avoir? Boîtes de conserve toutes les valeurs possibles ont attribué une place unique dans la mémoire ou le cache Oui -> utilisez count genre ou radix sorte, ceux qui ont généralement une durée d'exécution linéaire de $ \ theta (n \ cdot k) $ (chiffre tri) ou $ \ theta (n \ cdot m) $ (tri seau), mais ralentir pour un grand nombre de valeurs différentes, comme $ k = 2 ^ {\ # nombre \ _de \ _Possible \ _values} $ et $ m = \ #maximum \ _length \ _de \ _keys $.

3) Est-ce que la structure de données sous-jacente se composent d'éléments liés? Oui -> AllWays utilisation en place sorte de fusion. Il y a à la fois facile à mettre en œuvre la taille fixe ou adaptatif (aka naturel) bottom-up en place sortes de fusion de différentes arités pour les structures de données liées, et comme ils ont besoin jamais copier l'ensemble des données à chaque étape et ils ne nécessitent récurrences non plus, ils sont plus vite que toute autre sorte de base général, comparision encore plus rapide que tri rapide.

4) Est-ce que le besoin de tri pour être stable? Oui -> utilisation sorte de fusion, soit en place ou non, de taille fixe ou adaptative, en fonction de la structure de données sous-jacente et le type de données à prévoir, même dans les cas où tri rapide serait par ailleurs préféré, comme la stabilisation d'un tri arbitraire algorithme nécessite $ \ theta (n) $ de mémoire supplémentaire dans le pire des cas, composé d'indices originaux, qui doit également être maintenu en phase avec chaque swap qui doit être effectué sur les données d'entrée, de sorte que chaque gain de performance qui pourrait de tri rapide ont plus de fusion est probablement contrecarrée sorte.

5) la taille peut des données sous-jacentes être lié à une taille petite à moyenne? par exemple. Est n <10000 ... 100000000 (selon l'architecture sous-jacente et de la structure de données)? Oui -> utiliser sorte Bitonic ou mergesort Doseur impair-pair. Goto 1)

6) Pouvez-vous épargner un autre $ \ theta (n) $ la mémoire? Oui -> a) Est-ce que les données d'entrée sont constituées de gros morceaux de déjà triés données séquentielles? -> adaptatif d'usage (aka naturel) sorte de fusion ou tim sorte Oui -> b) Est-ce que les données d'entrée sont constituées principalement d'éléments qui sont presque au bon endroit? -> utilisation de tri à bulles ou le tri par insertion. Si vous craignez leur $ \ theta (n ^ 2) $ complexité du temps (ce qui est pathologique pour les données presque Sorted), peut-être envisager de passer à la coquille sorte avec un (presque) séquence asymptotiquement optimale des lacunes, certaines séquences que le rendement $ \ theta ( n \ cdot \ log (n) ^ 2) $ pire moment de l'exécution de cas sont connus, ou peut-être essayer tri peigne. Je ne suis pas sûr que ce soit de tri shell ou tri peigne exécuteraient raisonnablement bien dans la pratique.

Non -> 7) Pouvez-vous épargner un autre $ \ theta (\ log (n)) $ la mémoire? Oui -> a) Est-ce que la structure de données de undelying permettent un accès séquentiel dirigé ou mieux? Oui -> Permet-elle qu'une seule séquence d'accès en lecture / écriture à la fois jusqu'à la fin des données a été atteint (par exemple accès à la bande dirigée)? Oui -> i) fusion utilisation sorte, mais il n'y a aucun moyen évident de faire ce cas en place, il peut exiger $ supplémentaire \ Theta (n) $ la mémoire. Mais si vous avez le temps et les couilles de le faire, il y a un moyen de fusionner 2 tableaux en $ \ theta (n) $ temps en utilisant seulement $ \ theta (\ log (n)) $ l'espace d'une manière stable, selon Donald E. Knuth "L'art de la programmation informatique, Volume 3: tri et de recherche", l'exercice 5.5.3. indique qu'il existe un algorithme par L. Trabb-Pardo qui le fait. Cependant, je doute que ce serait plus vite que la version mergesort naïve ou quicksort de l'affaire ci-dessus. Non, il permet à plusieurs accès simultanés à une séquence de données (par exemple, pas est un lecteur de bande) -> ii) l'utilisation tri rapide, à des fins pratiques Je recommande soit un randomized ou une médiane approximative. Si vous êtes méfiant de $ pathologique \ Theta (n ^ 2) $ cas, pensez à utiliser introsort. Si vous êtes un puriste sur le comportement déterministe, pensez à utiliser la médiane de la médiane algorithme pour sélectionner l'élément pivot, il faut $ \ theta (n) $ temps et sa mise en œuvre naïve nécessite $ \ theta (n) $ espace (parallélisables ), alors qu'il peut être mis en œuvre pour ne nécessitent $ \ theta (\ log (n)) $ espace (non parallélisables). Cependant, la médiane de la médiane algorithme vous donne un quicksort déterministe qui a le pire cas $ \ theta (n \ cdot \ log (n)) $ d'exécution. Non -> vous êtes foutus (désolé, nous avons besoin d'au moins 1 moyen d'accéder à chaque élément de données une fois)

Non -> 8) Pouvez-vous épargner une petite quantité constante de la mémoire? Oui -> Est-ce que la structure de données sous-jacentes permettent un accès aléatoire? Oui -> utilisation heapsort, il a une asymptotique optimale d'exécution de $ \ theta (n \ cdot \ log (n)) $, mais la cohérence du cache morne et ne paralléliser bien. Non -> vous déconné Non -> vous déconné

conseils de mise en œuvre pour le tri rapide:

1) quicksort binaire Naive nécessite $ \ theta (n) $ la mémoire supplémentaire, cependant, il est relativement facile de réduire ce jusqu'à $ \ theta (\ log (n)) $ en réécrivant le dernier appel de récursion dans une boucle . Faire la même chose pour quicksorts k-aire pour k> 2 exige $ \ Theta (n ^ {\ log_k (k-1)}) $ espace (d'après le théorème de maître), de sorte que le tri rapide binaire nécessite le moins de mémoire, mais Je serais ravi d'entendre si quelqu'un sait si quicksort k-aire pour k> 2 est peut-être plus rapide que quicksort binaire sur une configuration du monde réel.

2) bottom-up Il existe, itérative des variantes de tri rapide, mais autant que je sache, ils ont les mêmes limites de l'espace asymptotique et le temps en haut vers le bas ceux, avec les bas côtés supplémentaires d'être difficiles à mettre en œuvre (par exemple, la gestion explicitement queue). Mon expérience est que, pour des raisons pratiques, ce sont jamais à considérer.

conseils de mise en œuvre pour mergesort:

1) bottum-up mergesort est toujours plus rapide que mergesort haut vers le bas, car il ne nécessite pas d'appels récursifs.

2) la mergesort très naïve peut être accéléré à l'aide d'un double tampon, et mettre le tampon au lieu de copier les données de retour de la matrice temporelle après chaque étape.

3) Pour beaucoup de données réelles, mergesort adaptatif est beaucoup plus rapide qu'une mergesort de taille fixe.

4) l'algorithme de fusion peut être facilement parallélisé en divisant les données d'entrée en k parties sensiblement de même taille. Cela nécessite des références k en données, et il est une bonne chose de choisir k tel que tous k (ou c * k pour une petite constante c> = 1) ajustement dans la hiérarchie de mémoire le plus proche (généralement L1 cache de données). Le choix le plus petit à partir d'éléments k la manière naïve (recherche linéaire) prend $ \ theta (k) $ temps, alors que la construction d'un min-tas dans ces éléments k et choisir le plus petit ne nécessite que amorti $ \ theta (\ log ( k)) $ temps (choisir le minimum est de $ \ theta (1) $ bien sûr, mais nous devons faire un peu d'entretien comme un élément est supprimé et remplacé par un autre à chaque étape). La fusion nécessite toujours parallélisée $ \ theta (n) $ mémoire quel que soit k.

D'après ce que je l'ai écrit, il est clair que est quicksort souvent pas l'algorithme le plus rapide, sauf si les conditions suivantes sont tous:

1) il y a plus de valeurs possibles "quelques"

2) la structure de données sous-jacente est pas liée

3) on n'a pas besoin d'un ordre stable

4) données est assez grand pour que le léger asymptotique sous-optimale d'exécution d'un tri bitonique ou doseurs impair-pair mergesort coups de pied dans

5) les données ne sont pas presque triée et ne consiste pas plus grandes pièces déjà trié

6), on peut accéder à la séquence de données simultanément à partir de plusieurs endroits

7) { Les écritures en mémoire sont particulièrement chers (parce que ce principal inconvénient de mergesort), pour autant qu'il ralentit l'algorithme au-delà de split sous-optimale probable d'un tri rapide. } ou { nousne peut avoir $ \ theta (\ log (n)) $ mémoire supplémentaire, $ \ theta (n) $ est trop (par exemple le stockage externe) }

p.s .: besoin de quelqu'un pour me aider avec la mise en forme du texte.

La plupart des méthodes tries doivent déplacer des données dans les étapes courtes (par exemple, la fusion fait sorte des changements, se confond alors localement ce petit morceau de données, puis se fond un plus grand. ..). Par conséquent, vous avez besoin de mouvements de données si les données sont loin de sa destination.

Quicksort, sur les autres essais latéraux pour intervertir les numéros qui sont dans la première partie de la mémoire et sont grandes, avec des chiffres qui sont dans la deuxième partie du tableau et sont de petite taille (si vous triez $ a \ le b $, l'argument est le même dans l'autre sens), ils sont rapidement attribués à proximité de leur destination finale.

Licencié sous: CC-BY-SA avec attribution

Non affilié à cs.stackexchange