righe di ordinamento di un file.txt enorme in java

Question

Sto lavorando con un file di testo molto grande (755 Mb). Ho bisogno di ordinare le linee (circa 1890000) e poi scriverle in un altro file.

ho già notato che la discussione che ha un file di partenza davvero simile al mio: Sorting Lines Based on words in them as keys

Il problema è che non riesco a memorizzare le linee in una collezione in memoria perché ho un eccezione Java Heap spazio (anche se ho ampliato è al massimo) .. (già provato!)

non possibile aprire con Excel e utilizzare la funzionalità di ordinamento perché il file è troppo grande e non può essere completamente caricato ..

I pensato di usare un DB ... ma penso che scrivere tutte le righe poi tu se la query SELECT è troppo lunga in termini di esecuzione del tempo..am mi sbaglio?

Eventuali suggerimenti apprezzato Grazie in anticipo

Answer 1

Penso che la soluzione è quella di fare un merge sort utilizzando i file temporanei:

1. Leggi le prime n righe del primo file, (n indica il numero di righe che puoi permetterti di memorizzare e ordinare in memoria), ordinale e scrivile nel file 1.tmp (o comunque lo chiami). Fai lo stesso con le prossime linee n e memorizzalo in 2.tmp. Ripeti fino a quando tutte le righe del file originale sono state elaborate.

2. Leggere la prima riga di ciascun file temporaneo. Determina il più piccolo (in base al tuo ordine), scrivilo nel file di destinazione e leggi la riga successiva dal file temporaneo corrispondente. Ripeti fino a quando tutte le linee sono state elaborate.

3. Elimina tutti i file temporanei.

Questo funziona con file grandi e arbitrari, purché lo spazio su disco sia sufficiente.

Answer 2

Perché non provi multithreading e aumentare dimensione heap del programma è in esecuzione? (Questo richiede anche di utilizzare merge sort tipo di cosa purché si disponga di più memoria di 755mb nel sistema.)

Answer 3

divide and conquer è la soluzione migliore :)

dividere il file in quelle più piccole, specie ogni file separatamente poi riorganizzarsi.

vicini:

Sort a file with huge volume of data given memory constraint

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

Answer 4

Algoritmo:

Quanta memoria facciamo abbiamo a disposizione? Supponiamo di avere X MB di memoria disponibile.

1. dividere il file in K pezzi, dove X * K = 2 GB. Porta ogni chunk in memoria e ordina le linee come al solito usando qualsiasi algoritmo O(n log n). Salva le righe sul file.

2. Ora porta in memoria il prossimo blocco e ordina.

3. Una volta terminato, unirli uno alla volta.

L'algoritmo di cui sopra è anche noto come ordinamento esterno. Il passaggio 3 è noto come N-way merge

Answer 5

Forse si può usare perl per formattare il file e caricarlo nel database come mysql. è così veloce e usare l'indice per interrogare i dati. e scrivere in un altro file.

u possibile impostare la dimensione heap JVM come .i '-Xms256m Xmx1024m' sperano di aiutare u .thanks

Answer 6

è possibile eseguire il seguente con

-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; 
    } 
} 

stampe

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