Tri d'un fichier tres volumineux

Bonjour !
Alors, je vous explique mon problème :
Pour trier un fichier, ce que je faisait avant etait simple, je recupere les entiers de mon fichier dans une arraylist et je trie simplement avec sort


Mais mon problèeme, c'est que les fichiers que je devrai lire peuvent etre tres tres volumineux , et ne tiennent plus en mémoire lorsqu'on les stocke dans des arraylist :?

D'ou ma question : que préconisez vous pour remédier à ce problème ?
J'ai aussi pensé à couper le fichier en plusieurs petits morceaux, les trier et les fusionner, mais le problème est justement la fusion

Merci d'avance pour votre réponse

je ne sais pas trop, mais je pense que java n'est pas le maitre dans ce domaine.

Peut etre que tes perf et la memoire se porteraient mieux en utilisant un script perl par exemple ...

Sinon pour le faire en java, à part comme tu dis, découper, trier, fusionner je vois pas trop. Par contre, même si tu fonctionne par fusion successive, à un moment ou à un autre (la dernière fusion) tu va avoir besoin en mémoire de toutes les valeurs ... ce qui revient à ton problème de départ ...

Citation:

---

Envoyé par in

Par contre, même si tu fonctionne par fusion successive, à un moment ou à un autre (la dernière fusion) tu va avoir besoin en mémoire de toutes les valeurs ... ce qui revient à ton problème de départ ...

---

Oui le problème est justement là :?
et pour l'instant, je n'ai pas eu d'idée vraiment géniale pour y remédier :cry:

Bonsoir,

Il y aurait eu plus de réponses sur le forum algo ;)

Tu dois utiliser un tri externe. Renseigne toi sur le tri par fusion naturelle.

bon courage.

Salut,

Par curiosité : quel est la taille de ces fichiers ? Et comment tu les lis ?

a++

ce que tu peux faire sinon c'est utiliser ton fichier à trier en lecture et considérer chacunes de ses lignes commes leséléments d'un tableau.

Aces la classe RandomAccesFile tu peux accéder à n'importe quelle ligne sans trop de souci, ce que tu peux donc faire est considérer un tri qui trie soit par le début, soit par la fin (car l'écritures dans les fichiers n'est pas dynamique i.e. tu peux pas écrire à la ligne 2 sans effacer tout le contenu) et à chaque fois que tu possède un élément que tu sais trié tu l'écris dans le deuxièe fichier. Je pense par exemple au tri par tas,de complexité n log n et qui trie par la fin. Ce qui va passer en mémoire sera donc la seule ligne du fichier considérée, ça devrait aller.
Un inconvéniant majeur néanmoins : parcourir tout le tems le fichier source, et écrire à chaque fois dans le fichier cible le nouvel élément va considérablement ralentir le programme à cause de la faible vitesse des IO.

Bon à mon avis ça devrait marcher ce que je te dis là, mais j'en suis pas vraiment sur, tape pas si ça foire lol;)

Saloutre,

Perso je serais parti sur ton idée de splitter le fichier en plusieurs plus petits fichiers que tu tries en utilisant l'algo que tu veux ... tri rapide par exemple.

Ensuite tu as plusieurs fichiers, tous triés et tu dois les fusionner, certes. Je ne vois pas où est le problème à partir du moment où au lieu de conserver le résultat en RAM (dans une liste) tu écris au fur et à mesure dans un fichier ...

Je m'explique :

1. Ouvrir des flux de lecture sur chaque fichier trié
2. Ouvrir un flux d'écriture sur un fichier (la fusion de tous les fichiers)
3. Lire le première ligne de chaque fichier trié
4. Sélectionner la plus petite valeur parmi celles lues dans les fichiers triés (ou plus grande, selon le tri) et lire la ligne suivante du fichier
5. Ecrire la valeur dans le fichier de sortie
6. Retourner en 4 tant qu'il reste des lignes dans les fichiers

Je sais pas si tu me suis ... mais en gros, t'as quasi pas besoin de RAM pour faire ça .. par contre ça risque de traîner un peu car bcp de lecture/écriture sur le disque ... mais bon, on peut pas tout avoir !

A+ bon dév :)