Mehrmals replace() auf langem String, zu speicherintensiv

[gigi99]

Ich habe einen seeeeehr langen String.

Darin muss ich viele Ersetzungen vornehmen. Das mache ich in einer for-Schleife (für jede Ersetzung eine Iteration)

String str =  "seeeeeeeeehr lang usw. ..... ";
for(int i = 0; i<=100000; i++)
{
   str = str.replace(key[i],  value[i]);
}

Das geht zwar einigermaßen schnell, Problem ist aber der Speicherverbrauch.
Wenn in meine Klasse 2x parallell laufen lasse, wird schon gemotzt, dass der virtuelle Speicher aus ist.
Wenn der String noch größer wird / noch mehr Ersetzungen notwendig sind, dann ist wohl OutOfMemoryException zu erwarten.

Ich vermute, dass es mit dem replace zusammenhängt, dass ja viele tausend Mal auf den langen String angewandt wird. Liegt der String vielmals im Speicher?

Wie könnte man das besser machen, ohne auf eine gute Performance zu verzichten?

Danke

 

[tfa]

Nimm einen StringBuffer.

 

[kleiner_held]

Fuer performante Stringersetzungen wuerde ich immer auf java.util.regex zurueckgreifen (wird intern bei String.replace() sowieso verwendet).
Abgesehen davon wuerde ich schon bei dem Fakt "seeeeehr langer String" ueberlegen, ob man nicht auf eine stream-basierte Vorgehensweise umsteigen kann. Das haengt aber halt von deiner konkreten (Teil-)aufgabe ab und laesst sich nicht pauschal aussagen.

 

[gigi99]

StringBuffer habe ich auch schon angeschauft. Allerdings muss bei der replace-Methode dort immer ein Anfang und Ende angegeben werden. Geht zwar irgendwie auch, diese herauszufinden, aber vielleicht geht's auch einfacher?!

replace im Zusammenhang mit RegEx schaue ich mir mal an.

Das mit Streams hört sich interessant an. Wäre mir auch am liebsten.
Aber wie kann ich ein replace in einem Stream vornehmen?

 

[kleiner_held]

Es kommt drauf an wo deine Daten, die du in dem riesigen String hast, eigentlich her kommen. Wenn du z.B.: aus einer Text-Datei liest, die Ersetzungen vornimmst und wieder in eine Textdatei schreibst, dann ist es wesentlich besser nicht erst die komplette Datei einzulesen, sondern z.B.: Zeilenweise zu arbeiten, also einen BufferedReader verwenden und in einer Schleife jeweils:
1. eine Zeile einlesen
2. Ersetzungen vornehmen
3. die Zeile rausschreiben (in einen Writer)

Die Fragestellung ist also, ob man das ganze auf einen Eingabe->Verarbeitung->Ausgabe Prozess runterbrechen kann, der abschnittsweise (in dem Beispiel zeilenweise) druchfuehrbar ist (anstatt komplett).

 

[gigi99]

Eigentlich sind mein Ausgangspunkt mehrere ByteArrayOutputStreams, die
ich zu einem String umwandle, konkateniere
und dann die Ersetzungen durchführe (wie beschrieben)

 

[maki]

Fuer performante Stringersetzungen wuerde ich immer auf java.util.regex zurueckgreifen (wird intern bei String.replace() sowieso verwendet).
Abgesehen davon wuerde ich schon bei dem Fakt "seeeeehr langer String" ueberlegen, ob man nicht auf eine stream-basierte Vorgehensweise umsteigen kann. Das haengt aber halt von deiner konkreten (Teil-)aufgabe ab und laesst sich nicht pauschal aussagen.

Die nicht-regex basierten Methoden sind um einiges schneller und damit performanter als die Regex Version.
StringBuffer#replace nutzt übrigens keine regex, wie denn auch, ersetzt ja nur die angegebn teile des StringBuffers.

 

[kleiner_held]

Die nicht-regex basierten Methoden sind um einiges schneller und damit performanter als die Regex Version.
StringBuffer#replace nutzt übrigens keine regex, wie denn auch, ersetzt ja nur die angegebn teile des StringBuffers.

Es geht aber eben um den Fall in String A den String B durch C zu ersetzen wobei B und C nicht die gleiche Laenge haben. Und da ist mit Matcher.group(), Matcher.appendReplacement() und Matcher.appendTail() einen StringBuffer neu zu fuellen schneller als StringBuffer.replace(). Denn wenn B.length() nicht gleich C.length() ist, dann ist bei jedem StringBuffer.replace() ein System.arraycopy() faellig und den start und end index muss man sich vorher auch noch besorgen.

 

[gigi99]

Habe mal mit Pattern/Matcher/StringBuffer experimentiert.
Geht grundsätzlich mal, habe aber noch nicht getestet bzgl.
1. Laufzeit und
2. Speicherverbrauch.

Ist das nur eine Pseudo-Lösung oder könnte damit wirklich weniger Speicher verbraucht werden?

import java.util.regex.*;

public class ReplaceTest 
{
	public static void main(String[] args) 
	{
		StringBuffer buffer = new StringBuffer("das ist ein test string, der möglicherweise auch ganz lang ist");
		
		ReplaceTest rt = new ReplaceTest();
		buffer = rt.replace(buffer, "test", "TestT");
		buffer = rt.replace(buffer, "ist", "frisst");
		
		System.out.println(buffer.toString());
	}
	
	
	public StringBuffer replace (StringBuffer replaceIn, String findPattern, String replacePatternWith )
	{
		 Pattern p = Pattern.compile(findPattern);
		 Matcher m = p.matcher(replaceIn);
		 StringBuffer sb = new StringBuffer();
		 
		 while (m.find()) 
		 {
		     m.appendReplacement(sb, replacePatternWith);
		 }
		 m.appendTail(sb);
		 
		 
		 return sb;
	}
}

 

[Marco13]

Eigentlich ist regex eher langsam ... :?

In bezug auf die Laufzeit (die mit dem "brute force" Verfahren, das du bisher (einmal im ursprünglichen post, und jetzt nochmal mit Regex) verwendet hast, grottenst-schelcht sein dürfte :autsch: ) wäre es hilfreich, zu wissen, WAS dort GENAU gemacht wird. Einige wichtige Fragen wären da solche wie
- Kommen die Keys in der Reihenfolge im String vor, in der sie im keys-Array liegen?
- Gibt es keys, die sich im Input überschneiden?
Z.B.
input="wortest"
key0 = "wort", value0 = "aaaa";
key1 = "test", value1 = "bbbb";
Ergebnis: MUSS "aaaaest" sein - und nicht "aaaabbb" oder "wortbbb" oder "aaabbbb" ....
- Gibt es values, die (auch teilweise) aus keys bestehen?
Z.B.
input="wortest"
key0 = "wort", value0 = "tttt";
key1 = "test", value1 = "bbbb";
Ergebnis: MUSS "tttbbb" sein - und nicht irgendwas anderes....

In bezug auf den Speicher (den du ja als das Hauptproblem siehst...) : Schau mal nach, ob noch "lebende" Referenzen auf deine ByteArrayOutputStreams existieren (müssen). Z.B. könnte sowas Problematisch sein:

void foo()
{
    ByteArrayOutputStream b0 = createByteArrayOutputStreamWithLotsOfData();
    ByteArrayOutputStream b1 = createByteArrayOutputStreamWithLotsOfData();

    String input = new String(b0.toByteArray())+new String(b1.toByteArray());
    replace(....);
}

Da könnte es schon helfen, dem GC zu erlauben, die ByteArrayOutputStreams wegzuwerfen, indem man sie explizit auf null setzt:

void foo()
{
    ByteArrayOutputStream b0 = createByteArrayOutputStreamWithLotsOfData();
    ByteArrayOutputStream b1 = createByteArrayOutputStreamWithLotsOfData();

    String input = new String(b0.toByteArray())+new String(b1.toByteArray());

    b0 = null;
    b1 = null;
    // Jetzt kann der Speicher, der vorher von den ByteArrayOutputStreams belegt war, freigegeben werden

    replace(....);
}

 

[gigi99]

Meine Tests ergaben, dass die zweite Version mit Pattern/Matcher/StringBuffer wesentlich sparsamer mit dem Speicher umgeht.

Stelle jetzt alles um auf StringBuffer (leistet replace) und StringTokenizer (leistet split).

Guggsch du hier:
http://www.particle.kth.se/~lindsey/JavaCourse/Book/Part1/Java/Chapter10/stringBufferToken.html

Auszug:
------------------------------------------
String objects are immutable, meaning that once created they cannot be altered. Concatenating two strings does not modify either string but instead creates a new string object:

String str = "This is ";
str = str + " a new string object";

Here str variable now references a completely new object that holds the "This is a new string object" string.

This is not very efficient if you are doing extensive string manipulation with lots of new strings created through this sort of append operations. The String class maintains a pool of strings in memory. String literals are saved there and new strings are added as they are created. Extensive string manipulation with lots of new strings created with the String append operations can therefore result in lots of memory taken up by unneeded strings.
------------------------------------------