# Alle Möglichen Substrings der Länge k aus String extrahieren



## cgnpwr (5. Jun 2008)

Hallo Liebe Java-Forum User,

folgendes Problem:

Aus einem String von z.B. 1000 Zeichen will ich z.B. alle Substrings der Länge 5 erhalten. Da es sich teilweise um lange und viele Strings handelt ist die Performance ein entscheidendes Kriterium.

Zur Zeit nutze ich eine Regular Expression und laufe dann per find(i) über alle Positionen. Ich habe aber leider keine Ahnung ob es zum Beispiel günstiger ist Substring zu nutzen oder ob es noch ganz andere Möglichkeiten gäbe 

Gibt es geschwindigkeits vorteile der String Operationen wie Substring ? Gibt es onch effektivere andere Methoden ?

Für Vorschläge und Kommentare wäre ich sehr Dankbar !

Freundlichen Gruß,

cgnpwr


----------



## SlaterB (5. Jun 2008)

ich glaube subString ist da sehr effektiv, da der String das gleiche char-Array benutzt, nur mit bestimmten Grenzen,

aber kannst du ja alles testen,

ich schlage ansonsten noch vor, das char[] rauszuholen und dann in einer Schleife jeweils 5 Zeichen in einen StringBuilder zu schreiben,


----------



## Illuvatar (5. Jun 2008)

Regex dürfte ziemlich langsam sein. Was schnelleres als String#substring kann ich mir nicht vorstellen.


----------



## eliot (5. Jun 2008)

Hmm,

ich weiss nicht, ob das performant ist,
aber ich würde das so lösen (Beispiel Code,
weiss nicht ob er kompilliert):


```
String input; //langer String
String dlim = " ";
StringTokenizer tokenizer = new StringTokenizer(inout, delim);
ArrayList<String> arr = new ArrayList<String>();
String tmp;
while(tokenizer.hasNext(){
   tmp = toenizer.next();
   if(tmp.lenght()==5{
      arr.add(tmp);
}
}
```

Eventuell ein Versuch wert?

regards
eliot


----------



## cgnpwr (5. Jun 2008)

Also erst mal vielen Dank für die schnellen Antworten, ich werde entweder noch heute oder morgen mal die hier angesprochenen Versionen durchtesten und dann nach Möglichkeit berichten !


----------



## cgnpwr (6. Jun 2008)

Hallo hier mal erste Test Ergebnisse, 

ich habe zunächst mal nur eine Implementierung mittels SubString gegen die RegularExpression Implemtierung getestet.  Die Ergebnisse sind jedoch *eindeutig zugunsten von Substring * zu sehen:

[Kopie aus der Konsolen Ausgabe:]

Zeichenketten Länge: 1000
Substring Länge: 50
Anzahl der Durchläufe bei denen jeweils alle Substrings gefunden werden: 1000

Ergebnisse: 
Substring ist bei 1000 Durchläufen im Durchschnitt (also pro Run !) um:-0.003445938669 [sekunden] schneller

Bei 1000 Durchläufen bedeutet dies in der Summe eine Verbesserung um: *-3.445938669 Sekunden*
Zeit insgesammt von RegEx Implementierung: 3.510964982
Zeit insgesammt von SubString Implementierung: 0.065026313

Setzt man die Summe der Zeit die die Substring Methode für alle aufrufe Benötigt als 100%
so erhält man das die RegEx Methode um: *53.992988684442246 mal schlechter ist bzw. 5399.298868444224 % schlechter performed.*

[Ende der Ausgabe]

Sobald ich etwas Zeit bekomme werde ich noch einen Ausführlicheren Bericht posten, in dem ich auch noch weitere Methoden wie die oben vorgeschlagene String Tokenizer Methode teste....

PS: bitte das die teilweise Auftretenden - Vorzeichen gepflegt ignorieren, ich war zu müde um die Betragsfunktion rauszukramen


----------



## Marco13 (6. Jun 2008)

Das mit dem StringTokenizer wird vmtl. nicht funktionieren. Was auch immer das sollte.


----------



## eliot (6. Jun 2008)

Marco13 hat gesagt.:
			
		

> Das mit dem StringTokenizer wird vmtl. nicht funktionieren. Was auch immer das sollte.



Wieso nicht?
Problemstellung war doch, dass ein String mit 1000 Zeichen in einzelne Strings zu unterteilen
(ein Wort wird durch ein Lerrzeichen getrennt). Aus dieser Menge sollen nur Wörter
der Länge 5 gewählt werden?!
Oder habe da was falsch verstanden?

regards
eliot


----------



## SlaterB (6. Jun 2008)

nein, gefragt war aus "123abcXYZ" alle 5stelligen Teilstrings,
also "123ab", "23abc", "3abcX" usw


----------



## eliot (11. Jun 2008)

SlaterB hat gesagt.:
			
		

> nein, gefragt war aus "123abcXYZ" alle 5stelligen Teilstrings,
> also "123ab", "23abc", "3abcX" usw



Ups, ok,
für dieses Problem ist meine Lösung wohl dann doch keine Lösung 
Sorry!

regards
eliot


----------

