Geht das effizienter?: Einlesen > Duplikate entf > Spe

  • Themenstarter Themenstarter Guest
  • Beginndatum Beginndatum
Status
Nicht offen für weitere Antworten.
G

Guest

Gast
Hi,

ich habe lange im Internet nach einem Programm gesucht, dass sehr große Textdateien (100 MB+) einlesen, Duplikate entfernen, und das Ganze wieder speichern kann.
Da ich nichts passendes gefunden habe, habe ich mir selbst was geschrieben.

Folgende Aufgaben sollen erledigt werden:
1. Effizient aus Datei einlesen (RAM Verbrauch steigt bei 100 MB Datei auf 700 MB)
2. Duplikate entfernen
3. Optional Datei sortieren
4. Ergebnis in neue Datei speichern


Eine TextDatei sieht ca. so aus:
Auto
laufen
Hund
laufen
Auto
Schmuck
Zeitung
...

Hier mein bisheriges Programm:
Code:
public class Main {
	private static final String INPUT_FILE = "1u2.txt";
	private static final String OUTPUT_FILE = "out.txt";
	
	public void writeFile(String filename, List<String> list){
		BufferedWriter b = null;
        try {
			b = new BufferedWriter (new FileWriter (filename));
			for(int i=0;i<list.size();i++){
				b.write(list.get(i));
				b.newLine();
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		finally{
			try {
				b.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
	
	public List<String> readFile(String filename) {
		List<String> list = new ArrayList<String>();
		String line = "";
		try {
			FileReader file = new FileReader(filename);
			BufferedReader data = new BufferedReader(file);
			while ((line = data.readLine()) != null) {
				list.add(line);
			}
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		} catch (IOException e2) {
			e2.printStackTrace();
		}
		return list;
	}
	
	public List<String> sortFile(List<String> list){
		Collections.sort(list);
		return list;
	}
	
	public void print(List<String> list){
		for(int i=0;i<list.size();i++){
			System.out.println(list.get(i));
		}
	}
	
	public List<String> removeDuplicates(List<String> list){
		Set<String> set = new HashSet<String>();
		set.addAll(list);
		list.clear();
		list.addAll(set);
		return list;
	}

	public static void main(String[] argv){
		Main main = new Main();
		List<String> list = main.readFile(INPUT_FILE);		// einlesen	
		list = main.removeDuplicates(list);					// duplikate entfernen
		list = main.sortFile(list);							// sortieren
		//main.print(list);									// optional ausgeben
		main.writeFile(OUTPUT_FILE, list);					// in datei schreiben
	}
}


Wo kann man dort noch etwas optimieren?
 
Ich habe deine Methode Readfile mal ein wenig geändert. Sie entfernt jetzt gleich die Duplikate und sortiert wird auch automatisch. Zeitkomplexität ist O(n log n). Und da nicht alles hin und her kopiert wird sollte es auch weniger Speicher brauchen. Hab allerdings gerade keine 100mb-textdatei zum testen. Bei google solltest du auch noch andere SortedSet-Implementierungen finden können, die vielleicht schneller sind.

Code:
   public SortedSet<String> readFile(String filename) { 
      SortedSet<String> ss = new TreeSet<String>(); 
      String line = ""; 
      try { 
         FileReader file = new FileReader(filename); 
         BufferedReader data = new BufferedReader(file); 
         while ((line = data.readLine()) != null) { 
            ss.add(line); 
         } 
      } catch (FileNotFoundException e1) { 
         e1.printStackTrace(); 
      } catch (IOException e2) { 
         e2.printStackTrace(); 
      } 
      return ss; 
   }
 
sicherlich lohnt es sich auch noch, die Datei als byte[] einzulesen, immer 50k Bytes,
darin nach den Byte(s) für den Zeilenumbruch zu suchen und dann selber jede Zeile als byte[] anzulegen,
diese dürften kleiner sein als Strings,
mit entsprechenden Comparator aber genauso gut zu vergleichen,

ist dann eher low-level und vielleicht in Java nicht richtig angesiedelt, aber zumindest (hoffentlich) performanter 😉
 
Kim Stebel hat gesagt.:
Ich habe deine Methode Readfile mal ein wenig geändert.
Vielen Dank! Das ist sehr viel schneller! :applaus:

Mein einziges Problem ist jetzt noch der Arbeitsspeicher. Ich bekomme bei Dateien ab 200 MB eine
java.lang.OutOfMemoryError: Java heap space

Wie könnte man das vielleicht speichereffizienter gestalten?
Das Problem ist ja, dass Zeile für Zeile in ein(e) Liste/Set geschoben wird und das dynamisch wächst.
 
siehe mein Post, um ein bisschen Speicher zu sparen,
irgendwann ist aber jeder Speicher voll, musst die Datei nur oft genug vergrößern 😉

in dem Fall musst du die Datei in Teilen bearbeiten, z.B.
erst MB 1-100 laden und sortieren und doppelte entfernen, in eine zweite Datei schreiben,
dann MB 100-200 genauso und hinten ran anfügen oder auch separat speichern, Hauptsache du weißt immer wo alles ist 😉

dann als nächstes die Teile verschränken,
z.B. MB 50-100 und 100-150, also 50-150 laden und sortieren,
danach dürften ja einige Wörter aus dem 100-150-Bereich nach 50-100 gewandert sein und umgekehrt,
als nächstes wieder 1-100 sowie 100-200 für sich sortieren,
dann wieder die Mitte 50-150 usw. bis irgendwann mal beim Vergleich der Mitte gar nix mehr zu sortieren ist,
zu dem Zeitpunkt ist die gesamte Datei sortiert,

bei mehr als drei Teilen muss man ähnlich entsprechend arbeiten,
mit bisschen Nachdenken oder Nachschlagen gibts da vielleicht auch noch intelligentere Verfahren,

am beste wäre ja, alles in eine DB zu schreiben, und diese sortieren zu lassen,
die hat gewiss sehr viel Ahnung davon
 
SlaterB hat gesagt.:
siehe mein Post, um ein bisschen Speicher zu sparen,
irgendwann ist aber jeder Speicher voll, musst die Datei nur oft genug vergrößern 😉

Hab ich gelesen, denke nur nicht dass das soooo viel Speicher einspart, denn wie du schon sagst, irgendwann ist auch der größte Speicher voll. Hab hier nur 2 GB.

SlaterB hat gesagt.:
am beste wäre ja, alles in eine DB zu schreiben, und diese sortieren zu lassen,
die hat Gewiss sehr viel Ahnung davon

Die Idee finde ich sehr gut, nur wie sortiert eine DB ? Schon beim Einfügen? Oder beim Abfragen? Und wieviel Speicher braucht die DB zum Sortieren?
 
die DB sortiert nicht beim Einfügen, eine Tabelle mit mehreren Attributen könnte man eh auf sehr viele Reihenfolgen bringen,

Sortieren wird sie sicherlich so wie du im entfernten Sinne, bzw. so wie ich vorgeschlagen habe nur eben besser mit Wissen auf dicken Büchern in effizienten Algorithmen

je weniger Speicher, desto länger dauerts eben, da gibts wohl keine Grenze,
wieviel der DB zur Verfügung steht ist Konfigurationssache wie bei allen Programmen
(genaues kann ich zu all dem nicht sagen)
 
noch eine Idee: du schaust dir zu jeder Zeile die ersten X Buchstaben an, z.b. nur den ersten, und speicherst das Wort dann in die A-Datei oder B-Datei oder ... (26 Streams offen)

dann hast du nach diesem ersten Schritt 26 kleinere Dateien, die du gut einzeln bearbeiten und später einfach zusammenfügen kannst
 
du musst beim start der jvm nen parameter übergeben, der die maximale heap-größe bestimmt....
das hatten wir hier im forum schon 100 mal...
wenn das nicht reichen sollte kannst du dich ja noch mal melden...
der vorschlag von slaterb ist natürlich auch gut, nur umständlicher zu implementieren. 😉
 
SlaterB hat gesagt.:
noch eine Idee: du schaust dir zu jeder Zeile die ersten X Buchstaben an, z.b. nur den ersten, und speicherst das Wort dann in die A-Datei oder B-Datei oder ... (26 Streams offen)

dann hast du nach diesem ersten Schritt 26 kleinere Dateien, die du gut einzeln bearbeiten und später einfach zusammenfügen kannst

Die Idee werde ich gleich mal probieren, nachdem ich das mit der DB probiert hab. Danke!
 
wäre es nicht schlauer, den ganzen Thread (bzw. die erste Antwort) zu lesen und zu bemerken, dass diese Erkenntnis bereits erlangt wurde? 😉
 
Status
Nicht offen für weitere Antworten.

Neue Themen


Zurück
Oben