Jaki jest najszybszy sposób usunięcia wszystkich niedrukowalnych znaków z a Stringw Javie?

Do tej pory próbowałem i mierzyłem na 138-bajtowym, 131-znakowym łańcuchu:

• String's replaceAll()- najwolniejsza metoda
  • 517009 wyników / sek
• Wstępnie skompiluj Pattern, a następnie użyj Matchera replaceAll()
  • 637836 wyników / sek
• Użyj StringBuffer, uzyskaj punkty kodowe używając codepointAt()jeden po drugim i dołącz do StringBuffer
  • 711946 wyników / sek
• Użyj StringBuffer, pobierz znaki używając charAt()jeden po drugim i dołącz do StringBuffer
  • 1052964 wyników / sek
• Wstępnie przydziel char[]bufor, pobierz znaki charAt()jeden po drugim i wypełnij ten bufor, a następnie przekonwertuj z powrotem na łańcuch
  • 2022653 wyników / sek
• Wstępnie przydziel 2 char[]bufory - stary i nowy, pobierz wszystkie znaki dla istniejącego String na raz za pomocą getChars(), iteruj po starym buforze jeden po drugim i wypełnij nowy bufor, a następnie przekonwertuj nowy bufor na String - moją własną najszybszą wersję
  • 2502502 wyników / sek
• Sam materiał 2 - obwody z zastosowaniem wyłącznie byte[], getBytes()oraz określanie kodowanie jako „UTF-8”
  • 857485 wyników / sek
• To samo z 2 byte[]buforami, ale określanie kodowania jako stałejCharset.forName("utf-8")
  • 791076 wyników / sek
• To samo z 2 byte[]buforami, ale określanie kodowania jako 1-bajtowego lokalnego kodowania (mało rozsądne)
  • 370164 wyników / sek

Moja najlepsza próba była następująca:

    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);

Jakieś przemyślenia, jak uczynić to jeszcze szybszym?

Dodatkowe punkty za odpowiedź na bardzo dziwne pytanie: dlaczego użycie nazwy zestawu znaków „utf-8” bezpośrednio daje lepszą wydajność niż użycie wstępnie przydzielonej stałej statycznej Charset.forName("utf-8")?

Aktualizacja

• Sugestia maniaka zapadkowego daje imponującą wydajność 3105590 na sekundę, co oznacza wzrost o + 24%!
• Sugestia Eda Stauba daje kolejną poprawę - 3471017 wyników na sekundę, + 12% w stosunku do poprzedniego najlepszego wyniku.

Zaktualizuj 2

Próbowałem zebrać wszystkie proponowane rozwiązania i ich krzyżowe mutacje i opublikowałem je jako mały framework do testów porównawczych na github . Obecnie obsługuje 17 algorytmów. Jeden z nich jest „specjalny” - algorytm Voo1 ( dostarczony przez użytkownika SO Voo ) wykorzystuje skomplikowane sztuczki odbicia, dzięki czemu osiąga fantastyczne prędkości, ale psuje stan ciągów JVM, dlatego jest testowany oddzielnie.

Możesz to sprawdzić i uruchomić, aby określić wyniki na swoim pudełku. Oto podsumowanie moich wyników. To specyfikacje:

• Debian sid
• Linux 2.6.39-2-amd64 (x86_64)
• Java zainstalowana z pakietu sun-java6-jdk-6.24-1, JVM identyfikuje się jako
  • Java (TM) SE Runtime Environment (kompilacja 1.6.0_24-b07)
  • 64-bitowa maszyna wirtualna serwera Java HotSpot (TM) (wersja 19.1-b02, tryb mieszany)

Różne algorytmy pokazują ostatecznie różne wyniki przy różnych zestawach danych wejściowych. Przeprowadziłem test porównawczy w 3 trybach:

Ten sam pojedynczy ciąg

Ten tryb działa na tym samym pojedynczym łańcuchu dostarczonym przez StringSourceklasę jako stała. Ostateczna rozgrywka to:

 Ops / s │ Algorytm
──────────┼──────────────────────────────
6 535 947 │ Voo1
──────────┼──────────────────────────────
5 350454 │ RatchetFreak2EdStaub1GreyCat1
5 249 343 │ EdStaub1
5 002501 │ EdStaub1GreyCat1
4 859 086 │ ArrayOfCharFromStringCharAt
4 295 532 │ RatchetFreak1
4 045307 │ ArrayOfCharFromArrayOfChar
2790178 │ RatchetFreak2EdStaub1GreyCat2
2 583 311 │ RatchetFreak2
1 274 859 │ StringBuilderChar
1 138174 │ StringBuilderCodePoint
  994 727 │ ArrayOfByteUTF8String
  918 611 │ ArrayOfByteUTF8Const
  756 086 │ MatcherReplace
  598 945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

W formie _wykresów : _{(źródło: greycat.ru )}

Wiele ciągów, 100% ciągów zawiera znaki sterujące

Dostawca ciągu źródłowego wstępnie wygenerował wiele losowych ciągów przy użyciu zestawu znaków (0..127) - w ten sposób prawie wszystkie ciągi zawierały co najmniej jeden znak sterujący. Algorytmy otrzymywały ciągi z tej wstępnie wygenerowanej tablicy w sposób okrężny.

 Ops / s │ Algorytm
──────────┼──────────────────────────────
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
  377829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceAll

W formie _wykresów : _{(źródło: greycat.ru )}

Wiele ciągów, 1% ciągów zawiera znaki sterujące

Tak samo jak poprzednio, ale tylko 1% łańcuchów zostało wygenerowanych ze znaków sterujących - pozostałe 99% zostało wygenerowanych przy użyciu zestawu znaków [32..127], więc nie mogły one w ogóle zawierać znaków sterujących. To syntetyczne obciążenie jest najbliższe rzeczywistemu zastosowaniu tego algorytmu u mnie.

 Ops / s │ Algorytm
──────────┼──────────────────────────────
3 711 952 │ Voo1
──────────┼──────────────────────────────
2 851440 │ EdStaub1GreyCat1
2 455 796 │ EdStaub1
2 426 007 │ ArrayOfCharFromStringCharAt
2 347 969 │ RatchetFreak2EdStaub1GreyCat2
2 242 152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1 922707 │ RatchetFreak2EdStaub1GreyCat1
1 857010 │ RatchetFreak2
1 023 751 │ ArrayOfByteUTF8String
  939 055 │ StringBuilderChar
  907194 │ ArrayOfByteUTF8Const
  841963 │ StringBuilderCodePoint
  606 465 │ MatcherReplace
  501555 │ StringReplaceAll
  381 185 │ ArrayOfByteWindows1251

W formie _wykresów : _{(źródło: greycat.ru )}

Bardzo trudno jest mi zdecydować, kto udzielił najlepszej odpowiedzi, ale biorąc pod uwagę rzeczywistą aplikację, najlepsze rozwiązanie zostało podane / zainspirowane przez Eda Stauba, myślę, że byłoby uczciwie zaznaczyć jego odpowiedź. Dziękujemy wszystkim, którzy wzięli w tym udział, Twój wkład był bardzo pomocny i nieoceniony. Zapraszam do uruchomienia zestawu testów na swoim komputerze i zaproponowania jeszcze lepszych rozwiązań (działające rozwiązanie JNI, ktoś?).

Bibliografia

• Repozytorium GitHub z pakietem do testów porównawczych

Jeśli rozsądne jest osadzenie tej metody w klasie, która nie jest współużytkowana przez wątki, możesz ponownie użyć bufora:

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);

itp...

To duża wygrana - około 20%, jak rozumiem obecnie najlepszy przypadek.

Jeśli ma to być używane na potencjalnie dużych łańcuchach, a „wyciek” pamięci jest problemem, można użyć słabej referencji.

użycie 1 tablicy znaków może działać trochę lepiej

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);

i unikałem wielokrotnych wezwań s.length();

kolejna mikro-optymalizacja, która może działać, to

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);

Cóż, przebiłem obecną najlepszą metodę (rozwiązanie dziwaka ze wstępnie przydzieloną tablicą) o około 30% według moich pomiarów. W jaki sposób? Sprzedając moją duszę.

Jestem pewien, że wszyscy, którzy do tej pory śledzili dyskusję, wiedzą, że narusza to prawie każdą podstawową zasadę programowania, ale cóż. W każdym razie poniższe działa tylko wtedy, gdy użyta tablica znaków ciągu nie jest dzielona między innymi ciągami - jeśli tak, ktokolwiek musi to debugować, będzie miał pełne prawo zdecydować cię zabić (bez wywołań funkcji podciąg () i używania tego na ciągach literałów to powinno działać, ponieważ nie rozumiem, dlaczego JVM miałby internować unikalne ciągi odczytywane z zewnętrznego źródła). Chociaż nie zapomnij upewnić się, że kod benchmarku tego nie robi - jest to bardzo prawdopodobne i oczywiście pomogłoby w rozwiązaniu refleksji.

Tak czy inaczej zaczynamy:

    // 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;
    }

W przypadku mojego ciągu testowego, który dostaje w 3477148.18ops/sporównaniu 2616120.89ops/sze starym wariantem. Jestem całkiem pewien, że jedynym sposobem na pokonanie tego mogłoby być napisanie tego w C (chociaż prawdopodobnie nie) lub zupełnie inne podejście, o którym nikt do tej pory nie pomyślał. Chociaż nie jestem absolutnie pewien, czy czas jest stabilny na różnych platformach - daje wiarygodne wyniki przynajmniej na moim komputerze (Java7, Win7 x64).

Możesz podzielić zadanie na kilka równoległych podzadań, w zależności od ilości procesora.

Byłem taki wolny i napisałem mały test porównawczy dla różnych algorytmów. To nie jest idealne, ale biorę minimum 1000 uruchomień danego algorytmu 10000 razy na losowym ciągu (domyślnie około 32/200% niedrukowalnych). To powinno zająć się takimi rzeczami, jak GC, inicjalizacja i tak dalej - nie ma tak dużego narzutu, że żaden algorytm nie powinien mieć co najmniej jednego uruchomienia bez większych przeszkód.

Niezbyt dobrze udokumentowane, ale cóż. Zaczynamy - zawarłem oba algorytmy ratchet freak oraz wersję podstawową. W tej chwili losowo inicjalizuję ciąg o długości 200 znaków z równomiernie rozmieszczonymi znakami w zakresie [0, 200).

Niski poziom wydajności Java IANA, ale czy próbowałeś rozwinąć główną pętlę ? Wydaje się, że może to pozwolić niektórym procesorom na równoległe przeprowadzanie kontroli.

Również ten ma kilka pomysłów zabawy dla optymalizacji.

dlaczego użycie nazwy zestawu znaków "utf-8" bezpośrednio daje lepszą wydajność niż użycie wstępnie przydzielonej statycznej stałej Charset.forName ("utf-8")?

Jeśli masz na myśli String#getBytes("utf-8")itp .: To nie powinno być szybsze - z wyjątkiem lepszego buforowania - ponieważCharset.forName("utf-8") jest używane wewnętrznie, jeśli zestaw znaków nie jest buforowany.

Jedną z rzeczy może być to, że używasz różnych zestawów znaków (lub może część twojego kodu działa w sposób przezroczysty), ale zestaw znaków zapisany w pamięci podręcznej StringCodingnie zmienia się.