einfache Filterung optimieren

[donchris]

Hallo

ich habe für ein universitäres Projekt eine riesige Datenmenge (Textdateien von rund 10GB) die ich filtern muss. Es geht darum, dass sich in der Datei ein Menge an Stichwörtern befindet, die ich aussortieren möchte.

Mir würden zwei Methoden einfallen:

1#
Mit einem Scanner (input per pipe) Wort für Wort mit einer Art Blacklist vergleichen und ausgeben/speichern/etc

2#
Einlesen mit Regex - replaceAll und wieder einer Blacklist

Doch welche Methode wäre bei einer großen Datenmenge schneller? Ich habe bereits einen Filter per Regex/replaceAll programmiert, doch dieser benötigt ~50 Minuten für 300 MB (bei einem Intel QuadCore 2,4Ghz ohne GUI)

Arbeitsspeicher wäre genug vorhanden (8GB). Würden sich noch andere Methoden anbieten? Wie könnte man noch weiter optimieren.

mfg
chris

 

[SlaterB]

allgemein ist es gut möglich, dass die Zeit an ganz anderer Stelle verloren geht, String + String z.B.,
StringBuilder kann da Wunder vollbringen,

edit: oder auch Einlesen/ Schreiben ohne Buffer

----

bei RegEx ist es günstig, das Pattern nur einmal zu erstellen,
allgemein ist replaceAll() zeitlich allen manuellen geschickten String-Manipulationen unterlegen

poste doch bisschen Code

 

[nrg]

also Regex sollte wohl imho das langsamste sein. Sehe ich das jetzt richtig, dass du eine Blacklist an Wörtern hast, die du einfach rausschmeissen möchtest?

Blacklist:
ich, test, welt

Datei davor:
[c]ich schreibe ein hallo welt programm. test[/c]

Datei danach:
[c] schreibe ein hallo programm. [/c]

es gibt ja auch einen replace ohne RegEx. Die Frage ist, ob du wirklich Reguläre Ausdrücke verwendest.

edit: @ Slater:

allgemein ist es gut möglich, dass die Zeit an ganz anderer Stelle verloren geht, String + String z.B.,
StringBuilder kann da Wunder vollbringen,

das Thema hatten wir doch schon öfters und wird doch vom Compiler optimiert. Also sowas dürfe jetzt nicht der Flaschenhals sein. (wobei ich es auch für guten Stil halte das mit SB zu machen - aus Performancesicht aber afaik unbedeutend)

 

[donchris]

Bezüglich Strings habe ich keine Sorge, da hier kaum welche verwendet werden (es wird direkt ausgegeben und die Ausgabe wird per pipe in eine Datei umgeleitet). Intern wird zwar ein String verwendet, doch dieser wird immer nur referenziert, kaum geändert und schließlich ausgegeben.

Ja ich habe genau so eine Blacklist gemeint. Im Moment habe ich eine List. Per Scanner würde ich dann

if(blacklist.contains(word=sc.next()){
//blabla
}

Die Ein/Ausgabe würde ich per Pipes über die Standard Ein/Ausgabe machen. Könnte man das noch verbessern, oder habe ich hier keinen "Flaschenhals" mehr übrig?

 

[nrg]

les doch einfach alles mit einem bufferedreader in eine liste ein und dann iteriere drüber. nun machst du für jede zeile ein replace mit jedem element aus deiner blacklist.

 

[SlaterB]

ein einfacher Test ist, das replaceAll() oder sonstige Änderungen wegzulassen und die Daten nur durchzureichen,
welche Geschwindigkeit wird dann erreicht?

 

[Empire Phoenix]

also Regex sollte wohl imho das langsamste sein. Sehe ich das jetzt richtig, dass du eine Blacklist an Wörtern hast, die du einfach rausschmeissen möchtest?

Blacklist:
ich, test, welt

Datei davor:
[c]ich schreibe ein hallo welt programm. test[/c]

Datei danach:
[c] schreibe ein hallo programm. [/c]

es gibt ja auch einen replace ohne RegEx. Die Frage ist, ob du wirklich Reguläre Ausdrücke verwendest.

edit: @ Slater:


das Thema hatten wir doch schon öfters und wird doch vom Compiler optimiert. Also sowas dürfe jetzt nicht der Flaschenhals sein. (wobei ich es auch für guten Stil halte das mit SB zu machen - aus Performancesicht aber afaik unbedeutend)

Ja wird es aber leider in der praxis bei mir zumindest nicht. Hatte das Problem erst neulich weil ich mich auf automatische optimierung verlassen habe.


Abgesehen davon ein ab und zu veränderter risiger String kann schon durchaus performance verbrauchen, da die dinger ja immutable sind und jedes mal für den neuen Speicher allociert werden muss.

 

[SlaterB]

edit: @ Slater:


das Thema hatten wir doch schon öfters und wird doch vom Compiler optimiert. Also sowas dürfe jetzt nicht der Flaschenhals sein. (wobei ich es auch für guten Stil halte das mit SB zu machen - aus Performancesicht aber afaik unbedeutend)

hab ich auch erst jetzt gesehen, da gibt es nichts zu unterschätzen,
wenn der Code

String fertig = "";
for (..) {
  String line = readLine();
  // bearbeite line
  fertig += line; // Zeile für Zeile bis 300 MB
}

lautet, dann ist das genau eine Möglichkeit, aus 30 sec 50 Min. zu machen,
das optimiert auch kein Compiler

 

[nrg]

achso. ich dachte das wird immer von compiler optimiert. dann habt ihr natürlich recht

 

[donchris]

Ich habe jetzt einen Prototypen zusammengeflickt:

 class WFilter{

public static void main(String[] argv){
	
	ArrayList Blacklist = new ArrayList();
	String word=new String();
	Scanner sc= new Scanner(System.in);
	
	while (sc.hasNext()){
		
		if (!Blacklist.contains(word=sc.next())){
			System.out.print(word + " ");
		}
	}
}
}

So schaffe ich rund 116MB pro Minute, also Rund 7GB pro Stunde.

Aber hier habe ich noch ein paar Probleme:
* bei den rohen Textdateien befinden sich Html tags und die konnte ich bis jetzt nur per Regex entfernen.
* Wäre es möglich, dass man auch die "Word"-Variable verzichtet? StingBulider hätte hier relativ wenig Sinn, oder?

 

[SlaterB]

116/min klingt ja schon besser als vorher 6/min

word als Zwischenspeicherung sollte doch nicht nicht stören, new String() aber bitte in keinem Programm schreiben, = "" oder = null reicht

System.out.print(word + " ");
ist vielleicht als
System.out.print(word);
System.out.print(" ");
performanter weil dann nicht immer ein neuer String erzeugt werden muss,
aber auf dieser Micro-Ebene kann auch der zusätzliche Methodenaufruf an sich länger dauern..

generell schneller wird es hier wohl nur, wenn man auf den Scanner verzichtet, aus der Eingabe immer groß 10000er char[] liest und diese char für char durcharbeitet, ohne dass der Scanner zu jedem Wort einen String erstellen muss,

komplizierte Dinge wie <html>-Tags kann man mit entsprechenden Aufwand dann auch herausfinden, aber ob sich die Mühe lohnt?
wie sieht im Vergleich zum obigen Prototyp die Variante mit RegEx aus und ist die immer noch langsam?

 

[Marco13]

Mal ganz nebenbei: WAS dauert dir zu lange? Für eine (ggf. große) BlackList eine List zu verwenden ist schon ungünstig. Ein HashSet könnte da deutlich schneller sein...

 

[donchris]

Bez. Regex-Progrgramm: In diesem befinden sich um die 10 Regeln, die Tags, vermehrte Leerzeichen, head-bereich etc löschen.

Was ist der Unterschied zwischen:

replaceAll("\\<.*?\\>", "")

und

replaceAll("\\<.*?>", "")

das eine scheint nur xhtml tags zu verwenden, oder?

Das größte Problem ist wohl die Umwandlung von Umlauten, könnte man die vl. ohne Regex oder performanter gestalten?

Weiters müsste ich alleinstehende Zahlen entfernen. usw. Leider fehlen mir hierzu die Regex-Kenntnisse.


Ziel der Prozedur ist eigentlich, dass man aus einer Datei (txt, html, ...) [meist html] einfach eine Liste von Stichwörtern erzeugt, die im Inhalt vorkommen (und nicht in den Tags).

zB:

<head>
<meta>
</head>
<body>
<a .. >hier lang</a>
Ein wenig text <p>neuer text</p>
</body>

sollte eigentlich nur der relevante Text gefiltert werden:
Output: Ein wenig text neuer text

Mein bisheriger Code ist nur zusammengeflickt - daher wundert es mich eigentlich nicht wirklich, dass er nicht so performant ist. Aber wie könnte man so eine ausgabe schnell generieren? :bahnhof:

[EDIT] Bezüglich dem HTML -> TXT Problem werde ich mich einmal an das Ubuntuusers forum wenden, denn hier gibt es html2text (ein C++ Programm, das anscheinend sehr performant arbeitet)

 

[Marco13]

Um das HTML zu filtern, würde sich eine Bibliothek (d.h. ein HTML-Parser) anbieten - die haben solches "Text-Extrahieren" oft schon mit eingebaut, oder es läßt sich einfach(er) bauen. Relevant könnte die Frage sein, wie groß die einzelnen HTML-Dateien sind....

 

[donchris]

Die Files sind relativ klein ~2kb, doch es sind nun über 20 GB und ~925 000 Dateien. Ok, die Zahlen passen nicht wirklich zusammen, aber es gibt einige Pdfs die die Werte verfälschen.

 

[Marco13]

OK, es ging nur darum, dass es wohl ein Problem gäbe, wenn man versuchen würde, das DOM für eine "große" HTML-Datei im Speichern zu halten. Bei sowas wie Jericho HTML Parser gibt's halt schon Beispiele wie http://jericho.htmlparser.net/samples/console/src/ExtractText.java , die ziemlich nah an dem sein könnten, was du brauchst - wie's mit der Geschwindigkeit aussieht, kann ich nicht genau sagen, aber einen Versuch wäre es vielleicht wert...

 

[donchris]

Ich habe jetzt schon ein kleines Beispiel, das ich erfolgreich übersetzten, aber nur im kleinen Rahmen testen konnte.

import java.io.File;
import java.lang.StringBuilder;
import java.io.BufferedReader;
import java.io.FileReader;

import org.jsoup.Jsoup;


class HTMLex{
	
	public static void main(String [ ] args){
		String Pfad ="/home/chris/ccc/";
		String[] arguments={"html"};
		
		convertRecursively(new File(Pfad), arguments);

		
	}
	
	
	private static void convertRecursively(File file, String[] extensions) {
		File[] children = file.listFiles();
		
		StringBuilder str= new StringBuilder();
		
		if (children != null) {
			for (File child : children) {
				
				//System.out.println(child.getName());
				
				if(child.isFile()){
					
					for (String endungen: extensions){
						//System.out.println(endungen + " != " + ende);  
						if(child.getName().endsWith(endungen)){
							try{
							 System.out.println(HTMLex.extractText(new FileReader(child)));
						 } catch (Exception e){
						 }
						}
					}
					
				}
				else if(child.isDirectory()){
					convertRecursively(child, extensions);
				}
			}
    }
}
	
	
	public static String extractText(FileReader reader) {
	StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(reader);
    String line;
    String textOnly=null;
    
		try{
    while ( (line=br.readLine()) != null) {
      sb.append(line);
    }
    textOnly = Jsoup.parse(sb.toString()).body().text();
    
} catch(Exception e){
	
}
return textOnly;
  }
}