Qui algorithme de tri qui fonctionne le mieux sur un très vaste ensemble de données
J'étais à la recherche sur Internet pour trouver de l'algorithme de tri qui est le mieux adapté pour un très grand ensemble de données. J'ai trouvé que beaucoup ont un avis fusion du tri est meilleur parce qu'il est juste, ainsi que le fait qu'il s'assure que le temps de la complexité est O(n log n) et la fonction de tri rapide n'est pas sûr: Il est vrai aussi que les variations de quicksort peut également ne pas être en sécurité parce que le jeu de données réelles peut être n'importe quoi.
Si la permutation de deux éléments négligeables coût du temps, alors pourquoi ne pouvons-nous pas choisir tas de sorte que le meilleur algorithme de tri dans ce cas, car il est en place ainsi que O(n log n)?.
En cas de Fusion de tri, il nécessite un autre O(n) l'espace; si les données sont très grandes puis on ne peut pas utiliser cet algorithme.
S'il vous plaît dites-moi: l'algorithme doit être le meilleur dans ce scénario?.
Mergesort sur une liste liée prend de la constante de l'espace et est encore stable, de sorte que votre préoccupation à propos de l'espace peut-être pas valide. Il est également efficace sur les fichiers et d'utiliser plusieurs processeurs.
sorting-algorithms.com a un affichage amusant de certaines des variables et des concessions à faire.
Faut-il vraiment utiliser O(1) auxiliaire de l'espace? J'ai pensé que vous aviez besoin de O(log n) de l'espace pour stocker la pile d'appel.
Non, c'est un algorithme itératif avec O(1) de l'espace. Juste un couple de pointeurs et d'une poignée de compteurs.
OriginalL'auteur Ankit Kumar Namdeo | 2015-08-26
Vous devez vous connecter pour publier un commentaire.
Il n'y a pas un algorithme qui est clairement le "meilleur" de l'algorithme. Il dépend d'un tas de facteurs.
Pour commencer, pouvez-vous adapter vos données dans la mémoire principale? Si vous ne pouvez pas, alors vous aurez besoin de s'appuyer sur un externe algorithme de tri. Ces algorithmes sont souvent basées sur des quicksort et mergesort.
Deuxième, savez-vous quelque chose au sujet de votre entrée de distribution? Si c'est surtout triés, puis quelque chose comme Timsort pourrait être une excellente option, car il est conçu pour bien fonctionner sur les données triées. Si c'est principalement du au hasard, Timsort est probablement pas un bon choix.
Troisième, ce genre d'éléments êtes-vous le tri? Si vous effectuez le tri des objets génériques, alors vous êtes assez bien verrouillé en comparaison de tri. Si non, vous pourriez peut-être utiliser un non-comparaison de tri comme le comptage, de tri ou tri radix.
Quatrième, le nombre de noyaux avez-vous? Certains algorithmes de tri (quicksort, mergesort, MSD tri radix) paralléliser vraiment bien, tandis que d'autres ne le font pas (heapsort).
Cinquième, comment sont vos données représentées? Si elles sont stockées dans un tableau, quicksort ou un quicksort variante sera probablement bien faire en raison de la localité de référence, tandis que mergesort peut être lente en raison de la mémoire supplémentaire nécessaire. Si ils sont dans une liste, même si, la localité de référence de quicksort s'en va et mergesort devient tout à coup à nouveau compétitifs.
La meilleure option est probablement prendre beaucoup de différents facteurs en compte et ensuite prendre une décision à partir de là. L'une des raisons c'est tellement amusant de conception et l'étude d'algorithmes est qu'il y a rarement un seul meilleur choix; souvent, la meilleure option dépend de la tonne sur votre situation particulière et des changements en fonction de ce que vous voyez.
(Vous avez mentionné quelques détails sur le quicksort, heapsort, et mergesort que je voulais toucher avant de clore cette réponse. Alors vous avez raison que quicksort a un dégénéré, O(n2) le pire des cas, il existe de nombreuses façons d'éviter cela. Le introsort algorithme conserve la trace de la profondeur de récursivité et les commutateurs de l'algorithme de heapsort si il semble que le quicksort va dégénérer. Cela garantit O(n log n) le pire des cas, le comportement avec une faible surcharge de la mémoire et maximise le montant de la prestation que vous obtenez à partir de quicksort. Randomisés de quicksort, tout en ayant un O(n2) le pire des cas, a une extrêmement petite probabilité de frapper ce pire des cas.
Heapsort est un bon algorithme dans la pratique, mais n'est pas aussi rapide que les autres algorithmes, dans certains cas, parce qu'il n'a pas de bonnes localité de référence. Cela dit, le fait qu'il ne dégénère et n'a besoin que O(1) auxiliaire de l'espace est un énorme argument de vente.
Mergesort a besoin de beaucoup d'auxiliaire de la mémoire, qui est l'une des raisons pour lesquelles vous pourriez ne pas l'utiliser si vous avez une énorme quantité de données à trier. Il est utile de connaître au sujet, bien que, depuis ses variantes sont largement utilisés.)
Le quicksort variante, je fais allusion à des œuvres en streaming le contenu du fichier par le biais de la mémoire, le maintien d'un énorme double-clos file d'attente de priorité. Lorsque la file d'attente se remplit, les éléments qui sont trop petits sont expulsés et écrit à un "moins" de fichiers et les éléments qui sont trop grandes sont expulsés et de l'écrit à une "grande" de fichier. L'ultime file d'attente de contenu et écrit à un "pivot" de fichier, puis de moins et de plus les fichiers sont triés de manière récursive. Ce n'est pas aussi commun que le mergesort variante, mais il fonctionne toujours, je crois.
L'article Wiki externe de tri. Un k-way en bas de fusion tri peut peut utiliser de grandes séquentielle I/O comme mentionné dans l'article de wiki, qui permet de réduire les frais généraux sur un disque dur, mais dans le cas d'un disque SSD, il n'existe pas de demander des frais généraux (l'agencement intérieur est reconfigurée afin de réduire écrire des nombres à des zones spécifiques), de sorte tri rapide peut être une alternative viable, même si elle n'est pas stable. Ce n'est pas mentionné dans l'article de wiki.
Je n'y avais pas pensé Ssd. Comme pour le tri rapide, découvrez ce site, qui IIRC est aussi un chapitre de livre.
Les références que j'ai trouver pour quicksort parler de la bonne fois de la complexité de O(n log(n)), mais pas ce journal. Pour un k-way merge de tri, le pire des cas le temps de la complexité est O(n logk(n)); et ma conjecture est que si k == 8 et k == 16, il va être beaucoup plus rapide qu'un quicksort. Également mentionné dans mon commentaire après le post original, quicksort ne plus se compare, mergesort plus de coups, et si le tri d'un certain type de structure par index ou un pointeur, mergesort est généralement plus rapide que quicksort.
OriginalL'auteur templatetypedef
Votre question est trop vague pour être répondu plus précisément. Il y a un certain nombre de l'efficacité des algorithmes de tri et chacun a ses propres forces et faiblesses. Si vous connaissez vos données, il est possible qu'une efficacité optimale de l'algorithme (tas, rapide, fusion, etc) n'est pas le bon outil pour le travail.
Par exemple, dans un récent produit, nous avons dû garder les signets dans un document Word triés en fonction de leur ordre d'apparition. Les signets pourrait devenir non triés en raison de l'édition du document (copier, couper, coller) donc, après chacune de ces opérations, il est important de recourir à la liste. Dans ce cas, bubblesort était la bonne réponse, même si elle a plus de big-O complexité ensuite n'importe quel nombre d'autres algorithmes. Le fait que le tri est efficace lorsque la liste est presque triées (ce qui est généralement le cas dans ce cas) et c'est une opération signifiait que c'était le bon outil pour le travail.
Prendre un coup d'oeil dur à vos données et de lire sur les différents points forts et les faiblesses de la bien connue des algorithmes de tri, et vous serez bien sur votre façon de répondre à votre propre question.
OriginalL'auteur P. Hinker