Der schnellste Weg, um alle nicht druckbaren Zeichen aus einem Java-String zu entfernen

81

Was ist der schnellste Weg, um alle nicht druckbaren Zeichen von einem Stringin Java zu entfernen?

Bisher habe ich versucht, einen 138-Byte-String mit 131 Zeichen zu messen:

  • String's replaceAll()- langsamste Methode
    • 517009 Ergebnisse / Sek
  • Kompilieren Sie ein Muster vor und verwenden Sie dann Matcher's replaceAll()
    • 637836 Ergebnisse / Sek
  • Verwenden Sie StringBuffer, rufen Sie Codepunkte codepointAt()einzeln ab und hängen Sie sie an StringBuffer an
    • 711946 Ergebnisse / Sek
  • Verwenden Sie StringBuffer, rufen Sie Zeichen einzeln ab charAt()und hängen Sie sie an StringBuffer an
    • 1052964 Ergebnisse / Sek
  • Ordnen Sie einen char[]Puffer vorab zu , rufen Sie die Zeichen einzeln ab , charAt()füllen Sie diesen Puffer und konvertieren Sie ihn zurück in String
    • 2022653 Ergebnisse / Sek
  • Ordnen Sie 2 char[]Puffer vorab zu - alt und neu, rufen Sie alle Zeichen für den vorhandenen String auf einmal ab getChars(), durchlaufen Sie den alten Puffer einzeln und füllen Sie den neuen Puffer, und konvertieren Sie dann den neuen Puffer in einen String - meine schnellste Version
    • 2502502 Ergebnisse / Sek
  • Gleiches Zeug mit 2 Puffern - nur mit byte[],getBytes() und der Angabe Codierung als „UTF-8“
    • 857485 Ergebnisse / Sek
  • Gleiches Zeug mit 2 byte[]Puffern, aber Angabe der Codierung als KonstanteCharset.forName("utf-8")
    • 791076 Ergebnisse / Sek
  • Gleiches Zeug mit 2 byte[] Puffern, aber Angabe der Codierung als lokale 1-Byte-Codierung (kaum eine vernünftige Sache)
    • 370164 Ergebnisse / Sek

Mein bester Versuch war der folgende:

    char[] oldChars = new char[s.length()];
    s.getChars(0, s.length(), oldChars, 0);
    char[] newChars = new char[s.length()];
    int newLen = 0;
    for (int j = 0; j < s.length(); j++) {
        char ch = oldChars[j];
        if (ch >= ' ') {
            newChars[newLen] = ch;
            newLen++;
        }
    }
    s = new String(newChars, 0, newLen);

Irgendwelche Gedanken darüber, wie man es noch schneller macht?

Bonuspunkte für die Beantwortung einer sehr seltsamen Frage: Warum die Verwendung des Zeichensatznamens "utf-8" direkt zu einer besseren Leistung führt als die Verwendung einer vorab zugewiesenen statischen Konstante Charset.forName("utf-8") ?

Aktualisieren

  • Vorschlag von Ratschenfreak liefert eine beeindruckende Leistung von 3105590 Ergebnissen / Sek., Eine Verbesserung um + 24%!
  • Der Vorschlag von Ed Staub liefert eine weitere Verbesserung - 3471017 Ergebnisse / Sek., Ein Plus von 12% gegenüber dem vorherigen Bestwert.

Update 2

Ich habe mein Bestes gegeben, um alle vorgeschlagenen Lösungen und ihre Kreuzmutationen zu sammeln und sie als kleines Benchmarking-Framework bei github zu veröffentlichen . Derzeit gibt es 17 Algorithmen. Einer davon ist der "spezielle" Voo1- Algorithmus ( bereitgestellt vom SO-Benutzer Voo) ) verwendet komplizierte Reflexionstricks, um hervorragende Geschwindigkeiten zu erreichen, JVM-Strings .

Sie können es gerne ausprobieren und ausführen, um die Ergebnisse auf Ihrer Box zu ermitteln. Hier ist eine Zusammenfassung meiner Ergebnisse. Es ist Spezifikationen:

  • Debian Sid
  • Linux 2.6.39-2-amd64 (x86_64)
  • Java aus einem Paket installiert sun-java6-jdk-6.24-1 , identifiziert sich JVM als
    • Java (TM) SE-Laufzeitumgebung (Build 1.6.0_24-b07)
    • Java HotSpot (TM) 64-Bit-Server-VM (Build 19.1-b02, gemischter Modus)

Unterschiedliche Algorithmen zeigen letztendlich unterschiedliche Ergebnisse bei unterschiedlichen Eingabedaten. Ich habe einen Benchmark in 3 Modi durchgeführt:

Gleiche einzelne Zeichenfolge

Dieser Modus arbeitet mit derselben einzelnen Zeichenfolge, die von der StringSourceKlasse als Konstante bereitgestellt wird . Der Showdown ist:

 Ops / s │ Algorithmus
───────────────────────────────────────────
6 535 947 │ Voo1
───────────────────────────────────────────
5 350 454 │ RatchetFreak2EdStaub1GreyCat1
5 249 343 │ EdStaub1
5 002 501 │ EdStaub1GreyCat1
4 859 086 │ ArrayOfCharFromStringCharAt
4 295 532 │ RatchetFreak1
4 045 307 │ ArrayOfCharFromArrayOfChar
2 790 178 │ RatchetFreak2EdStaub1GreyCat2
2 583 311 │ RatchetFreak2
1 274 859 │ StringBuilderChar
1 138 174 │ StringBuilderCodePoint
  994 727 │ ArrayOfByteUTF8String
  918 611 │ ArrayOfByteUTF8Const
  756 086 │ MatcherReplace
  598 945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

In Diagrammform : (Quelle: greycat.ru )Gleiches einzelnes String-Diagramm

Mehrere Zeichenfolgen, 100% der Zeichenfolgen enthalten Steuerzeichen

Der Quell-String-Anbieter hat viele zufällige Strings mit dem Zeichensatz (0..127) vorgeneriert - daher enthielten fast alle Strings mindestens ein Steuerzeichen. Algorithmen haben Strings von diesem vorgenerierten Array im Round-Robin-Verfahren empfangen.

 Ops / s │ Algorithmus
───────────────────────────────────────────
2 123 142 │ Voo1
───────────────────────────────────────────
1 782 214 │ EdStaub1
1 776 199 │ EdStaub1GreyCat1
1 694 628 │ ArrayOfCharFromStringCharAt
1 481 481 │ ArrayOfCharFromArrayOfChar
1 460 067 │ RatchetFreak2EdStaub1GreyCat1
1 438 435 │ RatchetFreak2EdStaub1GreyCat2
1 366 494 │ RatchetFreak2
1 349 710 │ RatchetFreak1
  893 176 │ ArrayOfByteUTF8String
  817 127 │ ArrayOfByteUTF8Const
  778 089 │ StringBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceAll

In Diagrammform : (Quelle: greycat.ru )Mehrere Saiten, 100% Konzentration

Mehrere Zeichenfolgen, 1% der Zeichenfolgen enthalten Steuerzeichen

Wie zuvor, jedoch wurde nur 1% der Zeichenfolgen mit Steuerzeichen generiert - andere 99% wurden mit dem Zeichensatz [32..127] generiert, sodass sie überhaupt keine Steuerzeichen enthalten konnten. Diese synthetische Last kommt der realen Anwendung dieses Algorithmus bei mir am nächsten.

 Ops / s │ Algorithmus
───────────────────────────────────────────
3 711 952 │ Voo1
───────────────────────────────────────────
2 851 440 │ EdStaub1GreyCat1
2 455 796 │ EdStaub1
2 426 007 │ ArrayOfCharFromStringCharAt
2 347 969 │ RatchetFreak2EdStaub1GreyCat2
2 242 152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1 922 707 │ RatchetFreak2EdStaub1GreyCat1
1 857 010 │ RatchetFreak2
1 023 751 │ ArrayOfByteUTF8String
  939 055 │ StringBuilderChar
  907 194 │ ArrayOfByteUTF8Const
  841 963 │ StringBuilderCodePoint
  606 465 │ MatcherReplace
  501 555 │ StringReplaceAll
  381 185 │ ArrayOfByteWindows1251

In Diagrammform : (Quelle: greycat.ru )Mehrere Saiten, 1% Konzentration

Es ist sehr schwer für mich zu entscheiden, wer die beste Antwort geliefert hat, aber angesichts der realen Anwendung, die die beste Lösung von Ed Staub gegeben / inspiriert hat, wäre es fair, seine Antwort zu markieren. Vielen Dank für alle, die daran teilgenommen haben. Ihre Beiträge waren sehr hilfreich und von unschätzbarem Wert. Fühlen Sie sich frei, die Testsuite auf Ihrer Box auszuführen und noch bessere Lösungen vorzuschlagen (funktionierende JNI-Lösung, irgendjemand?).

Verweise

GreyCat
quelle
21
"Diese Frage zeigt den Forschungsaufwand" - hmm ... ja, bestanden. +1
Gustav Barkefors
7
StringBuilderwird geringfügig schneller sein als StringBufferes nicht synchronisiert ist, ich erwähne dies nur, weil Sie dies markiert habenmicro-optimization
2
@ Jarrod Roberson: ok, also lassen Sie uns alle schreibgeschützten Felder endgültig machen und s.length()auch aus der forSchleife extrahieren :-)
Hause
3
Einige Zeichen unter dem Leerzeichen können gedruckt werden, z . B. \tund \n. Viele Zeichen über 127 sind in Ihrem Zeichensatz nicht druckbar.
Peter Lawrey
1
Haben Sie den String-Puffer mit einer Kapazität von s.length()initiiert?
Ratschenfreak

Antworten:

11

Wenn es sinnvoll ist, diese Methode in eine Klasse einzubetten, die nicht für mehrere Threads freigegeben ist, können Sie den Puffer wiederverwenden:

char [] oldChars = new char[5];

String stripControlChars(String s)
{
    final int inputLen = s.length();
    if ( oldChars.length < inputLen )
    {
        oldChars = new char[inputLen];
    }
    s.getChars(0, inputLen, oldChars, 0);

etc...

Dies ist ein großer Gewinn - 20% oder so, wie ich den derzeit besten Fall verstehe.

Wenn dies für potenziell große Zeichenfolgen verwendet werden soll und das "Speicherleck" ein Problem darstellt, kann eine schwache Referenz verwendet werden.

Ed Staub
quelle
Großartige Idee! Bisher wurden 3471017 Zeichenfolgen pro Sekunde gezählt - dh eine Verbesserung von + 12% gegenüber der vorherigen besten Version.
GreyCat
25

Die Verwendung eines 1-Zeichen-Arrays könnte etwas besser funktionieren

int length = s.length();
char[] oldChars = new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

und ich vermied wiederholte Anrufe zu s.length();

Eine andere Mikrooptimierung, die funktionieren könnte, ist

int length = s.length();
char[] oldChars = new char[length+1];
s.getChars(0, length, oldChars, 0);
oldChars[length]='\0';//avoiding explicit bound check in while
int newLen=-1;
while(oldChars[++newLen]>=' ');//find first non-printable,
                       // if there are none it ends on the null char I appended
for (int  j = newLen; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;//the while avoids repeated overwriting here when newLen==j
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);
Ratschenfreak
quelle
1
Vielen Dank! Ihre Version liefert 3105590 Zeichenfolgen / Sek. - eine massive Verbesserung!
GreyCat
newLen++;: Was ist mit Vorinkrement ++newLen;? - (auch ++jin der Schleife). Schauen Sie hier: stackoverflow.com/questions/1546981/…
Thomas
Das Hinzufügen finalzu diesem Algorithmus und das Verwenden oldChars[newLen++]( ++newLenist ein Fehler - die gesamte Zeichenfolge würde um 1 abweichen!) Ergibt keine messbaren Leistungssteigerungen (dh ich erhalte ± 2..3% Unterschiede, die mit Unterschieden verschiedener Läufe vergleichbar sind)
GreyCat
@ Grey Ich habe eine andere Version mit einigen anderen Optimierungen gemacht
Ratschenfreak
2
Hmm! Das ist eine geniale Idee! 99,9% der Strings in meiner Produktionsumgebung erfordern kein Strippen - ich kann es weiter verbessern, um die erste char[]Zuweisung zu eliminieren und den String unverändert zurückzugeben, wenn kein Strippen stattgefunden hat.
GreyCat
11

Nun, ich habe die derzeit beste Methode (Freak-Lösung mit dem vorab zugewiesenen Array) nach meinen Maßstäben um etwa 30% übertroffen. Wie? Indem ich meine Seele verkaufe.

Wie ich sicher bin, weiß jeder, der die Diskussion bisher verfolgt hat, dass dies so ziemlich jedes grundlegende Programmierprinzip verletzt, aber na ja. Das Folgende funktioniert jedoch nur, wenn das verwendete Zeichenarray der Zeichenfolge nicht von anderen Zeichenfolgen gemeinsam genutzt wird. Wenn dies der Fall ist, hat jeder, der dies debuggen muss, das Recht, Sie zu töten (ohne Aufrufe von substring () und dies für Literalzeichenfolgen zu verwenden Dies sollte funktionieren, da ich nicht verstehe, warum die JVM eindeutige Zeichenfolgen interniert, die von einer externen Quelle gelesen wurden. Vergessen Sie jedoch nicht, sicherzustellen, dass der Benchmark-Code dies nicht tut - das ist äußerst wahrscheinlich und würde der Reflexionslösung offensichtlich helfen.

Sowieso hier gehen wir:

    // Has to be done only once - so cache those! Prohibitively expensive otherwise
    private Field value;
    private Field offset;
    private Field count;
    private Field hash;
    {
        try {
            value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            offset = String.class.getDeclaredField("offset");
            offset.setAccessible(true);
            count = String.class.getDeclaredField("count");
            count.setAccessible(true);
            hash = String.class.getDeclaredField("hash");
            hash.setAccessible(true);               
        }
        catch (NoSuchFieldException e) {
            throw new RuntimeException();
        }

    }

    @Override
    public String strip(final String old) {
        final int length = old.length();
        char[] chars = null;
        int off = 0;
        try {
            chars = (char[]) value.get(old);
            off = offset.getInt(old);
        }
        catch(IllegalArgumentException e) {
            throw new RuntimeException(e);
        }
        catch(IllegalAccessException e) {
            throw new RuntimeException(e);
        }
        int newLen = off;
        for(int j = off; j < off + length; j++) {
            final char ch = chars[j];
            if (ch >= ' ') {
                chars[newLen] = ch;
                newLen++;
            }
        }
        if (newLen - off != length) {
            // We changed the internal state of the string, so at least
            // be friendly enough to correct it.
            try {
                count.setInt(old, newLen - off);
                // Have to recompute hash later on
                hash.setInt(old, 0);
            }
            catch(IllegalArgumentException e) {
                e.printStackTrace();
            }
            catch(IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        // Well we have to return something
        return old;
    }

Für meinen Teststring wird das 3477148.18ops/svs. 2616120.89ops/sfür die alte Variante. Ich bin mir ziemlich sicher, dass der einzige Weg, dies zu übertreffen, darin besteht, es in C zu schreiben (wahrscheinlich nicht) oder einen völlig anderen Ansatz, über den bisher noch niemand nachgedacht hat. Obwohl ich mir absolut nicht sicher bin, ob das Timing auf verschiedenen Plattformen stabil ist - liefert zumindest auf meiner Box (Java7, Win7 x64) zuverlässige Ergebnisse.

Voo
quelle
Vielen Dank für die Lösung. Schauen Sie sich bitte das Fragen-Update an. Ich habe mein Test-Framework veröffentlicht und 3 Testergebnisse für 17 Algorithmen hinzugefügt. Ihr Algorithmus ist immer an der Spitze, ändert jedoch den internen Status von Java String und bricht damit den Vertrag "unveränderlicher String" => Es wäre ziemlich schwierig, ihn in realen Anwendungen zu verwenden. Testmäßig, ja, es ist das beste Ergebnis, aber ich denke, ich werde es als separate Nominierung bekannt geben :)
GreyCat
3
@GreyCat Ja, es hat sicherlich einige große Probleme und ehrlich gesagt habe ich es so ziemlich nur geschrieben, weil ich mir ziemlich sicher bin, dass es keinen erkennbaren Weg gibt, Ihre derzeit beste Lösung weiter zu verbessern. Es gibt Situationen, in denen ich sicher bin, dass es gut funktioniert (keine Teilzeichenfolge oder interne Aufrufe vor dem Entfernen), aber das liegt am Wissen über eine aktuelle Hotspot-Version (dh afaik, es werden keine internen Zeichenfolgen von E / A gelesen - nicht). nicht besonders nützlich sein). Es kann nützlich sein, wenn man diese zusätzlichen x% wirklich braucht, aber ansonsten eher eine Basislinie, um zu sehen, wie viel man noch verbessern kann;)
Voo
1
Obwohl ich versucht habe, eine JNI-Version zu testen, wenn ich Zeit finde - habe sie bisher noch nie verwendet, so dass das interessant wäre. Aber ich bin mir ziemlich sicher, dass es aufgrund des zusätzlichen Aufrufaufwands (Zeichenfolgen sind viel zu klein) und der Tatsache, dass es der JIT nicht so schwer fallen sollte, die Funktionen zu optimieren, langsamer wird. Nur nicht verwenden, new String()falls Ihre Zeichenfolge nicht geändert wurde, aber ich denke, Sie haben das bereits.
Voo
Ich habe bereits versucht, genau das Gleiche in reinem C zu tun - und es zeigt keine wirkliche Verbesserung gegenüber Ihrer reflexionsbasierten Version. C-Version läuft so etwas wie + 5..10% schneller, nicht wirklich so toll - ich dachte, es wäre mindestens 1.5x-1.7x ...
GreyCat
2

Sie können die Aufgabe abhängig von der Anzahl der Prozessoren in mehrere parallele Unteraufgaben aufteilen.

umbr
quelle
Ja, ich habe auch darüber nachgedacht, aber es wird in meiner Situation keine Leistungssteigerungen bringen - dieser Stripping-Algorithmus würde in einem bereits massiv parallelen System aufgerufen.
GreyCat
2
Außerdem könnte ich vermuten, dass das Abspalten einiger Threads für die Verarbeitung pro 50-100-Byte-Zeichenfolge ein großer Overkill wäre.
GreyCat
Ja, das Gabeln von Fäden für jede kleine Saite ist keine gute Idee. Der Load Balancer könnte jedoch die Leistung verbessern. Übrigens, haben Sie die Leistung mit StringBuilder anstelle von StringBuffer getestet, dessen Leistung aufgrund der Synchronisierung fehlt?
Umbr
Meine Produktions-Setup-Läufe erzeugen mehrere separate Prozesse und verwenden so viele parallele CPUs und Kerne wie möglich, sodass ich sie StringBuilderüberall problemlos verwenden kann.
GreyCat
2

Ich war so frei und schrieb einen kleinen Benchmark für verschiedene Algorithmen. Es ist nicht perfekt, aber ich nehme das Minimum von 1000 Durchläufen eines bestimmten Algorithmus 10000 Mal über eine zufällige Zeichenfolge (standardmäßig mit etwa 32/200% nicht druckbaren Zeichen). Das sollte sich um Dinge wie GC, Initialisierung usw. kümmern - es gibt nicht so viel Overhead, dass ein Algorithmus nicht mindestens einen Lauf ohne große Hindernisse haben sollte.

Nicht besonders gut dokumentiert, aber na ja. Los geht's - ich habe sowohl die Algorithmen des Ratschenfreaks als auch die Basisversion aufgenommen. Im Moment initialisiere ich zufällig eine 200 Zeichen lange Zeichenfolge mit gleichmäßig verteilten Zeichen im Bereich [0, 200].

Voo
quelle
+1 für die Mühe - aber Sie hätten mich fragen sollen - ich habe bereits eine ähnliche Benchmarking-Suite - dort habe ich meine Algorithmen getestet;)
GreyCat
@GreyCat Nun, ich hätte es tun können, aber das zusammen zu werfen (aus dem vorhandenen Code sowieso) war wahrscheinlich schneller;)
Voo
1

IANA Java-Performance-Junkie auf niedriger Ebene, aber haben Sie versucht, Ihre Hauptschleife abzuwickeln? ? Es scheint, dass es einigen CPUs ermöglichen könnte, Prüfungen parallel durchzuführen.

Auch dies hat einige lustige Ideen für Optimierungen.

Ryan Ransford
quelle
Ich bezweifle, dass hier ein Abrollen durchgeführt werden könnte, da (a) Abhängigkeiten von den folgenden Schritten des Algorithmus von den vorherigen Schritten bestehen. (B) Ich habe noch nicht einmal von jemandem gehört, der das manuelle Abrollen von Schleifen in Java durchführt und herausragende Ergebnisse erzielt. JIT macht normalerweise einen guten Job beim Abrollen von allem, was es für die Aufgabe hält. Vielen Dank für den Vorschlag und einen Link :)
GreyCat
0

Warum führt die Verwendung des Zeichensatznamens "utf-8" direkt zu einer besseren Leistung als die Verwendung der vorab zugewiesenen statischen Konstante Charset.forName ("utf-8")?

Wenn Sie damit meinen String#getBytes("utf-8")usw.: Dies sollte nicht schneller sein - mit Ausnahme eines besseren Cachings - da Charset.forName("utf-8")es intern verwendet wird, wenn der Zeichensatz nicht zwischengespeichert wird.

Eine Sache könnte sein, dass Sie verschiedene Zeichensätze verwenden (oder dass ein Teil Ihres Codes transparent ist), aber der zwischengespeicherte Zeichensatz StringCodingändert sich nicht.

Thomas
quelle