Frage Schnellste Möglichkeit, alle nicht druckbaren Zeichen aus einer Java-Zeichenfolge zu entfernen


Wie entferne ich am schnellsten alle nicht druckbaren Zeichen von einem? String in Java?

Bisher habe ich versucht und gemessen an 138-Byte, 131-Zeichen String:

  • Zeichenfolge ist replaceAll() - langsamste Methode
    • 517009 Ergebnisse / Sek
  • Ein Muster vorkompilieren, dann Matcher verwenden replaceAll()
    • 637836 Ergebnisse / Sek
  • Benutze StringBuffer, erhalte Codepunkte mit codepointAt() eins nach dem anderen und an den StringBuffer anhängen
    • 711946 Ergebnisse / Sek
  • Verwenden Sie StringBuffer, erhalten Sie Zeichen mit charAt() eins nach dem anderen und an den StringBuffer anhängen
    • 1052964 Ergebnisse / Sek
  • Vorabzuweisen a char[] puffern, Zeichen verwenden charAt() eins nach dem anderen und füllen Sie diesen Puffer, dann zurück in String konvertieren
    • 2022653 Ergebnisse / Sek
  • Vorbelegung 2 char[] Puffer - alt und neu, erhalten alle Zeichen für vorhandene String auf einmal mit getChars(), wiederhole den alten Puffer nacheinander und fülle den neuen Puffer und konvertiere dann den neuen Puffer in String - meine eigene schnellste Version
    • 2502502 Ergebnisse / Sek
  • Gleiches Zeug mit 2 Puffern - nur mit byte[], getBytes() und Angabe der Codierung als "utf-8"
    • 857485 Ergebnisse / Sek
  • Gleiches Zeug mit 2 byte[] Puffer, aber die Codierung als Konstante angeben Charset.forName("utf-8")
    • 791076 Ergebnisse / Sek
  • Gleiches Zeug mit 2 byte[] Puffer, aber Codierung als 1-Byte-Local-Encoding (kaum eine gesunde Sache 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 merkwürdigen Frage: warum die Verwendung des Zeichensatznamens "utf-8" direkt eine bessere Leistung liefert als die Verwendung von zuvor zugewiesenem statischem const Charset.forName("utf-8")?

Aktualisieren

  • Vorschlag von Ratschen-Freak liefert beeindruckende 3105590 Ergebnisse / Sek. Performance, eine + 24% Verbesserung!
  • Vorschlag von Ed Staub ergibt eine weitere Verbesserung - 3471017 Ergebnisse / Sekunde, a + 12% gegenüber der vorherigen Bestmarke.

Update 2

Ich habe mein Bestes versucht, um alle vorgeschlagenen Lösungen und seine Kreuzmutationen zu sammeln und es als a veröffentlicht kleines Benchmark-Framework bei Github. Zur Zeit sind 17 Algorithmen vorhanden. Einer von ihnen ist "besonders" - Voo1 Algorithmus (von SO Benutzer Voo zur Verfügung gestellt) verwendet komplizierte Reflektions-Tricks und erzielt dadurch stellare Geschwindigkeiten, aber es vermasselt den Zustand der JVM-Streicher, daher wird es separat bewertet.

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

  • Debian sid
  • Linux 2.6.39-2-amd64 (x86_64)
  • Java installiert von einem Paket sun-java6-jdk-6.24-1, JVM identifiziert sich 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 ausgeführt:

Gleiche einzelne Zeichenfolge

Dieser Modus arbeitet mit einer einzigen Zeichenfolge von StringSourceKlasse als Konstante. 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 │ ArrayOfByteUTF8Konst
  756 086 │ MatcherReplace
  598 945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

In gezeichneter Form: Gleiches einzelnes Zeichenkettendiagramm http://www.greycat.ru/img/os-chart-single.png

Mehrere Zeichenfolgen, 100% der Zeichenfolgen enthalten Steuerzeichen

Der Quellenzeichenfolgenanbieter hat viele zufällige Zeichenfolgen mit dem Zeichensatz (0..127) vorgeneriert - daher enthielten fast alle Zeichenfolgen mindestens ein Steuerzeichen. Algorithmen erhielten Strings von diesem vorgenerierten Array im Round-Robin-Modus.

 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 │ ArrayOfByteUTF8Konst
  778 089 │ StringBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceAll

In gezeichneter Form: Mehrere Strings, 100% Konzentration http://www.greycat.ru/img/os-chart-multi100.png

Mehrere Zeichenfolgen, 1% der Zeichenfolgen enthalten Steuerzeichen

Wie zuvor, aber nur 1% der Zeichenfolgen wurde mit Steuerzeichen generiert - andere 99% wurden mit dem Zeichensatz [32..127] generiert, sodass sie keine Steuerzeichen enthalten konnten. Diese synthetische Ladung 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 │ ArrayOfByteUTF8Konst
  841 963 │ StringBuilderCodePoint
  606 465 │ MatcherReplace
  501 555 │ StringReplaceAll
  381 185 │ ArrayOfByteWindows1251

In gezeichneter Form: Mehrere Zeichenketten, 1% Konzentration http://www.greycat.ru/img/os-chart-multi1.png

Es ist sehr schwer für mich, zu entscheiden, wer die beste Antwort gegeben hat, aber angesichts der realen Anwendung, die beste Lösung von Ed Staub gegeben wurde, wäre es wohl angemessen, seine Antwort zu markieren. Danke für alle, die daran teilgenommen haben, Ihre Eingabe war sehr hilfreich und von unschätzbarem Wert. Fühlen Sie sich frei, die Testsuite auf Ihrer Box zu betreiben und noch bessere Lösungen vorzuschlagen (funktionierende JNI-Lösung, irgendjemand?).

Verweise


76
2017-08-23 13:10


Ursprung


Antworten:


Wenn es sinnvoll ist, diese Methode in eine Klasse einzubetten, die nicht über 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);

etc...

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

Wenn dies bei potentiell großen Strings verwendet werden soll und das Speicherleck problematisch ist, kann eine schwache Referenz verwendet werden.


9
2017-08-23 19:32



die Verwendung von 1 Char-Array könnte ein bisschen 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 Mikro-Optimierung, 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
2017-08-23 13:20



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

Ich bin sicher, dass jeder, der die Diskussion bis jetzt verfolgt hat, weiß, dass dies so ziemlich jedes grundlegende Programmierprinzip verletzt, aber naja. Das Folgende funktioniert jedoch nur dann, wenn das verwendete Zeichenarray des Strings nicht von anderen Strings gemeinsam genutzt wird. Wenn es das tut, hat jedes Recht, dich zu töten (ohne Aufrufe von substring () und mit literalen Strings) das sollte funktionieren, da ich nicht verstehe, warum die JVM einzigartige Zeichenketten von einer externen Quelle lesen würde. Vergessen Sie jedoch nicht, dass der Benchmark-Code es nicht tut - das ist sehr wahrscheinlich und würde die Reflektionslösung offensichtlich unterstützen.

Wie auch immer wir gehen:

    // 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, der bekommt 3477148.18ops/s gegen 2616120.89ops/s für die alte Variante. Ich bin mir ziemlich sicher, dass der einzige Weg, das zu schlagen, sein könnte, es in C zu schreiben (wahrscheinlich nicht) oder eine völlig andere Herangehensweise, über die bisher noch niemand nachgedacht hat. Obwohl ich mir absolut nicht sicher bin, ob das Timing über verschiedene Plattformen hinweg stabil ist, ergeben sich zumindest zuverlässige Ergebnisse auf meiner Box (Java7, Win7 x64).


9
2017-08-24 12:55



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


2
2017-08-23 13:37



IANA Low-Level-Java-Performance-Junkie, aber haben Sie es versucht entrolling Ihre Hauptschleife? Es scheint, dass es einigen CPUs erlauben könnte, Prüfungen parallel durchzuführen.

Ebenfalls, Dies hat einige lustige Ideen für Optimierungen.


1
2017-08-23 13:24



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

Nicht besonders gut dokumentiert, aber naja. Auf geht's - Ich habe sowohl die Algorithmen von Ratchet Freak als auch die Basisversion hinzugefügt. Im Moment initialisiere ich zufällig eine 200 Zeichen lange Zeichenfolge mit gleichmäßig verteilten Zeichen im Bereich [0, 200].


1
2017-08-23 14:52



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

Wenn du meinst String#getBytes("utf-8") etc .: Das sollte nicht schneller sein - bis auf etwas besseres Caching - da Charset.forName("utf-8")wird intern verwendet, wenn der Zeichensatz nicht zwischengespeichert wird.

Eine Sache könnte sein, dass Sie verschiedene Zeichensätze verwenden (oder vielleicht etwas von Ihrem Code transparent), aber der Zeichensatz zwischengespeichert wird StringCoding ändert sich nicht.


0
2017-08-23 13:22