Geht das effizienter?: Einlesen > Duplikate entf > Spe

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?
 

Kim Stebel

Bekanntes Mitglied
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; 
   }
 
S

SlaterB

Gast
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 ;)
 
G

Guest

Gast
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.
 
S

SlaterB

Gast
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
 
G

Guest

Gast
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?
 
S

SlaterB

Gast
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)
 
S

SlaterB

Gast
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
 

Kim Stebel

Bekanntes Mitglied
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. ;)
 
G

Guest

Gast
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!
 
S

SlaterB

Gast
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.
Ähnliche Java Themen
  Titel Forum Antworten Datum
D MacOS: PDF erstellen geht nicht Java Basics - Anfänger-Themen 1
P Netbeans installation geht nicht Java Basics - Anfänger-Themen 26
Ostkreuz wie geht der catch? Java Basics - Anfänger-Themen 3
A Methoden Guten Tag , ich wollte so machen dass wenn meine frog an eine fly/bee geht dann an meine Tafel geht der zahl +1 hoch. Java Basics - Anfänger-Themen 2
S IntelliJ geht alle Klassen durch Java Basics - Anfänger-Themen 9
B Explizit Array definieren geht nicht? Java Basics - Anfänger-Themen 14
Say Stelle in Code herausfinden, wie geht man vor? Java Basics - Anfänger-Themen 12
berserkerdq2 Geht collections.sort bei allen? Linkedhashset, ArrayList, HashSet etc. Java Basics - Anfänger-Themen 4
P Installation JRE 8u321 startet, geht aber nicht weiter Java Basics - Anfänger-Themen 1
E Rekursiv Objekte erzeugen - geht das? Java Basics - Anfänger-Themen 2
E Pervasive PSQL insert funktion geht nicht Java Basics - Anfänger-Themen 9
U Warum kann ich die Methode in der ENUM Klasse nicht aufrufen? Und warum geht die Switch nicht? Java Basics - Anfänger-Themen 8
H Wie geht eigentlich Objektorientierung? Java Basics - Anfänger-Themen 14
M Methoden Wert einer Variable geht verloren? Java Basics - Anfänger-Themen 6
melisax Lower & Uppercase Beispielprogramm geht nicht Java Basics - Anfänger-Themen 3
MarcKKKK123 Wie geht das? Java Basics - Anfänger-Themen 1
B Static Attribute in einer Klasse, wie geht das? :O Java Basics - Anfänger-Themen 19
N methodenaufruf for each geht nicht Java Basics - Anfänger-Themen 2
O Methode in while-Schleife aufrufen geht nur beim ersten Mal Java Basics - Anfänger-Themen 2
W App geht live und dann? Java Basics - Anfänger-Themen 9
P Geht es vielleicht viel kürzer? Java Basics - Anfänger-Themen 7
S While-Schleife geht in Endlosschleife über, warum? Java Basics - Anfänger-Themen 6
B Interface List - Objekt übergeben? Einzelnes Objekt geht, aber Liste nicht? Java Basics - Anfänger-Themen 4
K Erste Schritte Programm geht aus Schleife, warum? Java Basics - Anfänger-Themen 2
S Geht das bei Java ? Java Basics - Anfänger-Themen 11
L Wie geht man bei mehreren Action Klassen vor? Java Basics - Anfänger-Themen 0
C unverständlicher Code Attribute ohne Datentyp, wie geht das? Java Basics - Anfänger-Themen 8
B OCR - Rechnungserkennung, wie geht das genau? Java Basics - Anfänger-Themen 59
CptK Klassen KeyListner geht nicht Java Basics - Anfänger-Themen 7
L Klassen Objekt aus einer Warteschlange in eine andere übergeben, geht nicht? Java Basics - Anfänger-Themen 6
K Armstrong Programm geht nur bis 1000, aber nicht weiter Java Basics - Anfänger-Themen 2
M Nim-Spiel geht in den negativen Bereich Java Basics - Anfänger-Themen 1
amazinglife77 Input/Output Lesen/Schreiben Properties: in eclipse geht, als JAR nicht Java Basics - Anfänger-Themen 4
V Erste Schritte Warum geht meine continue Anweisung nicht? Java Basics - Anfänger-Themen 8
MR._FIRE_Flower String.split("(") geht nicht Java Basics - Anfänger-Themen 4
M Restbuchwert Berechnung geht nicht Java Basics - Anfänger-Themen 45
K Klassen Nachträglich ein Objekt einem anderen zuweisen, geht das? Java Basics - Anfänger-Themen 2
S int addieren geht nicht Java Basics - Anfänger-Themen 13
L system.print.out geht nicht Java Basics - Anfänger-Themen 11
M Referenz geht bei Zwischenspeichern verloren (ArrayList) Java Basics - Anfänger-Themen 4
S Komma geht beim Schreiben ins csv verloren. Java Basics - Anfänger-Themen 6
M Arrays einspeichern geht nicht Java Basics - Anfänger-Themen 21
J BlueJ und import-Anweisungen, wie geht das? Java Basics - Anfänger-Themen 4
J Geht mit Java überhaupt was? Java Basics - Anfänger-Themen 13
J Debuggen - wie geht das? Java Basics - Anfänger-Themen 6
I erstelle Vorschaubild mit der lib PDF-Renderer und möchte danach Dateiname ändern -> geht aber nicht Java Basics - Anfänger-Themen 0
J Ausführen geht nicht Java Basics - Anfänger-Themen 19
G System.out.printf geht nicht Java Basics - Anfänger-Themen 6
E Erste Schritte [Noob] Warum geht meine For-Schleife nicht? Java Basics - Anfänger-Themen 2
I Java Code so gut es geht Kommentieren Java Basics - Anfänger-Themen 4
S Button "Berechnen" geht nicht Java Basics - Anfänger-Themen 3
B Compiler-Fehler Ein Java-Eclipse-Anfänger geht auf Reisen... Java Basics - Anfänger-Themen 10
K JUnit: Objekte von eigenen Klassen vergleichen...geht nicht Java Basics - Anfänger-Themen 5
T fianl array geht nicht... Java Basics - Anfänger-Themen 2
O if and else geht nur manchmal Java Basics - Anfänger-Themen 17
B Nichts geht mehr Java Basics - Anfänger-Themen 10
D Java geht auf windows 64 bit nicht. Java Basics - Anfänger-Themen 5
V Einfacher vergleich von Arrays geht schief Java Basics - Anfänger-Themen 2
T sample.war geht nicht... Java Basics - Anfänger-Themen 1
Thallius Klassen aus Classname programmatisch erzeugen. Wie geht das in java? Java Basics - Anfänger-Themen 5
C Datentypumwandlung geht nicht Java Basics - Anfänger-Themen 5
U kompilieren geht nicht wg. Formatierung wahrscheinlich Java Basics - Anfänger-Themen 7
G While schleife mit 2 Bedingungen geht nicht! Java Basics - Anfänger-Themen 15
S Methoden Rückgabewert einer Methode als Parameter an eine andere Methode übergeben, geht das? Java Basics - Anfänger-Themen 5
L Das erste Mal GridBagLayout - wie geht das? Java Basics - Anfänger-Themen 5
O Jar Datei erstellen geht nicht. Java Basics - Anfänger-Themen 4
O (.+?) --> $1 geht nicht Java Basics - Anfänger-Themen 5
V relativer Pfad geht nicht, absolut schon? Java Basics - Anfänger-Themen 3
R Java JDK/ Kompiler geht nicht Java Basics - Anfänger-Themen 4
H Geht dieser Code noch einfacher (try catch finally) Java Basics - Anfänger-Themen 7
P Geht dieser Code noch einfacher? Java Basics - Anfänger-Themen 16
J Warum geht int und String nicht? Java Basics - Anfänger-Themen 18
J repaint() geht gar nicht; GUI aktualisieren Java Basics - Anfänger-Themen 10
N ArrayList geht nicht Java Basics - Anfänger-Themen 8
B Erste Schritte Listing aus Buch - wie geht das? Java Basics - Anfänger-Themen 6
K Datentypen Kurzform Addition geht, Langform scheitert am Typen Java Basics - Anfänger-Themen 6
R Einfacher Timer geht nicht Java Basics - Anfänger-Themen 7
J Anzeige erneuern, wie geht das? Java Basics - Anfänger-Themen 6
D Compiler-Fehler ANT-Script geht nicht Java Basics - Anfänger-Themen 6
A Android Datenbank gaaanz einfaches Insert geht nicht - warum? Java Basics - Anfänger-Themen 4
N JAVA Installation - Umgebungsvariable geht nicht. Java Basics - Anfänger-Themen 3
K Aus JFrame-Fenster SuM-Fenster öffnen geht nicht! Java Basics - Anfänger-Themen 8
L Jarfiles packen, wie geht's genau? Java Basics - Anfänger-Themen 12
K Erste Schritte Progressbar geht nicht Java Basics - Anfänger-Themen 5
H Ein alternativer Konstruktor geht nicht Java Basics - Anfänger-Themen 3
B Std-Serialisierung - Speichern/Laden geht nur auf einem Rechner Java Basics - Anfänger-Themen 17
F Geht in alle Case rein, warum?? Java Basics - Anfänger-Themen 12
El_Lobo Methoden Zu viele Getter- und Settermethoden - geht das einfacher? Java Basics - Anfänger-Themen 3
P quickSort eines Objekt-Arrays geht nicht! Java Basics - Anfänger-Themen 11
M if then else geht nicht Java Basics - Anfänger-Themen 10
N Methoden mehrere replace hintereinander geht nicht ? Java Basics - Anfänger-Themen 2
Maxim6394 KeyListener geht nicht Java Basics - Anfänger-Themen 15
C Erste Schritte switch Anweisung geht nicht Java Basics - Anfänger-Themen 3
N geht oder geht nicht? Java Basics - Anfänger-Themen 24
E bo wie geht das denn? Java Basics - Anfänger-Themen 8
Z Anfügen an Arraylist geht nicht Java Basics - Anfänger-Themen 3
M Unterverzeichnisse löschen geht nicht. Java Basics - Anfänger-Themen 3
T Methoden Array kopieren: Wie geht das? Java Basics - Anfänger-Themen 20
M If Abfrage geht nicht Java Basics - Anfänger-Themen 2
0 file.delete() geht nicht Java Basics - Anfänger-Themen 23

Ähnliche Java Themen


Oben