Effiziente Stringverarbeitung

mccae

Senfdazugeber
Huhu,

Ich brauch wiedereinmal Hilfe,...

Es geht um folgendes: Es ist eine Website auszulesen und der Quellcode zu analysieren. Es soll nach einem speziellen Tag gesucht werden und der Text zwischen Anfangs- und Endtag geholt werden.

Dieser Tag kann mehrfach vorkommen...
Die Website gibt aber je nach input bis zu 70000 Zeichen zurück.

Das ganze habe ich bereits hinbekommen, jedoch ist das ganze noch nicht Effizient genug. Der ganze Text wird nämlich geladen und analysiert.

Wie könnte ich nur lesen und speichern ab der ersten Occurence des Tags, bis zum Ende, und dann wieder bis zum Anfang des nächsten?!

Denn ich bin auf das Problem gestoßen, dass der Tag der mit readLine() geholt wird incomplete ist, und erst auf der naechsten Line weitergeht,...

Hier mal mein derzeitiger Code:

Java:
		URL url = new URL("http://www.domain.tld?param="+param.toString());

		BufferedReader in = new BufferedReader(new InputStreamReader(url.openStream()));
		String str = "";
		StringBuilder out = new StringBuilder();
		
		while ((str = in.readLine()) != null) {
			out.append(str);
		}
                                          in.close();

In eine Schleife wird das ganze dann durchlaufen und der StringBuilder so bearbeitet:

Java:
int ind = out.indexOf("<specialtag>");
		
if(ind<0){
	throw new NoTagException();
}
		    
out.delete(0, ind+12);
			    
ind = out.indexOf("</specialtag>");
		
if(ind<0){
	throw new EndlessException();
}
			    
out.delete(ind, ind+13);

Kann mir jemand eine Strategie vorschlagen, mit der das Auslesen effizienter funktionieren kann?!

Die Performance ist naemlich sehr schlecht.
Während den Calls von indexOf und delete Methoden des StringBuilders, der wie gesagt bis zu 70000 enthalten kann, kommt es zu inakzeptablen Aufrufzeiten die zwischen einer halben Sekunde und bis zu 5,6,7 Sekunden betragen.

Der String der oben den Wert der aktuellen Line erhält, (String str) wird ja mehrfach benutzt.

Ich weiß ja, dass trotz einer Neuzuweisung der String immer noch im Stringpool verbleibt. Der Stringpool wird afaik nicht vom GarbageCollector erfasst?!

Ich bitte um Hilfe,...

mfg
Martin Conrad Caesar
 
Ich würde spontan vorschlagen schon beim Auslesen des Streams nach dem Tag zu suchen und da eine Liste von Strings zusammen zu bauen.
 
Ich würde spontan vorschlagen schon beim Auslesen des Streams nach dem Tag zu suchen und da eine Liste von Strings zusammen zu bauen.

Huhu,

Die Idee hatte ich ja auch, nur brauche ich eine Strategie für über Absätze hinausgehende Tags die gesplitted sind.

Z.b:
Zeile 1 "<font color = red>omgwtf</font><spe"
Zeile 2 "zialtag>lorem ipsum</s"
Zeile 3 "pezial></br>blablabla"
 
Boah das willst Du wirklich selber machen?
Wenn das irgendwie wohlgeformt ist, dann probiere lieber einen XML-Parser.
Ich wollte das Ganze eigentlich mit heise.de/newsticker testen, allerdings findet dann SAX eine DTD nicht und schmeißt etwas Unschönes durch die Gegend.
Glücklicherweise gibt es wunderbare Setter wo man eine Validierung abschalten kann... (ich vermisse die XmlReaderSettings aus .Net)

Java:
public class SpezialtagParser {
	
	public static class SpecialHandler extends DefaultHandler {

		@Override
		public void characters(char[] ch, int start, int length)
				throws SAXException {
			StringBuffer str = new StringBuffer();
			while(length-->0) {
				char c=ch[start+length];
				if(false == (c==' ' || c=='\t' || c=='\n'))
					str.insert(0, ch[start+length]);
			}
			if(0 != str.length())
				indentedOutput(str.toString());
		}

		@Override
		public void endElement(String uri, String localName, String qName)
				throws SAXException {
			m_indentLevel--;
			indentedOutput("END: " + qName);
		}

		@Override
		public void startElement(String uri, String localName, String qName,
				Attributes attributes) throws SAXException {
			indentedOutput(qName);
			m_indentLevel++;
		}
		
		private void indentedOutput(String s) {
			System.out.println(times("\t", m_indentLevel) + s);
		}
		
		private String times(String other, int times) {
			StringBuffer b = new StringBuffer();
			while(times-->0)
				b.append(other);
			return b.toString();
		}
		
		private int m_indentLevel=0;
	
	}
	
	public static void main(String[] args) throws Exception {
		SAXParserFactory spf = SAXParserFactory.newInstance();
		SAXParser sp = spf.newSAXParser();
		FileInputStream fis = new FileInputStream(new File("special.xml"));
		sp.parse(fis, new SpecialHandler());
	}
	
}

Das ist sog. XML Push Parsing (der Parser pusht das Zeug zum Handler).
Eventuell kann mich jemand aufklären was zur Zeit State of the Art ist bei XML-Verarbeitung unter Java? ;-)
 
Zuletzt bearbeitet von einem Moderator:
Moin,

also ein StringBuilder mit 70000 Zeichen sollte auf einem normalen PC (ich hab es auf einem CoreDuo mit 2.5 GHz und 4 GB Hauptspeicher und Java 6 von Sun laufen lassen) nicht zu solch hohen Laufzeiten führen, das ist eher Kindergeburtstag (also die 70000 Zeichen). Aber fangen wir von vorne an.

Du benutzt tatsächlich eine Schleife so wie Du sie gepostet hast? Da würde dann aber nicht das von dir gewünschte Ergebniss, also die Werte zwischen zwei Tags, rauskommen. Deine Code schneidet alles ab Start inklusive dem Starttag raus, und entfernt dann noch den Endtag. Dein StringBuilder enthält jetzt den Wert zwischen den Tags gefolgt vom Resttext. Wenn Du den StringBuilder dann erneut bearbeitest, sucht er wieder den ersten Tag und schneidet alles vom Start (wo jetzt der Zwischentagtext steht) bis zum Starttag inklusive raus - also auch den Text, den Du ja eigentlich wolltest - am Ende der Schleife bleibt so der Text übrig, der nach dem letzten schließenden Tag im StringBuilder war.

Ich hab Deinen Schleifencode leicht modifiziert (er schneidet die Werte zwischen den Tags raus und speichert sie in einer Liste) und ihn mal gegen ein größeres HTML File (circa 1000000 Zeichen) laufen lassen, dass ich lokal vorliegen hatte. Ergebnis - nach circa einer Sekunde hatte er alle Tagvorkommen gefunden.

Neben der XML-Parser Variante von kabel2 (hab ich nicht durchgemessen) könntest du noch reguläre Ausdrücke benutzen. Nach meiner Erfahrung sind die auch bei großen Strings ziemlich fix. Der Messwert bei mir waren circa 40 ms für die gleiche Aufgabe und das gleiche File. Das ganze sieht dann ungefähr so aus
Java:
StringBuilder out = ....  //eingelesene Werte
List<String> results = new ArrayList<String>();
Pattern p = Pattern.compile("<specialtag>([^<]*)</specialtag>");
Matcher m = p.matcher(out);
while(m.find()){
	results.add(m.group(1));
}
Also wie gesagt, Deine Zeiten erscheinen ziemlich hoch. Vielleicht machst du ja noch irgendwas anderes.

Ich weiß ja, dass trotz einer Neuzuweisung der String immer noch im Stringpool verbleibt
Hä? Wo hast Du das den her? IMHO gehen die Dinger bei Sun-VM's in den Stringpool, wenn du Literale ( z.B. String s1 ="Blah") benutzt oder auf Strings die intern() Methode aufrufst. Normale Strings, die erst zur Laufzeit erzeugt werden, können ganz normal vom Garbage Collector entfernt werden.

Grüße
THMD
 
Huhu,

Erstmal danke an THMD und kabel2 ;)

Du benutzt tatsächlich eine Schleife so wie Du sie gepostet hast?

Nein, dass war nur ein javarisierter Gedankenvorgang :D
Dieses Codefragment von oben stellt die Methode zum finden eines Tags und des Textes dazwischen dar.

Eigentlich ging es mir nicht darum den Text zwischen den Text zu finden, wenn der Text bereits vorhanden ist.

Ziel ist es, so wenig Speicher zu verbrauchen wie möglich.
Dies möchte ich dadurch realisieren, dass die gelesenen Lines während dem Lesen analysiert und weiterverarbeitet oder verworfen werden.

Also nicht den Text komplett auslesen, sondern Lines ohne den Tags komplett ignorieren und die nächste Line einlesen.

Irgendwie stehe ich auf der Leitung, denn es gibt das Problem, dass sich ein Tag wie oben beschrieben auf mehreren Lines befinden kann.

Ich dachte dabei daran, immer zum Beispiel 4 Lines zu buffern, diese aneinanderzuhängen und zu analysiern. (Wenn ein Tag gefunden wurde, zuscheinden und weiterlesen bis der Endtag kommt. Falls der Tag nicht gefunden wurde, weiterbuffern).

Das ist in etwa das woran ich gedacht habe. Ich brauche einen Schubs in die Richtige richtung was dies betrifft.

mfg
Martin Conrad Caesar
 
Moin,

Ziel ist es, so wenig Speicher zu verbrauchen wie möglich.
Ich dachte es geht Dir um Geschwindigkeit. In den allermeisten Fällen bedeutet weniger Speicherverbrauch auch höhere Laufzeit. Warum die Speicherbeschränkung? Hast Du eine spezielle Umgebung oder geht es Dir nur ums Prinzip? Die Verwendung von readLine() ist dann aber auch nicht unbedingt speicherschonend. Was machst Du, wenn die Webseite keine Zeilenumbrüche enthält?

Irgendwie stehe ich auf der Leitung, denn es gibt das Problem, dass sich ein Tag wie oben beschrieben auf mehreren Lines befinden kann.
Hm hast Du mal ein echtes lebendes Beispiel dafür? Es ist zwar möglich, dass ein Tag insgesamt über mehrere Zeilen geht, aber ein "echter" Umbruch (also kein virtueller in irgendeiner Quellcodeansicht) innerhalb des Tagnamens ist imho nicht erlaubt und ich kenne jetzt auch keinen Browser der das interpretieren würde. Das bedeutet, dass bei Verwendung von readLine zumindest der Tagname immer innerhalb einer eingelesenen Zeile ist,


Grüße
THMD
 
Moin,

ich hab den Thread zwar nur quergelesen, und weiß nicht ob es noch interessant ist, aber

@kabel2

die Stichworte für solche Problemstellungen unter java sind JDOM und XPath

greetz
 
Howdie.

Der Thread hat sich zwar erledigt, aber zu THMDs Aussage bezüglich Strings und GC muss ich noch was loswerden.

Hä? Wo hast Du das den her? IMHO gehen die Dinger bei Sun-VM's in den Stringpool, wenn du Literale ( z.B. String s1 ="Blah") benutzt oder auf Strings die intern() Methode aufrufst. Normale Strings, die erst zur Laufzeit erzeugt werden, können ganz normal vom Garbage Collector entfernt werden.

IMHO ist mccaes Aussage korrekt, dass sämtliche Strings im Constant Pool der JVM abgelegt werden. Du hast insofern recht, dass ein mit new String("blablubb") erzeugtes Objekt vom GC eingesammelt wird. Das zugehörige Literal "blablubb" jedoch bleibt im Pool, genau wie alle anderen erzeugten Strings. Nimm z.B.
Java:
String s1 = "string 1";
String s2 = s1.concat(" string 2");
Hier werden jetzt drei Strings in den Pool gespeichert: "string 1", " string 2" und "string 1 string 2".

Dies hat natürlich zur Folge, dass sämtliche nicht mehr verwendete bzw. referenzierte Strings (gerade bei so großen Strings, von denen hier die Rede war) unnötig Resourcen verbrauchen. Deshalb soll bei intensiven String-Operationen auch ein StringBuilder bzw. -Buffer verwendet werden, wo immer dasselbe Objekt geändert wird.

Ein einfaches Beispiel: Wir haben eine Variable String specTag, in die wir eine Homepage mit 1'000'000 Zeichen einlesen. Diese Variable überschreiben wir mit dem gefundenen Tag. Deiner Ansicht nach würde das ursprüngliche Homepage-Literal vom GC gelöscht - es verbleibt allerdings im Pool, damit der String (falls er nochmals benötigt wird) nicht mehr erzeugt werden, sondern nur noch geladen werden muss.

So, Besserwisser-Modus aus ;)

Gruß
miffi
 
Zuletzt bearbeitet:
Zurück