string Schlüsselwort

Ein Zeichen aus einem String entfernen

Algorithmus Java char string

Strings werden intern als array von chars repräsentiert *(jedenfalls war das bis JDK7 so). Das heißt, es müsste doch relativ einfach möglich sein, ein Zeichen aus einem String entfernen zu können. Genau das werde ich euch heute vorstellen. Es gibt verschiedene Umsetzungsmöglichkeiten und wir werden diese im Hinblick auf Performanz beurteilen. Als erstes nutzen wir die Methode public String replace(char oldChar, char newChar), die uns mit der String-Klasse zur Verfügung gestellt wird. String str = "hallo Welt"; str.replace("l",""); Wie lange dauert das Entfernen des Zeichens? Und ist es tatsächlich die optimale Lösung oder gibt es noch eine andere Möglichkeit? Schauen wir uns die Zeiten mal an. Um ein einigermaßes sinnvolles Ergebnis zu erhalten, machen wir ein Warmup, damit der Hotspot-Compiler drüber schauen und gegebenenfalls Optimierungen vornehmen kann. Dafür führen wir die jeweilige Methode etwa 10000 Mal aus, bevor wir die Zeit messen. Das Ergebnis: 6966ns. Ist das jetzt wirklich das beste Ergebnis? Schauen wir uns mal die Alternativen an. Wir könnten die Zeichen ja auch mit einer Methode ersetzen. Hierfür wandeln wir den String in ein Array von char um und hängen die Buchstaben zeichenweise an, solange wir nicht das zu entfernende Zeichen gefunden haben. Das würde dann wie folgt aussehen: public String entferneZeichen(String str, char c) { char[] array = str.toCharArray(); StringBuilder sb = new StringBuilder(); for(char ch : array) { if(ch != c) { sb.append(ch); } } return sb.toString(); } Ist das wohl schneller? Laut ermittelter Zeit bei gleichem Warmup ist es fast doppelt so langsam; nämlich: 13868ns. Wir könnten jetzt die Methode auch rekursiv aufbauen und schauen, ob das nicht vielleicht die optimale Lösung ist. public static String entferneZeichenRec(String str, char c) { int index = str.indexOf(c); if(index == -1) { return str; } return entferneZeichenRec(str.substring(0, index) + str.substring(index +1, str.length()), c); } Die Messung sagt, dass der rekursive Aufruf 4838ns dauert. Also nur minimal schneller als die replace-Methode, die uns zur Verfügung gestellt wird. Sollte man sich da wirklich die Mühe machen, eine eigene Methode zu schreiben? Man könnte doch genausogut die gewonnene Zeit durch Einsatz von replace mit Sonnen und Katzenleckerlies verbringen. Nun, schauen wir uns das Ganze doch mal näher an. Wir haben beim Warmup 10000 Durchläufe vorgenommen. Was passiert wohl, wenn wir das Ganze auf 20000 hochsetzen? Schauen wir uns da doch mal die Messungen an. Wuhuuuuuu, replace dauert plötzlich 78296ns, gefolgt von der Methode ersetzeZeichen(String str, char c) mit 19318ns. Aber die Nummer 1 ist plötzlich die rekursive Methode. Die braucht nach wie vor nur sehr kurz: 5809ns. Wie konnte das passieren??? Vorhin war doch replace noch schneller und die rekursive Methode nur unwesentlich schneller als die replace-Methode. Tja, des Rätsels Lösung liegt in der Behandlung von Strings. Strings sind unveränderlich und damit wird immer ein String-Objekt erzeugt. Je mehr Durchläufe, desto mehr String-Objekte und desto langsamer die Methode. Wir sagen ja auch str = str.replace("l","");. Würden wir nur str.replace("l",""); ausführen, wäre in str immernoch hallo Welt gespeichert. Ihr seht also, dass man gerade bei der Nutzung von Strings sehr vorsichtig sein muss. Im schlimmsten Fall kann es passieren, dass wir eine OutOfMemoryException erhalten, obwohl unser Heap eigentlich noch fast leer ist. Grund dafür sind vermutlich die String-Objekte, die rumschwirren. Apropos schwirren.. Ich habe vorhin hier eine Fliege entdeckt. Ich geh mal spielen. Viel Spaß noch.

27. September 2016 13:41

Itchy in Itchy programmiert