Le temps de la Complexité et le Coût de l'Externe, de Fusion et de Tri

Je l'ai obtenu à partir d'un lien qui parle de fusion externe de tri.

À partir de la diapositive 6 Exemple: avec 5 pages de mémoire tampon, de sorte 108 page fichier

  • Pass0: [108/5] = 22 tris de 5 pages chacun (dernier de fonctionner uniquement avec 3 pages)

  • Rapidair1 [22/4] = 6 tris de 20 pages chacun (dernier de fonctionner uniquement avec 8 pages)

  • Pass2: [6/3] = 2 tris, 80 pages et 28 pages

  • Pass 3: [2/2] = 1 fichier Trié de 108 pages

Question: Ma compréhension est en externe, de fusion et de tri, en passe de 0 vous créer des morceaux et puis trier chaque morceau. Dans le reste de passe que vous gardez la fusion.
Ainsi, l'application qui à l'exemple ci-dessus, puisque nous n'avons que 5 pages de mémoire tampon, dans le Passage à 0 de ses clair que nous avons besoin 22 tris de 5 pages chacun.

  1. Maintenant, pourquoi faisons-nous tris pour le reste passe à la place ou à la fusion ?

  2. Comment se fait-il dit, pour passer de 1, 6 tris de 20 pages chacun quand on n'a que 5 pages de mémoire tampon ?

  3. Où est exactement de fusion qui se passe ici ? et comment est N en réduisant à chaque passage je.e de 108 à 22 à 6 à 2 ?

InformationsquelleAutor Frank Q. | 2012-04-28
  1. 16

    Externe, de Fusion, le Tri est nécessaire lorsque vous ne pouvez pas stocker toutes les données dans la mémoire. Le meilleur que vous pouvez faire est de briser les données dans des tris et de fusionner les pistes dans des passes suivantes. La longueur de course est lié à votre disposition taille de la mémoire tampon.

    Pass0: vous êtes en effectuant les opérations EN PLACE. Si vous chargez 5 pages de données dans la mémoire, puis de les trier en place en place à l'aide d'un algorithme de tri.
    Ces 5 pages seront stockés ensemble comme une course.

    Passes suivants: vous ne pouvez plus faire les activités en place, puisque vous êtes la fusion s'exécute de nombreuses pages. 4 pages sont chargées dans la mémoire, et le 5ème est le tampon d'écriture. La fusion est identique à l'algorithme de tri fusion, mais vous allez diviser et conquérir par un facteur de B-1 au lieu de 2. Lorsque le tampon d'écriture est rempli, il est écrit sur le disque et la page suivante est commencé.

    Complexité:
    Lors de l'analyse de la complexité de la fusion externe de tri, le nombre d'I/Os est ce qui est envisagé. Dans chaque passage, vous devez lire une page et d'écrire la page. Soit N le nombre de pages. Chaque course sera le coût 2N. Lire la page, écrire la page.

    Soit B le nombre de pages que vous pouvez tenir de l'espace tampon et N le nombre de pages.

    Il y aura ceil(log_B-1(ceil(N/B))) passe. Chaque passage aura 2N I/Os. Donc O(nlogn).

    Dans chaque passe, la page de la longueur de course est en augmentation par un facteur de B-1, et le nombre de tris est en diminution par un facteur de B-1.

    Pass0: ceil(108 /5) = 22, 5 pages par exécuter

    Rapidair1: ceil(22 /4) = 6, 20 pages par exécuter

    Pass2: ceil(6 /4 ) = 2, 80 pages par exécuter

    Pass3: ceil(2 /4 ) = 1 - faire, 1 série de 108 pages

    • Supposons que la taille de toutes les pages est égal. Vous chargez 4 pages à partir de 108 pages et de le stocker dans les 4 d'entrée de la mémoire tampon des pages puis de fusionner les données en mémoire tampon des résultats. Maintenant, comment le résultat de la mémoire tampon contenir les données qui sont de la taille de l'4 d'entrée de la mémoire tampon des pages ?
    • Toutes les pages sont de la même taille, à part le dernier. Dans pass 0, vous chargez les 5 pages et de les trier en place. Il ne retient pas tous les 4 pages à la fois. Il ne contient que la première page de chaque course, pensez à chacun de s'exécuter comme une liste chaînée. À la fin de chaque page est un pointeur à l'endroit où la page suivante dans la course. Les données sont triées, de sorte que les données de la page 2 va être logiquement après les données de la page 1. Je pense que vous avez le mélange jusqu'à ce qu'une page et un la est. Les séries sont composées de plusieurs pages, les pages contiennent des données.
    • Pour l'étape 1, vous copiez les 4 pages à partir du disque dans le 4 pages d'entrée dans la mémoire RAM, puis de fusionner ces pages en page de sortie qui est dans la mémoire RAM. C'est que la sortie de page 4 fois la taille de l'autre entrée de pages ? Vous voyez ce que je veux dire ?
    • Ohh ok. Eh bien, oui. L'entrée et la sortie est de 1 à 1, de sorte que si vous lisez dans les 108 pages, 108 pages seront écrites sur le disque. Mais le nombre de pages par course est de plus en plus à chaque passage. Vous écrivez 1 page pour de la ram, quand il se remplit, vous l'écrire sur le disque. Puis il se vide et se remplit de nouveau, après qu'il remplit, il est écrit sur le disque après la page précédente. Si la mémoire tampon peut contenir 250 #s, puis 200 sera de 4 pages, une fois 50 triés nombres sont écrits dans la mémoire tampon de sortie, il est sauvegardé sur le disque et effacé. Chaque fois qu'un tampon d'entrée est à court de chiffres, la prochaine page est lu. Espérons que cette aide.
    • Dans un étrange cas comme celui-ci où le nombre de pages est très petit, il importe donc que c'est discret, vous pourriez faire moins de la fusion de travail par la fusion de trois 20page court entre rapidair1 et pass2. Puis pass2 est un 4-way merge. Qui réduit la quantité totale de mouvement de données. Dans une situation réelle, avec des milliers à des millions de pages de mémoire disponible, votre idéal de fusion largeur est probablement limité par autre chose que le nombre de pages. (par exemple, en évitant trop d'I/O cherche)
    InformationsquelleAutor JustinDanielson
  2. 0

    A. dans la mesure où il ne mentionne JAMAIS la fusion, je suppose (l'espoir) que la "tri", les passes sont à effectuer les fusions.

    B. Encore une fois, en supposant que c'est la fusion, vous avez besoin d'un tampon pour enregistrer les enregistrements fusionnés, et l'utilisation de l'un des tampons pour chaque fichier fusionnés: ainsi, les 4 fichiers d'entrée, chaque w/5 pages: 20 pages.

    C. Crois que j'ai répondu, où l'opération de fusion est deux fois maintenant 🙂

    • Je ne vois pas où 4 fichiers d'entrée vient ? Vous traitez avec les pages ici. Je peux utiliser les 4 pages de mémoire tampon de 5, pour charger les 4 pages de 108 pages et stocker le résultat dans la dernière page. Mais cela ne semble pas être le cas, comme expliqué ci-dessus. Et dans le passage de deux comment est-elle devenue 6/3 ?
    • Désolé; j'ai appris cela à l'aide de fichiers au lieu de les pages. Mais les pages sont regroupées dans des ensembles plus larges, de plus les séquences d'enregistrements. Vous voulez réserver un tampon de page pour chaque groupe, tirant dans chaque page dans la séquence de ce groupe, comme la fusion devient pour elle. Pour passer 2, les groupes sont maintenant de 20 pages (à partir de 4 groupes de taille 5), donc il y a seulement 6 groupes.
    InformationsquelleAutor Scott Hunter