fichier sorte de fusion basé sur grands ensembles de données en Java

Question

donné grands ensembles de données qui ne correspondent pas à la mémoire, est-il une bibliothèque ou api pour effectuer de tri en Java? l'implémentation serait probablement similaire au tri de l'utilitaire linux.

Answer 1

Java fournit un usage général de routine de tri qui peut être utilisé dans le cadre de la plus grande solution à votre problème. Une approche commune pour trier les données qui est trop grand pour tout ajustement en mémoire est la suivante:

1) Lire les données autant que se tenir dans la mémoire principale, disons que c'est 1 Gb

2) Quicksort que 1 Gb (voici où vous devez utiliser Java de type intégré du cadre Collections)

3) Write triée 1 Gb sur le disque comme « morceau-1 »

4) Répétez les étapes 1-3 jusqu'à ce que vous avez parcouru toutes les données, en sauvegardant chaque morceau de données dans un fichier séparé. Donc, si vos données d'origine étaient 9 Go, vous aurez maintenant 9 blocs de données triés "chunk-1" à "chunk-9"

5) Vous avez juste besoin d'un tri final de fusion pour fusionner les 9 morceaux triés en un seul ensemble de données entièrement trié. Le tri par fusion fonctionnera très efficacement contre ces blocs pré-triés. Il ouvrira essentiellement 9 lecteurs de fichiers (un pour chaque morceau), plus un enregistreur de fichiers (pour la sortie). Il compare ensuite le premier élément de données dans chaque fichier lu et sélectionne la plus petite valeur, qui est écrite dans le fichier de sortie. Le lecteur à partir duquel cette valeur sélectionnée est arrivée à son élément de données suivant, et le processus de comparaison à 9 voies pour trouver la plus petite valeur est répété, en écrivant à nouveau la réponse dans le fichier de sortie. Ce processus se répète jusqu'à ce que toutes les données aient été lues dans tous les fichiers fragmentés.

6) Une fois l'étape 5 a terminé la lecture de toutes les données que vous avez terminé - votre fichier de sortie contient maintenant des données entièrement triées définies

Avec cette approche, vous pouvez facilement écrire un utilitaire « megasort » générique de votre propre cela prend un nom de fichier et un paramètre maxMemory et trie efficacement le fichier en utilisant des fichiers temporaires. Je parie que vous pourriez trouver au moins quelques implémentations là-bas pour cela, mais si non, vous pouvez simplement rouler les vôtres comme décrit ci-dessus.

Answer 2

La façon la plus courante de gérer grands ensembles de données en mémoire (vous pouvez acheter un serveur avec 1 To ces jours-ci) ou dans une base de données.

Si vous ne comptez pas utiliser une base de données (ou acheter plus de mémoire) vous pouvez écrire vous-même juste facilement.

Il existe des bibliothèques qui peuvent aider qui exécutent des fonctions Plan-Reduce mais ils peuvent ajouter plus de complexité qu'ils économisent.