Mergesort - Bas-plus rapide que de Haut en Bas?

Je viens de lire "les Algorithmes, 4e Ed" par Sedgewick & Wayne, et le long de la manière dont j'ai été l'implémentation des algorithmes discuté en JavaScript.

J'ai récemment pris la mergesort les exemples fournis dans le livre de comparer top-down et bottom-up des approches... mais je trouve que bottom-up est en cours d'exécution plus rapide (je pense). Voir mon analyse sur mon blog.
- http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/

Je n'ai pas été en mesure de trouver toutes les discussions que dit l'une des méthodes de mergesort devrait être plus rapide que l'autre. Est mon de mise en œuvre (ou l'analyse) imparfait?

Note: mon analyse des mesures de l'itératif boucles de l'algorithme, pas strictement le tableau compare/se déplace. C'est peut-être défectueux ou hors de propos?

EDIT: Mon analyse n'a pas réellement le temps de la vitesse, de sorte que ma déclaration au sujet de courir "vite" est un peu trompeur. Je suis suivi de l' "itérations" par le biais de la méthode récursive (top-down) et les boucles for (bottom-up) et bottom-up s'affiche pour utiliser moins d'itérations.

  • Les compare et les échanges sont les principaux éléments de coût dans le tri de l'analyse, je suis à peu près sûr.
  • oui, ils devraient normalement être les éléments à analyser lors de la comparaison des différents algorithmes de tri. Mais dans ce cas, ils devraient être les mêmes... elles sont de la même algorithme, donc ce n'est pas ce que je suis après. Ma mise en œuvre reflète ce qui est dans le livre... est-il possible que bottom-up utilise moins de boucles au-dessus/dans le tableau, mais a le même nombre de compare/se déplace?
  • Je vois votre point de vue... mais ceux qui ne contribuent pas à la disparité dans mon nombre d'itérations. Si vous regardez mon code, j'ai seulement suivi les itérations à l'intérieur de l'récursive et itérative des boucles. Les mathématiques.floor() n'a rien à faire avec elle - je ne suis pas en utilisant la base de l'analyse
  • Peut-être "courir plus vite" dans mon premier post n'est pas correct. Je suis la recherche bottom-up passe en boucle sur le tableau de moins en moins de temps, mais qui n'ont rien à voir avec la "vitesse"
  • Existe-il des différences lorsque vous le tri d'un tableau dont la taille est exactement une puissance de 2?
  • Oui... en utilisant un tableau de taille 1024, de haut en bas a 22,527 "itérations" tout en bas a 21,513 "itérations".

InformationsquelleAutor arthurakay | 2012-04-14
  1. 4

    Si par le plus rapide que vous avez, moins "itérations", alors oui. Si vous vous posez des questions sur le temps d'exécution peut-être.

    La raison en est que certaines de ces 21,513 itérations sont en fait plus que le 22,527 itérations.

    De la recherche à la source, il semble que certains des nœuds feuilles dans votre diagramme sont triés ensemble et non individuellement entraîne une diminution du nombre des fusions et des sortes mais eux prennent de plus en plus.

    • Bonne explication, merci! J'ai probablement besoin de digérer la mise en œuvre un peu plus, mais au moins je sais que je ne suis pas totalement fou. Je n'ai tout simplement pas s'attendre à une différence, compte tenu de mes deux algorithmes utilisent la même fusion() code.
    InformationsquelleAutor majinnaibu
  2. 13

    Je n'ai pas été en mesure de trouver toutes les discussions que dit l'une des méthodes de mergesort devrait être plus rapide que l'autre.

    Bottom-up et top-down fusion de toutes sortes, ainsi que d'autres variantes, ont été bien étudiés durant les années 90. En un mot, si vous mesurez le coût que le nombre de comparaisons de clés individuelles, les meilleurs coûts sont les mêmes (~ (n lg n)/2), le pire des coûts de haut en bas est inférieur ou égal au pire des cas de bottom-up (mais les deux ~ n lg n) et le coût moyen de haut en bas est inférieur ou égal à la moyenne des cas de bottom-up (mais les deux ~ n lg n), où "lg n" est le logarithme binaire. Les différences proviennent du linéaire. Bien sûr, si n=2^p, les deux variantes sont en fait exactement la même chose. Cela signifie que, de la comparaison, de sages, de haut en bas, c'est toujours mieux que bottom-up. En outre, il a été prouvé que la "moitié-moitié" partage de la stratégie de haut en bas de fusion tri est optimal. Les documents de recherche sont de Flajolet, Golin, Panny, Prodinger, Chen, Hwang et Sedgewick.

    Voici ce que j'ai trouvé dans mon livre de Conception et d'Analyse de Purement Fonctionnelle Programmes (Publications de l'ordre, royaume-UNI), en Erlang:

    tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T)           -> T.

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S,    T,      U) -> mrg(tms(S),tms(T)).

mrg(     [],    T)            -> T;
mrg(      S,   [])            -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg(  [X|S],    T)            -> [X|mrg(S,T)].

    Noter que c'est pas un tri stable. Aussi, en Erlang (et OCaml), vous devez utiliser alias (ALIAS=...) dans les modèles si vous souhaitez économiser de la mémoire. L'astuce ici est de trouver le moyen de la liste sans le savoir sa longueur. Ceci est fait par cutr/3, qui gère deux pointeurs de la liste d'entrée: l'un est incrémenté par l'un et l'autre par deux, donc quand le second arrive à la fin, le premier est dans le milieu. (J'ai appris cela à partir d'un papier par Olivier Danvy.) De cette façon, vous n'avez pas besoin de garder une trace de la durée et de ne pas dupliquer les cellules de la deuxième moitié de la liste, donc vous avez seulement besoin (1/2)n lg n de l'espace supplémentaire, par rapport à n lg n. Ce n'est pas bien connue.

    Il est souvent affirmé que la variante est préférable pour les langages fonctionnels ou de la liste chaînée (Knuth, Panny, Prodinger), mais je ne pense pas que cela est vrai.

    J'ai été intrigué, comme vous, par le manque de discussion sur la fusion de toutes sortes, j'ai donc fait mes propres recherches et a écrit un grand chapitre à ce sujet. Je suis actuellement en train de préparer une nouvelle édition avec plus de matériel sur les fusionner toutes sortes.

    Par ailleurs, il existe d'autres variantes: file d'attente de fusion de tri et sur la ligne de fusion de tri (je discuter de ce dernier dans mon livre).

    [EDIT: la mesure du coût est le nombre de comparaisons, il n'y a pas de différence entre le fait de choisir un tableau par rapport à une liste liée. Bien sûr, si vous mettez en œuvre du sommet vers la variante avec les listes chaînées, vous devez être intelligent, comme vous ne savent pas forcément le nombre de touches, mais vous aurez besoin de traverser une moins la moitié des touches, à chaque fois, et à réaffecter, au total (1/2)n lg n cellules (si vous êtes intelligent). Bas jusqu'à la fusion de tri avec les listes chaînées en réalité plus de la mémoire supplémentaire, n lg n + n cellules. Donc, même avec les listes chaînées, le top-down variante est le meilleur choix. Aussi loin que la longueur du programme, votre kilométrage peut varier, mais dans un langage fonctionnel, de haut en bas de fusion tri peut être fait plus court que bottom-up, si la stabilité n'est pas nécessaire. Il y a quelques textes portant sur les implémentations de problèmes de fusion de tri, comme dans (pour laquelle vous avez besoin de tableaux), ou la stabilité etc. Par exemple, Une Analyse Minutieuse de Mergesort Programmes, par Katajainen et Larsson Traff (1997).]

    • vous écrivez "et le coût moyen de haut en bas est inférieur ou égal au pire des cas de bottom-up (mais les deux ~ n lg n)" est-ce donc, ou vouliez-vous dire "moyen" de "bottom-up"? A l'analyse effectuée pour les tableaux ou est-il valable pour les listes chaînées trop?
    • Vous êtes de droite. Je corrigée mon texte et ajouté de l'information.
    • merci; je serais très intéressé de voir votre optimale de haut en bas des listes liées fonctionnelle mergesort, à comparer avec ceci: mgsort xs = foldt merge [] [[x]|x<-xs].
    • (Je ne veux pas laisser entendre que c'est un one-liner; avec toutes les fonctions regroupées et un peu inline, ça devient un 9-doublure en Haskell).
    • J'ai édité la réponse. Le Haskell version vous référer semble être une bottom-up variante. Il est difficile de comparer avec d'autres langues, car il utilise des fonctionnalités spécifiques à Haskell. C'est pourquoi j'ai choisi une version simplifiée de Erlang pour mon livre, de sorte que les programmes s'adaptent facilement et comparés. Je donne aussi une traduction du code ci-dessus en Java, en gardant le style fonctionnel:-) (Il y a un chapitre sur le style fonctionnel à Java et à une prochaine sur XSLT.)
    • Pour une matrice ou un vecteur, de haut en bas de fusion de tri consiste à n-2 instances d'appels récursifs, généralement avec deux pointeurs et les deux indices par appel. En dépit de haut en bas d'avoir un cache amical parti pour quelques niveaux de récursivité rapport de bas en haut des cols, mes comparaisons ont trouvé des bas jusqu'à la fusion de tri de 5% à 10% plus rapide. Sur un processeur Intel 3770k, mode 64 bits, le tri de 20 millions de dollars (20*1024*1024) les entiers 64 bits prend 2.07 secondes avec de haut en bas, de 1,92 secondes avec de bas en haut, d'environ 8% plus rapide.
    • Pour les listes chaînées, bas jusqu'à la fusion de tri à l'aide d'une petite taille (25 à 32) tableau de pointeurs vers les nœuds élimine la nécessité de numériser les listes de les diviser. Pour une grande liste avec éparpillées, de nœuds, de bas en haut est+ de 35% plus rapide. wiki exemple .

    InformationsquelleAutor Christian
  3. 7

    J'avais posé la même question sur coursera forums de classe pour le numéro d'août 2012 de ce cours. Le professeur Kevin wayne (Princeton) a répondu que, dans de nombreux cas, la récursivité est plus rapide que l'itération en raison de la mise en cache d'améliorer les performances.

    Donc, en bref, que j'ai eu à l'époque était que de haut en bas de fusion tri sera plus rapide que le fond, jusqu'à la fusion de tri en raison de la mise en cache des raisons.

    Veuillez noter que la classe a été enseigné dans le langage de programmation Java(pas de Javascript).

    • Mieux vaut tard que jamais de commentaire? L'amélioration de la mise en cache de haut en bas peut se produire sur de petites sous-tableaux, où le juste fusionné de sortie est encore dans le cache pour être utilisé pour l'entrée suivante. Cependant, pour la plupart des processeurs, que le cache est vidé en mémoire en même temps il est utilisé pour la fusion d'entrée. Le résultat final sur des points de référence, j'ai couru sur des processeurs X86 est de bas en haut est plus rapide, mais pas par beaucoup depuis la récursivité surcharge est O(log2(n)), alors que le temps total est O(n log2(n)). Par exemple, le tri de 16 millions d'entiers 64 bits sur mon système, de bas en haut prend environ 1,5 secondes, de haut en bas sur les 1,6 secondes.
    InformationsquelleAutor Nikunj Banka