wake-up-neo.com

Schnellste Methode zum Entfernen aller nicht druckbaren Zeichen aus einem Java-String

Was ist der schnellste Weg, um alle nicht druckbaren Zeichen aus einer String in Java zu entfernen?

Bisher habe ich einen 138-Byte-String mit 131 Zeichen ausprobiert:

  • String replaceAll() - langsamste Methode
    • 517009 Ergebnisse/Sek
  • Kompilieren Sie ein Pattern vorab und verwenden Sie dann Matchers replaceAll()
    • 637836 Ergebnisse/Sek
  • Verwenden Sie StringBuffer, rufen Sie die Codepunkte mit codepointAt() einzeln ab und hängen Sie sie an StringBuffer an
    • 711946 Ergebnisse/Sek
  • Verwenden Sie StringBuffer, holen Sie Zeichen mit charAt() nacheinander und hängen Sie ihn an StringBuffer
    • 1052964 Ergebnisse/Sek
  • Ordnen Sie einen char[]-Puffer vorab zu, holen Sie Zeichen mit charAt() nacheinander ab, füllen Sie diesen Puffer, und konvertieren Sie ihn wieder in String
    • 2022653 Ergebnisse/Sek
  • Vorbelegung 2 char[]-Puffer - alt und neu, alle Zeichen für vorhandenen String auf einmal mit getChars() abrufen, den alten Puffer nacheinander durchlaufen und neuen Puffer füllen, dann neuen Puffer in String - meine schnellste Version umwandeln
    • 2502502 Ergebnisse/Sek
  • Gleiche Sachen mit 2 Puffern - nur mit byte[], getBytes() und Angabe der Codierung als "utf-8"
    • 857485 Ergebnisse/Sek
  • Gleiches Zeug mit 2 byte[]-Puffern, aber Angabe der Codierung als Konstante Charset.forName("utf-8")
    • 791076 Ergebnisse/Sek
  • Gleiches Zeug mit 2 byte[]-Puffern, aber Angabe der Kodierung als 1-Byte-Ortskodierung (kaum etwas Vernünftiges zu tun)
    • 370164 Ergebnisse/Sek

Mein bester Versuch war folgendes:

    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, wie man es noch schneller machen kann?

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

Aktualisieren

  • Der Vorschlag von Ratschenfreak liefert beeindruckende 3105590 Ergebnisse/Sek., Eine Verbesserung um 24%!
  • Der Vorschlag von Ed Staub führt zu einer weiteren Verbesserung - 3471017 Ergebnisse/Sek. Ein Plus von 12% gegenüber der vorherigen Bestleistung.

Update 2

Ich habe mein Bestes gegeben, um alle vorgeschlagenen Lösungen und ihre Kreuzmutationen zusammenzufassen und als kleines Benchmarking-Framework bei github zu veröffentlichen. Derzeit werden 17 Algorithmen verwendet. Einer von ihnen ist "special" - Voo1 - Algorithmus ( wird von SO user Voo bereitgestellt ) verwendet komplizierte Reflektionstricks, wodurch Sterngeschwindigkeiten erreicht werden, aber der Status der JVM-Strings wird dadurch beeinträchtigt Es wird separat bewertet.

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, das aus einem Paket Sun-Java6-jdk-6.24-1 installiert wurde, 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 letztlich unterschiedliche Ergebnisse bei unterschiedlichen Eingangsdaten. Ich habe einen Benchmark in 3 Modi durchgeführt:

Gleiche einzelne Zeichenfolge

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

 Ops/s │ Algorithmus 
 ──────────┼──────────────────────────────. 6 535 947 Voo1 
 ──────────┼───────────────────────────── 350 
 5 350 454.. O O O O. O St St St St St St St St St St St St St St St St St St St St St St St St __. 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: Gleiches Diagramm mit einem einzigen String http://www.greycat.ru/img/os-chart-single.png

Mehrere Zeichenfolgen, 100% der Zeichenfolgen enthalten Steuerzeichen

Der Provider für Quellstrings hat viele (0 ... 127) Zeichenketten mit zufälligen Strings vorgeneriert. Daher enthielten fast alle Strings mindestens ein Steuerzeichen. Algorithmen haben Strings von diesem vorab generierten Array in Round-Robin-Art 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 reak 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: 
 Mehrere Zeichenfolgen, Konzentration 100% http://www.greycat.ru/img/os-chart-multi100.png

Mehrere Zeichenfolgen, 1% der Zeichenfolgen enthalten Steuerzeichen

Wie zuvor, jedoch wurden nur 1% der Zeichenfolgen mit Steuerzeichen generiert. Andere 99% wurden im Zeichensatz [32..127] generiert, sodass sie keine Steuerzeichen enthalten konnten. Diese synthetische Last kommt der realen Weltanwendung dieses Algorithmus an meiner Stelle am nächsten.

Ops/s │ Algorithmus ──────────┼──────────────────────────────. 3 711 952 Voo1 1 2 851 440 │ EdStaub1GreyCat1 .__ 455 796 │ EdStaub1. __ 2 426 007 │ ArrayOfCharFromStringCharAt.. 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 Tabellenform: 
 Mehrere Zeichenfolgen, 1% Konzentration http://www.greycat.ru/img/os-chart-multi1.png

Es ist sehr schwer für mich zu entscheiden, wer die beste Antwort lieferte, aber angesichts der praxisnahen Anwendung wurde die beste Lösung von Ed Staub gegeben/inspiriert. Ich denke, es wäre 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, um die Testsuite auf Ihrer Box auszuführen und schlagen Sie noch bessere Lösungen vor (funktionierende JNI-Lösung, irgendjemand?).

Verweise.

76
GreyCat

Wenn es sinnvoll ist, diese Methode in eine Klasse einzubetten, die nicht von Threads gemeinsam genutzt wird, 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);

usw...

Dies ist ein großer Gewinn - etwa 20%, wenn ich den aktuellen besten Fall verstehe.

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

9
Ed Staub

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 an 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);
24
ratchet freak

Nun, ich habe die derzeit beste Methode (freak-Lösung mit dem vorab zugewiesenen Array) um etwa 30% nach meinen Maßen geschlagen. Wie? Indem ich meine Seele verkaufe.

Ich bin mir sicher, dass jeder, der die Diskussion bisher verfolgt hat, weiß, dass dies gegen alle grundlegenden Programmierprinzipien verstößt, aber na ja. Das Folgende funktioniert jedoch nur, wenn das verwendete Zeichen-Array der Zeichenfolge nicht von anderen Zeichenfolgen gemeinsam genutzt wird. Wenn dies der Fall ist, der Debugging durchführen muss, hat dies alle Rechte, die Sie (ohne Aufrufe von substring ()) umbringen, und dies für literale Zeichenfolgen Dies sollte funktionieren, da ich nicht sehe, warum die JVM eindeutige Zeichenfolgen aus einer externen Quelle lesen würde. Vergessen Sie jedoch nicht, sicherzustellen, dass der Benchmark-Code dies nicht tut. Dies ist äußerst wahrscheinlich und würde der Reflexionslösung offensichtlich helfen.

Wie auch immer, wir gehen hier hin:

    // 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 meine Testzeichenfolge erhält das 3477148.18ops/s vs. 2616120.89ops/s für die alte Variante. Ich bin mir ziemlich sicher, dass der einzige Weg, um ihn zu schlagen, darin bestehen könnte, ihn in C zu schreiben (wahrscheinlich nicht) oder eine völlig andere Herangehensweise, über die bisher noch niemand nachgedacht hat. Ich bin mir aber absolut nicht sicher, ob das Timing auf verschiedenen Plattformen stabil ist - zumindest auf meiner Box (Java7, Win7 x64) werden zuverlässige Ergebnisse erzielt.

9
Voo

Sie können die Aufgabe in mehrere parallele Teilaufgaben aufteilen, abhängig von der Anzahl der Bearbeiter.

2
umbr

IANA Low-Level-Java-Leistungsjunkie, aber haben Sie versucht, Ihre Hauptschleife aufzuwickeln []? Es hat den Anschein, als könnten einige CPUs parallel Prüfungen durchführen.

This hat auch einige lustige Ideen für Optimierungen.

1
Ryan Ransford

Ich war so frei und schrieb einen kleinen Benchmark für verschiedene Algorithmen. Es ist nicht perfekt, aber ich brauche das Minimum von 1000 Durchläufen eines gegebenen Algorithmus 10000-mal über eine zufällige Zeichenfolge (standardmäßig etwa 32/200% nicht druckbar). Das sollte sich um Dinge wie GC, Initialisierung usw. kümmern - es ist nicht so viel Aufwand, dass jeder Algorithmus nicht mindestens einen Durchlauf ohne viel Behinderung haben sollte.

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

1
Voo

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

Wenn Sie String#getBytes("utf-8") etc meinen: Dies sollte nicht schneller sein - abgesehen von etwas besserem Caching -, da Charset.forName("utf-8") intern verwendet wird, wenn der Zeichensatz nicht zwischengespeichert wird.

Eine Sache könnte sein, dass Sie unterschiedliche Zeichensätze verwenden (oder vielleicht ist etwas von Ihrem Code transparent), der in StringCoding zwischengespeicherte Zeichensatz ändert sich jedoch nicht.

0
Thomas