Najszybszy sposób na usunięcie wszystkich niedrukowalnych znaków z ciągu Java

82

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 )Ten sam pojedynczy wykres łańcuchowy

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 strun, 100% koncentracji

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 )Wiele strun, stężenie 1%

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

java  string  performance  optimization  micro-optimization 
— GreyCat
źródło
21
„To pytanie pokazuje wysiłek badawczy” - hmm ... tak, zdaj. +1
— Gustav Barkefors
7
StringBuilderbędzie nieznacznie szybszy niż StringBufferniezsynchronizowany, wspominam o tym, ponieważ oznaczyłeś tomicro-optimization
2
@Jarrod Roberson: ok, więc ustawmy wszystkie pola tylko do odczytu jako ostateczne i wyodrębnijmy s.length()również z forpętli :-)
— home
3
Niektóre znaki są poniżej powierzchni np druku \ti \n. Wiele znaków powyżej 127 jest niedrukowalnych w Twoim zestawie znaków.
— Peter Lawrey
1
czy zainicjowałeś bufor ciągów o pojemności s.length()?
— ratchet freak

Odpowiedzi:

11

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.

— Ed Staub
źródło
Świetny pomysł! Jak dotąd liczba ta wzrosła do 3471017 ciągów na sekundę - czyli o 12% więcej niż w poprzedniej najlepszej wersji.
— GreyCat
25

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);
— maniak grzechotki
źródło
1
Dzięki! Twoja wersja daje 3105590 ciągów na sekundę - ogromna poprawa!
— GreyCat
newLen++;: a co ze stosowaniem preinkrementacji ++newLen;? - (również ++jw pętli). Zajrzyj tutaj: stackoverflow.com/questions/1546981/…
— Thomas
Dodanie finaldo tego algorytmu i użycie oldChars[newLen++]( ++newLenjest błędem - cały ciąg byłby przesunięty o 1!) Nie daje żadnych mierzalnych przyrostów wydajności (tj. Otrzymuję różnice ± 2..3%, które są porównywalne z różnicami różnych przebiegów)
— GreyCat
@grey Zrobiłem kolejną wersję z kilkoma innymi optymalizacjami
— ratchet freak
2
Hmm! To wspaniały pomysł! 99,9% ciągów w moim środowisku produkcyjnym tak naprawdę nie wymaga usuwania - mogę go dalej ulepszyć, aby wyeliminować nawet pierwszą char[]alokację i zwrócić String w takim stanie, w jakim jest, jeśli nie nastąpi usunięcie.
— GreyCat
11

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

— Voo
źródło
Dzięki za rozwiązanie, sprawdź aktualizację pytań - opublikowałem mój framework testowy i dodałem 3 wyniki testów dla 17 algorytmów. Twój algorytm jest zawsze na wierzchu, ale zmienia stan wewnętrzny Java String, łamiąc w ten sposób kontrakt „niezmienny String” => użycie go w rzeczywistych aplikacjach byłoby dość trudne. Test-mądry, tak, to najlepszy wynik, ale myślę, że
— ogłosimy
3
@GreyCat Tak, z pewnością ma pewne duże ograniczenia i szczerze mówiąc, napisałem to tylko dlatego, że jestem prawie pewien, że nie ma zauważalnego sposobu na dalsze ulepszenie obecnie najlepszego rozwiązania. Są sytuacje, w których jestem pewien, że będzie działać dobrze (bez podciągów ani wywołań stażystów przed usunięciem go), ale dzieje się tak z powodu wiedzy o jednej aktualnej wersji Hotspot (tj. Afaik nie będzie internować ciągów odczytanych z IO - nie być szczególnie przydatne). Może się przydać, jeśli naprawdę potrzebujesz tych dodatkowych x%, ale poza tym bardziej podstawowa, aby zobaczyć, ile jeszcze możesz poprawić;)
— Voo
1
Chociaż spróbuję wypróbować wersję JNI, jeśli znajdę czas - nigdy jej nie użyłem, więc byłoby to interesujące. Ale jestem prawie pewien, że będzie wolniejszy z powodu dodatkowego narzutu wywołań (ciągi znaków są o wiele za małe) i faktu, że JIT nie powinien mieć takich problemów z optymalizacją funkcji. Po prostu nie używaj, new String()jeśli twój ciąg nie został zmieniony, ale myślę, że już to masz.
— Voo
Próbowałem już zrobić dokładnie to samo w czystym C - i cóż, tak naprawdę nie pokazuje to zbytniej poprawy w stosunku do twojej wersji opartej na odbiciach. Wersja C działa około + 5..10% szybciej, niezbyt dobrze - myślałem, że będzie to co najmniej 1,5x-1,7x ...
— GreyCat
2

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

— umbr
źródło
Tak, też o tym myślałem, ale w mojej sytuacji nie przyniesie to żadnego wzrostu wydajności - ten algorytm usuwania zostałby wywołany w i tak masowo równoległym systemie.
— GreyCat
2
Poza tym, mogę się domyślać, że rozwidlenie kilku wątków do przetwarzania na każdy ciąg o długości 50-100 bajtów byłoby ogromną przesadą.
— GreyCat
Tak, rozwidlanie nici dla każdej małej struny nie jest dobrym pomysłem. Ale moduł równoważenia obciążenia może poprawić wydajność. BTW, czy testowałeś wydajność za pomocą StringBuilder zamiast StringBuffer, który ma brak wydajności, ponieważ jest zsynchronizowany.
— umbr
Moja konfiguracja produkcyjna uruchamia kilka oddzielnych procesów i wykorzystuje tyle równoległych procesorów i rdzeni, ile to możliwe, więc mogę swobodnie używać StringBuilderwszędzie bez żadnych problemów.
— GreyCat
2

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

— Voo
źródło
+1 za wysiłek - ale powinieneś był mnie zapytać - mam już podobny zestaw do testów porównawczych - tam testowałem moje algorytmy;)
— GreyCat
@GreyCat Cóż, mogłem, ale samo zrzucenie tego razem (i tak z istniejącego kodu) było prawdopodobnie szybsze;)
— Voo
1

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.

— Ryan Ransford
źródło
Wątpię, czy dałoby się tu jakikolwiek rozwinąć, ponieważ istnieją (a) zależności od kolejnych kroków algorytmu do poprzednich kroków, (b) nawet nie słyszałem, żeby ktokolwiek wykonywał ręczne rozwijanie pętli w Javie, dając jakieś niesamowite wyniki; JIT zwykle wykonuje dobrą robotę, rozwijając wszystko, co widzi, pasujące do zadania. Jednak dzięki za sugestię i link :)
— GreyCat
0

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ę.

— Tomasz
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.