Comment trier 100 Go de chaînes de caractères

Question

Étant donné un disque dur de 120 Go, dont 100 sont remplis de chaînes de caractères de longueur 256 et 2 Go de RAM, comment puis-je trier ces chaînes de caractères en Java le plus efficacement possible ? Combien de temps cela prendra-t-il ?

Answer 1

A1. Vous voulez probablement implémenter une forme de fusionner-trier .

A2 : Plus long que si vous aviez 256 Go de RAM sur votre machine.

Edit : piqué par la critique, je cite l'article de Wikipedia sur le tri par fusion :

*Le tri par fusion est si intrinsèquement séquentiel qu'il est pratique de l'exécuter en utilisant des lecteurs de bandes lents comme périphériques d'entrée et de sortie. Il nécessite très peu de mémoire, et la mémoire requise ne dépend pas du nombre d'éléments de données.

Pour la même raison, il est également utile pour trier les données sur le disque qui sont trop volumineuses pour tenir entièrement dans la mémoire primaire. Sur les lecteurs de bande qui peuvent fonctionner à la fois en arrière et en avant, les passes de fusion peuvent être exécutées dans les deux sens, évitant ainsi les temps de rembobinage*.

Answer 2

Voici comment je m'y prendrais :

La phase 1 consiste à diviser les 100 Go en 50 partitions de 2 Go, à lire chacune des 50 partitions en mémoire, à les trier à l'aide de quicksort et à les écrire. Vous voulez que les partitions triées se trouvent à l'extrémité supérieure du disque.

La phase 2 consiste ensuite à fusionner les 50 partitions triées. C'est la partie la plus délicate car vous n'avez pas assez d'espace sur le disque pour stocker les partitions ET le résultat final trié. Donc ...

1. Faites une fusion à 50 pour remplir les 20 premiers Go à l'extrémité inférieure du disque.

2. Faites glisser les données restantes dans les 50 partitions vers le haut pour obtenir 20 Go supplémentaires d'espace libre contigu à la fin des 20 premiers Go.

3. Répétez les étapes 1. et 2. jusqu'à ce que vous ayez terminé.

Cela fait beaucoup d'entrées-sorties sur le disque, mais vous pouvez utiliser vos 2 Go de mémoire pour la mise en mémoire tampon dans les étapes de copie et de fusion afin d'obtenir un débit de données en minimisant le nombre de recherches sur le disque, et faire de gros transferts de données.

EDIT - @meriton a proposé un moyen astucieux de réduire la copie. Au lieu de glisser, il suggère que les partitions soient triées en ordre inverse et lues à l'envers dans la phase de fusion. Cela permettrait à l'algorithme de libérer l'espace disque utilisé par les partitions (phase 2, étape 2) en tronquant simplement les fichiers de partition.

Les inconvénients potentiels sont une fragmentation accrue du disque et une perte de performance due à la lecture des partitions à l'envers. (Sur ce dernier point, la lecture d'un fichier à l'envers sous Linux / UNIX nécessite plus de syscalls, et l'implémentation de FS peut ne pas être capable de faire de la "lecture anticipée" dans la direction inverse).

Enfin, j'aimerais souligner que toute prédiction théorique du temps pris par cet algorithme (et d'autres) est en grande partie une conjecture. Le comportement de ces algorithmes sur une JVM réelle, un système d'exploitation réel et des disques réels est tout simplement trop complexe pour que des calculs de type "back for the envelope" puissent donner des réponses fiables. Un traitement approprié nécessiterait une mise en œuvre, un réglage et un étalonnage réels.

Answer 3

Je répète en gros La réponse de Krystian mais en élaborant :

Oui, vous devez faire cela plus ou moins en place, puisque vous avez peu de RAM disponible. Mais des tris naïfs en place seraient un désastre ici, simplement à cause du coût du déplacement des chaînes.

Plutôt que de déplacer les cordes, gardez simplement la trace de celles qui doivent être échangées avec d'autres et déplacez-les, une fois, à la fin, à leur emplacement final. En d'autres termes, si vous avez 1000 chaînes, créez un tableau de 1000 ints. array[i] est l'emplacement où la chaîne i doit se retrouver. Si array[17] == 133 à la fin, cela signifie que la chaîne 17 doit se retrouver à la place de la chaîne 133. array[i] == i pour tous les i au départ. Echanger des chaînes de caractères, donc, est juste une question d'échange de deux ints.

Ensuite, n'importe quel algorithme in-place comme quicksort fonctionne assez bien.

La durée du jeu est sûrement dominée par le mouvement final des cordes. En supposant que chacune d'entre elles se déplace, vous déplacez environ 100 Go de données en écritures de taille raisonnable. Je peux supposer que le lecteur / contrôleur / OS peut déplacer environ 100MB/sec pour vous. Donc, 1000 secondes environ ? 20 minutes ?

Mais est-ce que ça rentre dans la mémoire ? Vous disposez de 100 Go de chaînes de caractères, dont chacune fait 256 octets. Combien de chaînes de caractères ? 100 * 2^30 / 2^8, soit environ 419M de chaînes. Vous avez besoin de 419M ints, chacun étant de 4 octets, soit environ 1.7GB. Voilà, ça tient dans vos 2GB.

Answer 4

Cela ressemble à une tâche qui demande Triage externe méthode. Le volume 3 de "The Art of Computer Programming" contient une section avec une discussion approfondie sur les méthodes de tri externe.

Answer 5

Je pense que vous devriez utiliser BogoSort. Il faudra peut-être modifier un peu l'algorithme pour permettre le tri in situ, mais ça ne devrait pas être trop difficile :)