trier les lignes d'un énorme fichier.TXT en java

je travaille avec un très gros fichier texte (755Mb). Je dois trier les lignes (environ 1890000) et ensuite les écrire dans un autre fichier.

j'ai déjà remarqué que la discussion qui a un fichier de départ vraiment similaire au mien: lignes de tri basées sur des mots en tant que clés

le problème est que je ne peux pas stocker les lignes dans une collection en mémoire parce que je reçois une Exception Java Heap Space (même si je l'ai étendue à maximal.).(déjà essayé!)

Je ne peux pas non plus l'ouvrir avec excel et utiliser la fonction de tri parce que le fichier est trop grand et il ne peut pas être complètement chargé..

j'ai pensé à utiliser un DB ..mais je pense que l'écriture de toutes les lignes puis utiliser la requête SELECT c'est trop long en termes de temps d'exécution..est-ce que je me trompe?

tous les conseils appréciés Merci d'avance

7
demandé sur Community 2012-01-12 13:38:08

6 réponses

je pense que la solution ici est de faire un tri de fusion en utilisant des fichiers temporaires:

  1. lire les premières lignes n du premier fichier, ( n étant le nombre de lignes que vous pouvez vous permettre de stocker et trier en mémoire), les trier et les écrire au fichier 1.tmp (ou comment vous l'appelez). Faites de même avec les lignes suivantes n et conservez-les dans 2.tmp . Répétez jusqu'à ce que toutes les lignes de le fichier d'origine a été traitée.

  2. Lire la première ligne de chaque fichier temporaire. Déterminez le plus petit (selon votre ordre de tri), écrivez-le dans le fichier de destination, et lisez la ligne suivante du fichier temporaire correspondant. Répéter jusqu'à ce que toutes les lignes aient été traitées.

  3. Supprimer tous les fichiers temporaires.

cela fonctionne avec arbitraire gros fichiers, tant que vous avez assez d'espace disque.

15
répondu celtschk 2012-01-12 09:44:09

vous pouvez exécuter ce qui suit avec

-mx1g -XX:+UseCompressedStrings  # on Java 6 update 29
-mx1800m -XX:-UseCompressedStrings  # on Java 6 update 29
-mx2g  # on Java 7 update 2.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String... args) throws IOException {
        long start = System.nanoTime();
        generateFile("lines.txt", 755 * 1024 * 1024, 189000);

        List<String> lines = loadLines("lines.txt");

        System.out.println("Sorting file");
        Collections.sort(lines);
        System.out.println("... Sorted file");
        // save lines.
        long time = System.nanoTime() - start;
        System.out.printf("Took %.3f second to read, sort and write to a file%n", time / 1e9);
    }

    private static void generateFile(String fileName, int size, int lines) throws FileNotFoundException {
        System.out.println("Creating file to load");
        int lineSize = size / lines;
        StringBuilder sb = new StringBuilder();
        while (sb.length() < lineSize) sb.append('-');
        String padding = sb.toString();

        PrintWriter pw = new PrintWriter(fileName);
        for (int i = 0; i < lines; i++) {
            String text = (i + padding).substring(0, lineSize);
            pw.println(text);
        }
        pw.close();
        System.out.println("... Created file to load");
    }

    private static List<String> loadLines(String fileName) throws IOException {
        System.out.println("Reading file");
        BufferedReader br = new BufferedReader(new FileReader(fileName));
        List<String> ret = new ArrayList<String>();
        String line;
        while ((line = br.readLine()) != null)
            ret.add(line);
        System.out.println("... Read file.");
        return ret;
    }
}

imprime

Creating file to load
... Created file to load
Reading file
... Read file.
Sorting file
... Sorted file
Took 4.886 second to read, sort and write to a file
2
répondu Peter Lawrey 2012-01-12 10:55:46

algorithme:

combien de mémoire avons-nous? Supposons que nous ayons X MB de mémoire disponible.

  1. diviser le fichier en K morceaux, où X * K = 2 GB . Mettez chaque morceau en mémoire et triez les lignes comme d'habitude en utilisant n'importe quel algorithme O(n log n) . Enregistrer les lignes dans le fichier.

  2. apportez maintenant le morceau suivant dans la mémoire et le tri.

  3. une fois que nous avons terminé, fusionnez-les un par un.

l'algorithme ci-dessus est également connu sous le nom de tri externe. L'étape 3 est connue sous le nom de n-way merge

1
répondu e-zinc 2012-01-12 09:57:24

diviser pour mieux régner est la meilleure solution:)

divisez votre fichier en plus petits, triez chaque fichier séparément puis regroupez-vous.

Liens

Trier un fichier avec un volume énorme de données contrainte de mémoire donnée

http://hackerne.ws/item?id=1603381

0
répondu Adel Boutros 2017-05-23 11:47:32

pourquoi n'essayez-vous pas le multithreading et l'augmentation de la taille du tas du programme que vous exécutez? (cela nécessite également que vous utilisiez la sorte de fusion de sorte de chose pourvu que vous ayez plus de mémoire que 755mb dans votre système.)

0
répondu javaCity 2012-01-12 09:52:13

peut-être que vous pouvez utiliser perl pour formater le fichier .et charger dans la base de données comme mysql. c'est tellement rapide. et utiliser l'index pour interroger les données. et écrire dans un autre fichier.

u peut définir la taille de tas jvm comme '- Xms256m-Xmx1024m' .j'espère contribuer à l'u .merci

-2
répondu Eric.Sun 2012-01-12 09:49:52