# einfache Filterung optimieren



## donchris (4. Jan 2011)

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 (4. Jan 2011)

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 (4. Jan 2011)

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:


SlaterB hat gesagt.:


> 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 (4. Jan 2011)

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 (4. Jan 2011)

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 (4. Jan 2011)

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


----------



## Empire Phoenix (4. Jan 2011)

nrg hat gesagt.:


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



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 (4. Jan 2011)

nrg hat gesagt.:


> 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 (4. Jan 2011)

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


----------



## donchris (5. Jan 2011)

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 (5. Jan 2011)

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 (5. Jan 2011)

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 (5. Jan 2011)

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 (5. Jan 2011)

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 (5. Jan 2011)

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 (5. Jan 2011)

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 (5. Jan 2011)

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


----------

