Sur un disque tournant, j'ai N enregistrements que je veux permuter. En RAM, j'ai un tableau de N indices qui contiennent la permutation souhaitée. J'ai aussi assez de RAM pour contenir n enregistrements à la fois. Quel algorithme puis-je utiliser pour exécuter la permutation sur disque le plus rapidement possible, en tenant compte du fait que l'accès séquentiel au disque est beaucoup plus rapide?
J'ai beaucoup de disque excédentaire à utiliser pour les fichiers intermédiaires, si vous le souhaitez.
3 Réponses :
Il s'agit d'un problème connu. Trouvez les cycles dans votre ordre de permutation. Par exemple, étant donné cinq enregistrements à permuter [1, 0, 3, 4, 2], vous avez des cycles (0, 1) et (2, 3, 4). Vous faites cela en choisissant une position de départ inutilisée; suivez les pointeurs d'index jusqu'à ce que vous reveniez à votre point de départ. La séquence de pointeurs décrit un cycle.
Vous permutez ensuite les enregistrements avec une variable temporaire interne, longue d'un enregistrement.
temp = disk[0] disk[0] = disk[1] disk[1] = temp temp = disk[2] disk[2] = disk[3] disk[3] = disk[4] disk[4] = temp
Notez que vous pouvez également effectuer la permutation comme vous parcourez les pointeurs. Vous aurez également besoin d'une méthode pour rappeler quelles positions ont déjà été permutées, comme effacer l'index de permutation (mettez-le à -1).
Pouvez-vous voir comment généraliser cela?
p>
Le problème ici est l'accès séquentiel, pas seulement le désir de limiter les lectures / écritures. Visiter tous les cycles, un à la fois, ne va pas capitaliser là-dessus.
Le problème est de faire passer un la permutation, réorganisant ainsi les enregistrements pour un accès séquentiel optimal.
Je pense que la permutation pourrait être faite plus rapidement si elle était faite d'une manière qui tirait parti des lectures et des écritures séquentielles. Surtout parce que j'ai un peu d'espace tampon.
Prenons une situation où la permutation est cohérente sur des blocs de n éléments (par exemple avec n = 4, la permutation 4,5,6,7,0,1,2,3. Votre proposition ne tire pas correctement parti de votre espace de travail supplémentaire pour appliquer la permutation sans recherche de disque supplémentaire inutile.
@Sneftel: à droite. La mise à jour sur la question le montre clairement. Cette («ma») réponse suppose que la permutation est pour une efficacité séquentielle future , pas pour l’efficacité de la permutation elle-même. Nécessite une révision complète.
Ceci est un problème avec la coordination des intervalles. Je vais simplifier légèrement la notation en changeant la mémoire disponible pour les enregistrements M - avoir des N majuscules et minuscules est un peu déroutant.
Premièrement, nous re-cast les permutations comme une série d'intervalles, la durée de rotation pendant laquelle un enregistrement doit résider dans la RAM. Si un enregistrement doit être écrit dans une position de numéro inférieur, nous augmentons le point de terminaison de la taille de la liste, pour indiquer le bouclage - nous devons attendre la prochaine rotation du disque. Par exemple, en utilisant mon exemple précédent, nous développons la liste:
[0, 3] [3, 6] [2+4, 5+4] [1+4+4, 4+4+4]
Maintenant, nous appliquons la résolution de planification gourmande standard. Tout d'abord, triez par point de terminaison:
[0, 3] [1, 4] [2, 5] [3, 6]
Maintenant, appliquez l'algorithme pour M-1 "voies"; le supplément est nécessaire pour l'espace d'échange. Nous remplissons chaque voie, en ajoutant l'intervalle avec le point de terminaison le plus ancien, dont le point de départ ne se chevauche pas:
[0, 4] [1, 5] [2, 6] [3, 7] [4, 0+8] [5, 1+8] [6, 2+8] [7, 3+8]
Nous pouvons le faire dans un total de 7 "ticks" si M> = 3. Si M = 2, nous reportons la deuxième voie de 2 rotations à [11, 15].
Le bel exemple de Sneftal nous en donne plus problèmes, avec un chevauchement plus profond:
[0, 1] [2, 3] [3, 4] [4, 7] [1, 5]
Cela nécessite 4 "voies" si disponibles, en différant les voies si nécessaire si M
Le cas pathologique est celui où chaque enregistrement de la permutation doit être recopié en arrière une position, telle que [3, 0, 1, 2], avec M code> = 2.
[0, 1] [2, 3] [3, 4] [1, 5] [4, 7]
Dans ce cas, nous parcourons le cycle de report plusieurs fois. À la fin de chaque rotation, nous devons reporter tous les intervalles restants d'une rotation, ce qui entraîne
[1, 0, 3, 4, 2] 0 -> 1 1 -> 0+5 2 -> 3 3 -> 4 4 -> 2+5
Cela vous fait bouger ou avez-vous besoin de plus de détails? p>
J'ai une idée qui devra peut-être être améliorée. Mais voilà:
supposons que le hdd ait la structure suivante:
(1) 1111000000000000001111 (2) 1111111000000000000000
Et nous voulons écrire cette permutation:
| - - - 0 1 | 2 4 3 5 6 | ... | - - - 1 1 | 1 1 1 1 1 | ...
Maintenant, nous devons noter que si ce qui suit est vrai:
0 1 2 3 4 5 6 7 8 9 10 ... Inf
Nous pouvons parcourir le disque dur en une seule passe en utilisant la fonction ci-dessus. Par exemple:
| 2 3 1 2 2 | 2 3 1 2 2| 2 3 1 2 2 | 2 3 1 2 2 |... Inf
Nous pouvons commencer où nous voulons, par exemple à partir du "4" initial. Nous lisons 4 éléments séquentiellement, (n a 4 éléments maintenant) et nous commençons à placer à partir de 0 1 2 3, (nous pouvons parce que n = 5 au total, et 4 est utilisé. 1 est utilisé pour le swap). Donc, le total des opérations est de 4 lectures consécutives, puis des opérations rw 8 fois.
En utilisant cette analogie, il devient clair que si nous soustrayons "n-1" des équations (1) et (2), les positions qui ont la valeur "
Nous sélectionnons donc eq. (2) et soustraire, pour disons "n = 3", nous soustrayons 2 de l'éq. (2):
5 >> 2 4 >> 3 1 >> 1 2 >> 2 3 >> 2
Maintenant, il est clair que, en utilisant f (), et en partant de 0, en supposant n = 3, nous aurons une opération de départ comme telle: r , r, rw, rw, ...
Alors, comment faire le reste et trouver le coût minimum? Nous placerons un tableau avec un coût minimum initial, juste en dessous de l'équation (2). Les positions dans ce tableau signifieront où nous voulons que f () soit exécuté.
2 3 5 1 4
Le deuxième tableau, ceux avec 1 et 0 indiquent au programme où exécuter f ( ). Notez que si nous supposons que ces emplacements sont erronés, f () l'affirmera.
Avant de commencer à placer des fichiers dans hdd, nous voulons bien sûr voir si les positions f () sont correctes. Nous vérifions s'il y a des affirmations, nous essaierons de minimiser les coûts tout en supprimant toutes les affirmations. Donc, par exemple:
5 4 1 2 3
(1) a évidemment un coût plus élevé que (2). Donc, la question simplifie la recherche du tableau 1-0.
Quelques idées pour trouver le meilleur tableau:
Force brute: écrivez un tableau de comme indiqué dans (2) et commencez à décaler les 1 vers la droite, dans un ordre qui essaie toutes les permutations disponibles:
1111111100000000 1111111010000000 1111110110000000 ...
Approche complètement aléatoire: branchez mt1997 et commencez à permuter. Chaque fois que vous constatez une forte baisse des coûts, arrêtez l'exécution et implémentez le copier-coller hdd. Vous ne trouverez pas le minimum global, mais vous obtiendrez un bon compromis.
Algorithmes génétiques: Pour les permutations où "le nombre de changements est bien inférieur à n - 1", la méthodologie fournie dans cette réponse devrait (?) fournir un minimum global et des gradients lisses. Cela permet d'utiliser des algorithmes génétiques sans trop se fier aux mutations.
Un avantage que je trouve dans cette approche est que, puisque OP a mentionné qu'il s'agit d'un problème réel, la méthode fournit un moyen simple (plus?) de changer les fonctions de coût. Il est plus facile de détecter l'effet, par exemple, d'avoir beaucoup de petits fichiers contigus à copier plutôt que d'avoir un seul gros fichier. Ou peut-être que rrwwrrww est meilleur que rrrrwwww?
Est-ce que tout cela a du sens? Nous devrons essayer ...
Pas d'espace disque supplémentaire pour la mise en mémoire tampon (juste la RAM)?
@Gene Vous pouvez appliquer n'importe quelle permutation avec O (1) espace supplémentaire plus N bits (visitez tous les cycles). Il n'est pas nécessaire de mettre en mémoire tampon sur le disque.
@Gene Je n'ai pas pensé à le mentionner, mais oui, je peux tamponner sur le disque si vous le souhaitez. Je ne suis pas préoccupé par l'utilisation du disque dans ce cas, seulement la vitesse et la RAM. J'ai édité la question pour le mentionner.
S'il s'agit d'une application du monde réel, pourquoi ne pouvez-vous pas lister toutes les permutations et les trier selon une fonction de coût, dans laquelle l'accès séquentiel est privilégié? Vous pouvez ensuite suivre la liste triée.
@Maximus Je ne veux pas parcourir toutes les permutations, j'ai un tableau qui contient une permutation souhaitée. Ce que je recherche, c'est un algorithme pour la meilleure façon d'exécuter cette permutation spécifique.
Vous souhaitez lire N fichiers sur le disque et les réécrire selon la permutation souhaitée sur le tableau?
@Maximus Oui, mais je n'ai pas assez de mémoire pour stocker tous les N enregistrements à la fois. L'approche naïve consisterait à accéder au fichier de manière aléatoire tout en écrivant le résultat, mais j'aimerais plutôt le faire d'une manière qui maximise la séquentialité des lectures.
@Maximus :-) Le problème peut être fait en O (N) temps et O (1) espace (en supposant que la liste de permutation est donnée). Vous proposez un tri Leland gradué ?? Aimer!!
@Prune :) Eh bien, dans ce cas, vous ne pouvez pas faire mieux que le temps O (N). Mais je cherchais un moyen d'utiliser l'espace O (n), simplement parce que c'est une application réelle et que les constantes de Big-O comptent parfois. Alors peut-être pouvons-nous trouver un moyen d'utiliser plus d'espace et moins de temps?