Najszybszy sposób na iterację wszystkich znaków w łańcuchu

163

W Javie, jaki byłby najszybszy sposób na iterację wszystkich znaków w łańcuchu, to:

String str = "a really, really long string";
for (int i = 0, n = str.length(); i < n; i++) {
    char c = str.charAt(i);
}

Albo to:

char[] chars = str.toCharArray();
for (int i = 0, n = chars.length; i < n; i++) {
    char c = chars[i];
}

EDYTOWAĆ :

Chciałbym wiedzieć, czy koszt wielokrotnego wywoływania charAtmetody podczas długiej iteracji kończy się albo mniejszym, albo większym niż koszt wykonania pojedynczego wywołania toCharArrayna początku, a następnie bezpośredniego dostępu do tablicy podczas iteracji.

Byłoby wspaniale, gdyby ktoś mógł dostarczyć solidny punkt odniesienia dla różnych długości strun, mając na uwadze czas rozgrzewania JIT, czas uruchamiania JVM itp., A nie tylko różnicę między dwoma wywołaniami do System.currentTimeMillis().

Óscar López
źródło
18
Co się stało for (char c : chars)?
dasblinkenlight
Pierwsza z nich powinna być szybsza, a zresztą teoretycznie łańcuch znaków tablicy.
Keagan Ladds
Google jest często dobrym źródłem informacji: mkyong.com/java/…
Johan Sjöberg
2
Pytanie nie dotyczy wydajności korzystania z iteratorów dla każdego. Co chciałbym wiedzieć, czy koszt wielokrotnie nazywając charAtkończy się albo mniejszy lub większy niż koszt wykonywania pojedynczego połączenia dotoCharArray
Óscar López
1
Czy ktoś przeprowadził analizę za pomocą StringCharacterIterator ?
bdrx

Odpowiedzi:

352

PIERWSZA AKTUALIZACJA: Zanim wypróbujesz to kiedykolwiek w środowisku produkcyjnym (niezalecane), przeczytaj najpierw: http://www.javaspecialists.eu/archive/Issue237.html Począwszy od Java 9, opisane rozwiązanie nie będzie już działać , ponieważ teraz Java będzie domyślnie przechowywać łańcuchy jako bajt [].

DRUGA AKTUALIZACJA: od 25.10.2016 r. Na moim AMDx64 8core i source 1.8 nie ma różnicy między używaniem „charAt” a dostępem do pola. Wygląda na to, że jvm jest wystarczająco zoptymalizowany, aby wbudowywać i usprawniać wszelkie wywołania „string.charAt (n)”.

Wszystko zależy od długości Stringbadanego. Jeśli, jak mówi pytanie, dotyczy to długich ciągów, najszybszym sposobem sprawdzenia łańcucha jest użycie odbicia w celu uzyskania dostępu do kopii char[]łańcucha.

W pełni losowy test porównawczy z JDK 8 (win32 i win64) na 64 AMD Phenom II 4 core 955 @ 3,2 GHZ (zarówno w trybie klienta, jak iw trybie serwera) z 9 różnymi technikami (patrz poniżej!) Pokazuje, że używanie String.charAt(n)jest najszybsze w przypadku małych stringi, a użycie reflectiondo uzyskania dostępu do tablicy zaplecza String jest prawie dwukrotnie szybsze w przypadku dużych ciągów.

EKSPERYMENT

  • Wypróbowano 9 różnych technik optymalizacji.

  • Cała zawartość ciągu jest losowa

  • Test jest wykonywany dla rozmiarów strun w wielokrotności dwóch, zaczynając od 0,1,2,4,8,16 itd.

  • Testy są wykonywane 1000 razy na rozmiar łańcucha

  • Testy są za każdym razem tasowane w losowej kolejności. Innymi słowy, testy są wykonywane w losowej kolejności za każdym razem, gdy są wykonywane, ponad 1000 razy.

  • Cały zestaw testów jest wykonywany do przodu i do tyłu, aby pokazać wpływ rozgrzewania maszyny JVM na optymalizację i czasy.

  • Cały zestaw odbywa się dwukrotnie, raz w -clienttrybie, a drugi w -servertrybie.

WNIOSKI

tryb klienta (32 bity)

W przypadku ciągów o długości od 1 do 256 znaków wywołanie string.charAt(i)wygrywa ze średnim przetwarzaniem od 13,4 do 588 milionów znaków na sekundę.

Ponadto jest ogólnie 5,5% szybszy (klient) i 13,9% (serwer) w następujący sposób:

    for (int i = 0; i < data.length(); i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }

niż w ten sposób z lokalną zmienną końcową długości:

    final int len = data.length();
    for (int i = 0; i < len; i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }

W przypadku długich ciągów znaków o długości od 512 do 256 K , użycie odbicia w celu uzyskania dostępu do tablicy zaplecza String jest najszybsze. Ta technika jest prawie dwa razy szybsza niż String.charAt (i) (o 178% szybciej). Średnia prędkość w tym zakresie wynosiła 1,111 miliarda znaków na sekundę.

Pole należy uzyskać z wyprzedzeniem, a następnie można je ponownie wykorzystać w bibliotece na różnych ciągach. Co ciekawe, w przeciwieństwie do powyższego kodu, w przypadku dostępu do pola, posiadanie lokalnej zmiennej końcowej długości jest o 9% szybsze niż użycie „chars.length” w sprawdzaniu pętli. Oto jak najszybciej można skonfigurować dostęp do pola:

   final Field field = String.class.getDeclaredField("value");
   field.setAccessible(true);

   try {
       final char[] chars = (char[]) field.get(data);
       final int len = chars.length;
       for (int i = 0; i < len; i++) {
           if (chars[i] <= ' ') {
               doThrow();
           }
       }
       return len;
   } catch (Exception ex) {
       throw new RuntimeException(ex);
   }

Specjalne komentarze na temat trybu -server

Dostęp do pola zaczyna się wygrywać po 32-bitowych ciągach znaków w trybie serwera na 64-bitowej maszynie Java na moim komputerze AMD 64. Nie było to widoczne do długości 512 znaków w trybie klienta.

Warto również zauważyć, że myślę, że kiedy uruchamiałem JDK 8 (kompilacja 32-bitowa) w trybie serwera, ogólna wydajność była o 7% wolniejsza zarówno dla dużych, jak i małych ciągów. Było to w przypadku wczesnego wydania JDK 8 z kompilacją 121 grudnia 2013 r. Na razie wydaje się, że tryb serwera 32-bitowego jest wolniejszy niż tryb klienta 32-bitowego.

Biorąc to pod uwagę ... wydaje się, że jedynym trybem serwera, który warto wywołać, jest maszyna 64-bitowa. W przeciwnym razie faktycznie ogranicza wydajność.

W przypadku wersji 32-bitowej działającej -server modena AMD64 mogę powiedzieć:

  1. String.charAt (i) jest wyraźnym zwycięzcą. Chociaż między rozmiarami od 8 do 512 znaków byli zwycięzcy w kategorii „nowe” „ponowne wykorzystanie” i „pole”.
  2. String.charAt (i) działa o 45% szybciej w trybie klienta
  3. Dostęp do pola jest dwukrotnie szybszy w przypadku dużych ciągów znaków w trybie klienta.

Warto również powiedzieć, że String.chars () (Stream i wersja równoległa) to bust. O wiele wolniej niż w jakikolwiek inny sposób. StreamsAPI jest raczej powolny sposób, aby wykonywać operacje ogólnie ciągów.

Lista życzeń

Java String może mieć predykat akceptujący zoptymalizowane metody, takie jak include (predykat), forEach (konsument), forEachWithIndex (konsument). Tak więc, bez konieczności znajomości przez użytkownika długości lub powtarzania wywołań metod String, może to beep-beep beepprzyspieszyć analizowanie bibliotek .

Marz dalej :)

Happy Strings!

~ SH

W teście wykorzystano 9 następujących metod testowania ciągu znaków na obecność białych znaków:

„charAt1” - SPRAWDŹ ZAWARTOŚĆ STRINGU W ZWYKŁY SPOSÓB:

int charAtMethod1(final String data) {
    final int len = data.length();
    for (int i = 0; i < len; i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }
    return len;
}

„charAt2” - TAKIE SAME, JAK POWYŻEJ, ALE UŻYWAJ String.length () ZAMIAST TWORZENIA OSTATECZNEJ LOKALNEJ int NA DŁUGOŚĆ

int charAtMethod2(final String data) {
    for (int i = 0; i < data.length(); i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }
    return data.length();
}

„stream” - UŻYJ NOWEJ JAVA-8 String's IntStream I PRZEKAŻ PROGNOZĘ DO SPRAWDZENIA

int streamMethod(final String data, final IntPredicate predicate) {
    if (data.chars().anyMatch(predicate)) {
        doThrow();
    }
    return data.length();
}

"streamPara" - TAKIE SAMO JAK POWYŻEJ, ALE OH-LA-LA - JEDŹ RÓWNOLEGLE !!!

// avoid this at all costs
int streamParallelMethod(final String data, IntPredicate predicate) {
    if (data.chars().parallel().anyMatch(predicate)) {
        doThrow();
    }
    return data.length();
}

„reuse” - WYPEŁNIJ WIELOKROTNEGO UŻYTKU [] ZAWARTOŚCIĄ STRINGS

int reuseBuffMethod(final char[] reusable, final String data) {
    final int len = data.length();
    data.getChars(0, len, reusable, 0);
    for (int i = 0; i < len; i++) {
        if (reusable[i] <= ' ') {
            doThrow();
        }
    }
    return len;
}

"new1" - UZYSKAJ NOWĄ KOPIĘ ZNAKU [] Z STRUNU

int newMethod1(final String data) {
    final int len = data.length();
    final char[] copy = data.toCharArray();
    for (int i = 0; i < len; i++) {
        if (copy[i] <= ' ') {
            doThrow();
        }
    }
    return len;
}

„nowy2” - TAKIE SAME JAK POWYŻEJ, ALE UŻYWAJ „DLA KAŻDEGO”

int newMethod2(final String data) {
    for (final char c : data.toCharArray()) {
        if (c <= ' ') {
            doThrow();
        }
    }
    return data.length();
}

"field1" - FANCY !! UZYSKAJ POLE DOSTĘPU DO WEWNĘTRZNEGO ZNAKU STRUNY []

int fieldMethod1(final Field field, final String data) {
    try {
        final char[] chars = (char[]) field.get(data);
        final int len = chars.length;
        for (int i = 0; i < len; i++) {
            if (chars[i] <= ' ') {
                doThrow();
            }
        }
        return len;
    } catch (Exception ex) {
        throw new RuntimeException(ex);
    }
}

„field2” - TAKIE SAME JAK POWYŻEJ, ALE UŻYJ „DLA KAŻDEGO”

int fieldMethod2(final Field field, final String data) {
    final char[] chars;
    try {
        chars = (char[]) field.get(data);
    } catch (Exception ex) {
        throw new RuntimeException(ex);
    }
    for (final char c : chars) {
        if (c <= ' ') {
            doThrow();
        }
    }
    return chars.length;
}

WYNIKI KOMPOZYTOWE DLA -clientTRYBU KLIENTA (łącznie testy w przód i wstecz)

Uwaga: tryb -client z 32-bitową Javą i -server z 64-bitową Javą jest taki sam, jak poniżej na moim komputerze AMD64.

Size     WINNER  charAt1 charAt2  stream streamPar   reuse    new1    new2  field1  field2
1        charAt    77.0     72.0   462.0     584.0   127.5    89.5    86.0   159.5   165.0
2        charAt    38.0     36.5   284.0   32712.5    57.5    48.3    50.3    89.0    91.5
4        charAt    19.5     18.5   458.6    3169.0    33.0    26.8    27.5    54.1    52.6
8        charAt     9.8      9.9   100.5    1370.9    17.3    14.4    15.0    26.9    26.4
16       charAt     6.1      6.5    73.4     857.0     8.4     8.2     8.3    13.6    13.5
32       charAt     3.9      3.7    54.8     428.9     5.0     4.9     4.7     7.0     7.2
64       charAt     2.7      2.6    48.2     232.9     3.0     3.2     3.3     3.9     4.0
128      charAt     2.1      1.9    43.7     138.8     2.1     2.6     2.6     2.4     2.6
256      charAt     1.9      1.6    42.4      90.6     1.7     2.1     2.1     1.7     1.8
512      field1     1.7      1.4    40.6      60.5     1.4     1.9     1.9     1.3     1.4
1,024    field1     1.6      1.4    40.0      45.6     1.2     1.9     2.1     1.0     1.2
2,048    field1     1.6      1.3    40.0      36.2     1.2     1.8     1.7     0.9     1.1
4,096    field1     1.6      1.3    39.7      32.6     1.2     1.8     1.7     0.9     1.0
8,192    field1     1.6      1.3    39.6      30.5     1.2     1.8     1.7     0.9     1.0
16,384   field1     1.6      1.3    39.8      28.4     1.2     1.8     1.7     0.8     1.0
32,768   field1     1.6      1.3    40.0      26.7     1.3     1.8     1.7     0.8     1.0
65,536   field1     1.6      1.3    39.8      26.3     1.3     1.8     1.7     0.8     1.0
131,072  field1     1.6      1.3    40.1      25.4     1.4     1.9     1.8     0.8     1.0
262,144  field1     1.6      1.3    39.6      25.2     1.5     1.9     1.9     0.8     1.0

WYNIKI KOMPOZYTOWE DLA -serverTRYBU SERWEROWEGO (łącznie testy w przód i wstecz)

Uwaga: to jest test dla 32-bitowej wersji Java działającej w trybie serwera na AMD64. Tryb serwera dla 64-bitowej Javy był taki sam, jak dla 32-bitowej Javy w trybie klienta, z wyjątkiem tego, że dostęp do pola zaczyna wygrywać po rozmiarze 32 znaków.

Size     WINNER  charAt1 charAt2  stream streamPar   reuse    new1    new2  field1  field2
1        charAt     74.5    95.5   524.5     783.0    90.5   102.5    90.5   135.0   151.5
2        charAt     48.5    53.0   305.0   30851.3    59.3    57.5    52.0    88.5    91.8
4        charAt     28.8    32.1   132.8    2465.1    37.6    33.9    32.3    49.0    47.0
8          new2     18.0    18.6    63.4    1541.3    18.5    17.9    17.6    25.4    25.8
16         new2     14.0    14.7   129.4    1034.7    12.5    16.2    12.0    16.0    16.6
32         new2      7.8     9.1    19.3     431.5     8.1     7.0     6.7     7.9     8.7
64        reuse      6.1     7.5    11.7     204.7     3.5     3.9     4.3     4.2     4.1
128       reuse      6.8     6.8     9.0     101.0     2.6     3.0     3.0     2.6     2.7
256      field2      6.2     6.5     6.9      57.2     2.4     2.7     2.9     2.3     2.3
512       reuse      4.3     4.9     5.8      28.2     2.0     2.6     2.6     2.1     2.1
1,024    charAt      2.0     1.8     5.3      17.6     2.1     2.5     3.5     2.0     2.0
2,048    charAt      1.9     1.7     5.2      11.9     2.2     3.0     2.6     2.0     2.0
4,096    charAt      1.9     1.7     5.1       8.7     2.1     2.6     2.6     1.9     1.9
8,192    charAt      1.9     1.7     5.1       7.6     2.2     2.5     2.6     1.9     1.9
16,384   charAt      1.9     1.7     5.1       6.9     2.2     2.5     2.5     1.9     1.9
32,768   charAt      1.9     1.7     5.1       6.1     2.2     2.5     2.5     1.9     1.9
65,536   charAt      1.9     1.7     5.1       5.5     2.2     2.4     2.4     1.9     1.9
131,072  charAt      1.9     1.7     5.1       5.4     2.3     2.5     2.5     1.9     1.9
262,144  charAt      1.9     1.7     5.1       5.1     2.3     2.5     2.5     1.9     1.9

PEŁNY URUCHOMIONY KOD PROGRAMU

(aby przetestować na Javie 7 i wcześniejszych, usuń testy dwóch strumieni)

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.function.IntPredicate;

/**
 * @author Saint Hill <http://stackoverflow.com/users/1584255/saint-hill>
 */
public final class TestStrings {

    // we will not test strings longer than 512KM
    final int MAX_STRING_SIZE = 1024 * 256;

    // for each string size, we will do all the tests
    // this many times
    final int TRIES_PER_STRING_SIZE = 1000;

    public static void main(String[] args) throws Exception {
        new TestStrings().run();
    }

    void run() throws Exception {

        // double the length of the data until it reaches MAX chars long
        // 0,1,2,4,8,16,32,64,128,256 ... 
        final List<Integer> sizes = new ArrayList<>();
        for (int n = 0; n <= MAX_STRING_SIZE; n = (n == 0 ? 1 : n * 2)) {
            sizes.add(n);
        }

        // CREATE RANDOM (FOR SHUFFLING ORDER OF TESTS)
        final Random random = new Random();

        System.out.println("Rate in nanoseconds per character inspected.");
        System.out.printf("==== FORWARDS (tries per size: %s) ==== \n", TRIES_PER_STRING_SIZE);

        printHeadings(TRIES_PER_STRING_SIZE, random);

        for (int size : sizes) {
            reportResults(size, test(size, TRIES_PER_STRING_SIZE, random));
        }

        // reverse order or string sizes
        Collections.reverse(sizes);

        System.out.println("");
        System.out.println("Rate in nanoseconds per character inspected.");
        System.out.printf("==== BACKWARDS (tries per size: %s) ==== \n", TRIES_PER_STRING_SIZE);

        printHeadings(TRIES_PER_STRING_SIZE, random);

        for (int size : sizes) {
            reportResults(size, test(size, TRIES_PER_STRING_SIZE, random));

        }
    }

    ///
    ///
    ///  METHODS OF CHECKING THE CONTENTS
    ///  OF A STRING. ALWAYS CHECKING FOR
    ///  WHITESPACE (CHAR <=' ')
    ///  
    ///
    // CHECK THE STRING CONTENTS
    int charAtMethod1(final String data) {
        final int len = data.length();
        for (int i = 0; i < len; i++) {
            if (data.charAt(i) <= ' ') {
                doThrow();
            }
        }
        return len;
    }

    // SAME AS ABOVE BUT USE String.length()
    // instead of making a new final local int 
    int charAtMethod2(final String data) {
        for (int i = 0; i < data.length(); i++) {
            if (data.charAt(i) <= ' ') {
                doThrow();
            }
        }
        return data.length();
    }

    // USE new Java-8 String's IntStream
    // pass it a PREDICATE to do the checking
    int streamMethod(final String data, final IntPredicate predicate) {
        if (data.chars().anyMatch(predicate)) {
            doThrow();
        }
        return data.length();
    }

    // OH LA LA - GO PARALLEL!!!
    int streamParallelMethod(final String data, IntPredicate predicate) {
        if (data.chars().parallel().anyMatch(predicate)) {
            doThrow();
        }
        return data.length();
    }

    // Re-fill a resuable char[] with the contents
    // of the String's char[]
    int reuseBuffMethod(final char[] reusable, final String data) {
        final int len = data.length();
        data.getChars(0, len, reusable, 0);
        for (int i = 0; i < len; i++) {
            if (reusable[i] <= ' ') {
                doThrow();
            }
        }
        return len;
    }

    // Obtain a new copy of char[] from String
    int newMethod1(final String data) {
        final int len = data.length();
        final char[] copy = data.toCharArray();
        for (int i = 0; i < len; i++) {
            if (copy[i] <= ' ') {
                doThrow();
            }
        }
        return len;
    }

    // Obtain a new copy of char[] from String
    // but use FOR-EACH
    int newMethod2(final String data) {
        for (final char c : data.toCharArray()) {
            if (c <= ' ') {
                doThrow();
            }
        }
        return data.length();
    }

    // FANCY!
    // OBTAIN FIELD FOR ACCESS TO THE STRING'S
    // INTERNAL CHAR[]
    int fieldMethod1(final Field field, final String data) {
        try {
            final char[] chars = (char[]) field.get(data);
            final int len = chars.length;
            for (int i = 0; i < len; i++) {
                if (chars[i] <= ' ') {
                    doThrow();
                }
            }
            return len;
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
    }

    // same as above but use FOR-EACH
    int fieldMethod2(final Field field, final String data) {
        final char[] chars;
        try {
            chars = (char[]) field.get(data);
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
        for (final char c : chars) {
            if (c <= ' ') {
                doThrow();
            }
        }
        return chars.length;
    }

    /**
     *
     * Make a list of tests. We will shuffle a copy of this list repeatedly
     * while we repeat this test.
     *
     * @param data
     * @return
     */
    List<Jobber> makeTests(String data) throws Exception {
        // make a list of tests
        final List<Jobber> tests = new ArrayList<Jobber>();

        tests.add(new Jobber("charAt1") {
            int check() {
                return charAtMethod1(data);
            }
        });

        tests.add(new Jobber("charAt2") {
            int check() {
                return charAtMethod2(data);
            }
        });

        tests.add(new Jobber("stream") {
            final IntPredicate predicate = new IntPredicate() {
                public boolean test(int value) {
                    return value <= ' ';
                }
            };

            int check() {
                return streamMethod(data, predicate);
            }
        });

        tests.add(new Jobber("streamPar") {
            final IntPredicate predicate = new IntPredicate() {
                public boolean test(int value) {
                    return value <= ' ';
                }
            };

            int check() {
                return streamParallelMethod(data, predicate);
            }
        });

        // Reusable char[] method
        tests.add(new Jobber("reuse") {
            final char[] cbuff = new char[MAX_STRING_SIZE];

            int check() {
                return reuseBuffMethod(cbuff, data);
            }
        });

        // New char[] from String
        tests.add(new Jobber("new1") {
            int check() {
                return newMethod1(data);
            }
        });

        // New char[] from String
        tests.add(new Jobber("new2") {
            int check() {
                return newMethod2(data);
            }
        });

        // Use reflection for field access
        tests.add(new Jobber("field1") {
            final Field field;

            {
                field = String.class.getDeclaredField("value");
                field.setAccessible(true);
            }

            int check() {
                return fieldMethod1(field, data);
            }
        });

        // Use reflection for field access
        tests.add(new Jobber("field2") {
            final Field field;

            {
                field = String.class.getDeclaredField("value");
                field.setAccessible(true);
            }

            int check() {
                return fieldMethod2(field, data);
            }
        });

        return tests;
    }

    /**
     * We use this class to keep track of test results
     */
    abstract class Jobber {

        final String name;
        long nanos;
        long chars;
        long runs;

        Jobber(String name) {
            this.name = name;
        }

        abstract int check();

        final double nanosPerChar() {
            double charsPerRun = chars / runs;
            long nanosPerRun = nanos / runs;
            return charsPerRun == 0 ? nanosPerRun : nanosPerRun / charsPerRun;
        }

        final void run() {
            runs++;
            long time = System.nanoTime();
            chars += check();
            nanos += System.nanoTime() - time;
        }
    }

    // MAKE A TEST STRING OF RANDOM CHARACTERS A-Z
    private String makeTestString(int testSize, char start, char end) {
        Random r = new Random();
        char[] data = new char[testSize];
        for (int i = 0; i < data.length; i++) {
            data[i] = (char) (start + r.nextInt(end));
        }
        return new String(data);
    }

    // WE DO THIS IF WE FIND AN ILLEGAL CHARACTER IN THE STRING
    public void doThrow() {
        throw new RuntimeException("Bzzzt -- Illegal Character!!");
    }

    /**
     * 1. get random string of correct length 2. get tests (List<Jobber>) 3.
     * perform tests repeatedly, shuffling each time
     */
    List<Jobber> test(int size, int tries, Random random) throws Exception {
        String data = makeTestString(size, 'A', 'Z');
        List<Jobber> tests = makeTests(data);
        List<Jobber> copy = new ArrayList<>(tests);
        while (tries-- > 0) {
            Collections.shuffle(copy, random);
            for (Jobber ti : copy) {
                ti.run();
            }
        }
        // check to make sure all char counts the same
        long runs = tests.get(0).runs;
        long count = tests.get(0).chars;
        for (Jobber ti : tests) {
            if (ti.runs != runs && ti.chars != count) {
                throw new Exception("Char counts should match if all correct algorithms");
            }
        }
        return tests;
    }

    private void printHeadings(final int TRIES_PER_STRING_SIZE, final Random random) throws Exception {
        System.out.print("  Size");
        for (Jobber ti : test(0, TRIES_PER_STRING_SIZE, random)) {
            System.out.printf("%9s", ti.name);
        }
        System.out.println("");
    }

    private void reportResults(int size, List<Jobber> tests) {
        System.out.printf("%6d", size);
        for (Jobber ti : tests) {
            System.out.printf("%,9.2f", ti.nanosPerChar());
        }
        System.out.println("");
    }
}
Koordynator
źródło
1
Czy ten test został uruchomiony w wirtualnej maszynie wirtualnej serwera czy w maszynie JVM klienta? Najlepsze optymalizacje są wykonywane tylko w serwerowej JVM. Jeśli działałeś przy użyciu domyślnej 32-bitowej maszyny JVM i bez argumentów, to działałeś w trybie klienta.
ceklock
2
Uzyskanie bufora zapasowego jest problematyczne w przypadku podciągów lub łańcuchów utworzonych za pomocą String (char [], int, int), ponieważ otrzymujesz cały bufor (przynajmniej na Androidzie), ale indeksowanie będzie oparte na zeru. Jeśli jednak wiesz, że nie masz podciągu, będzie działać dobrze.
prewett
5
Każdy pomysł, dlaczego „for (int i = 0; i <data.length (); i ++)” jest szybszy niż definiowanie data.length () jako końcowej zmiennej lokalnej?
skyin
2
Definiowanie zmiennej w ogóle wymaga operacji na stosie w kodzie bajtowym metody. Ale optymalizacje wynikające z rozpoznania algorytmu mogą przyspieszyć powtarzanie operacji w rzeczywistym kodzie maszynowym, bez narzutu związanego z alokacją zmiennej. Takie optymalizacje czasami istnieją w kompilatorach kodu bajtowego, czasami nie. Wszystko zależy od tego, czy jvm jest wystarczająco sprytny :-)
Koordynator
2
@DavidS liczby to szybkość (w nanosekundach) przypadająca na sprawdzany znak. Mniejsze znaczy lepsze.
Koordynator
14

To tylko mikro-optymalizacja, o którą nie powinieneś się martwić.

char[] chars = str.toCharArray();

zwraca kopię strtablic znaków (w JDK zwraca kopię znaków przez wywołanie System.arrayCopy).

Poza tym str.charAt()sprawdza tylko, czy indeks rzeczywiście znajduje się w granicach i zwraca znak w indeksie tablicy.

Pierwsza nie tworzy dodatkowej pamięci w JVM.

Buhake Sindi
źródło
Nie odpowiada na pytanie. To pytanie dotyczy wydajności. Z tego, co wiesz, OP mógł odkryć, że iterowanie po łańcuchach jest głównym kosztem ich zastosowania.
rghome
9

Z ciekawości i dla porównania z odpowiedzią Saint Hill.

Jeśli potrzebujesz przetwarzać duże ilości danych, nie powinieneś używać maszyny JVM w trybie klienta. Tryb klienta nie jest przeznaczony do optymalizacji.

Porównajmy wyniki testów porównawczych @Saint Hill przy użyciu maszyny JVM w trybie klienta i serwera.

Core2Quad Q6600 G0 @ 2.4GHz
JavaSE 1.7.0_40

Zobacz też: Rzeczywiste różnice między „serwerem java” a „klientem java”?


TRYB KLIENTA:

len =      2:    111k charAt(i),  105k cbuff[i],   62k new[i],   17k field access.   (chars/ms) 
len =      4:    285k charAt(i),  166k cbuff[i],  114k new[i],   43k field access.   (chars/ms) 
len =      6:    315k charAt(i),  230k cbuff[i],  162k new[i],   69k field access.   (chars/ms) 
len =      8:    333k charAt(i),  275k cbuff[i],  181k new[i],   85k field access.   (chars/ms) 
len =     12:    342k charAt(i),  342k cbuff[i],  222k new[i],  117k field access.   (chars/ms) 
len =     16:    363k charAt(i),  347k cbuff[i],  275k new[i],  152k field access.   (chars/ms) 
len =     20:    363k charAt(i),  392k cbuff[i],  289k new[i],  180k field access.   (chars/ms) 
len =     24:    375k charAt(i),  428k cbuff[i],  311k new[i],  205k field access.   (chars/ms) 
len =     28:    378k charAt(i),  474k cbuff[i],  341k new[i],  233k field access.   (chars/ms) 
len =     32:    376k charAt(i),  492k cbuff[i],  340k new[i],  251k field access.   (chars/ms) 
len =     64:    374k charAt(i),  551k cbuff[i],  374k new[i],  367k field access.   (chars/ms) 
len =    128:    385k charAt(i),  624k cbuff[i],  415k new[i],  509k field access.   (chars/ms) 
len =    256:    390k charAt(i),  675k cbuff[i],  436k new[i],  619k field access.   (chars/ms) 
len =    512:    394k charAt(i),  703k cbuff[i],  439k new[i],  695k field access.   (chars/ms) 
len =   1024:    395k charAt(i),  718k cbuff[i],  462k new[i],  742k field access.   (chars/ms) 
len =   2048:    396k charAt(i),  725k cbuff[i],  471k new[i],  767k field access.   (chars/ms) 
len =   4096:    396k charAt(i),  727k cbuff[i],  459k new[i],  780k field access.   (chars/ms) 
len =   8192:    397k charAt(i),  712k cbuff[i],  446k new[i],  772k field access.   (chars/ms) 

TRYB SERWERA:

len =      2:     86k charAt(i),   41k cbuff[i],   46k new[i],   80k field access.   (chars/ms) 
len =      4:    571k charAt(i),  250k cbuff[i],   97k new[i],  222k field access.   (chars/ms) 
len =      6:    666k charAt(i),  333k cbuff[i],  125k new[i],  315k field access.   (chars/ms) 
len =      8:    800k charAt(i),  400k cbuff[i],  181k new[i],  380k field access.   (chars/ms) 
len =     12:    800k charAt(i),  521k cbuff[i],  260k new[i],  545k field access.   (chars/ms) 
len =     16:    800k charAt(i),  592k cbuff[i],  296k new[i],  640k field access.   (chars/ms) 
len =     20:    800k charAt(i),  666k cbuff[i],  408k new[i],  800k field access.   (chars/ms) 
len =     24:    800k charAt(i),  705k cbuff[i],  452k new[i],  800k field access.   (chars/ms) 
len =     28:    777k charAt(i),  736k cbuff[i],  368k new[i],  933k field access.   (chars/ms) 
len =     32:    800k charAt(i),  780k cbuff[i],  571k new[i],  969k field access.   (chars/ms) 
len =     64:    800k charAt(i),  901k cbuff[i],  800k new[i],  1306k field access.   (chars/ms) 
len =    128:    1084k charAt(i),  888k cbuff[i],  633k new[i],  1620k field access.   (chars/ms) 
len =    256:    1122k charAt(i),  966k cbuff[i],  729k new[i],  1790k field access.   (chars/ms) 
len =    512:    1163k charAt(i),  1007k cbuff[i],  676k new[i],  1910k field access.   (chars/ms) 
len =   1024:    1179k charAt(i),  1027k cbuff[i],  698k new[i],  1954k field access.   (chars/ms) 
len =   2048:    1184k charAt(i),  1043k cbuff[i],  732k new[i],  2007k field access.   (chars/ms) 
len =   4096:    1188k charAt(i),  1049k cbuff[i],  742k new[i],  2031k field access.   (chars/ms) 
len =   8192:    1157k charAt(i),  1032k cbuff[i],  723k new[i],  2048k field access.   (chars/ms) 

WNIOSEK:

Jak widać, tryb serwera jest znacznie szybszy.

ceklock
źródło
2
Dzięki za wysłanie wiadomości. Zatem w przypadku dużych łańcuchów dostęp do pola jest nadal 2x szybszy niż funkcja charAt (). W rzeczywistości dostęp do pola stał się ogólnie jeszcze szybszy, prowadząc po 28 ciągach długości (szaleństwo!) Więc ... tryb serwera sprawia, że ​​wszystko jest szybsze. Bardzo interesujące!
Koordynator
1
Tak, metoda refleksyjna jest naprawdę szybsza. Ciekawy.
ceklock
2
btw: nowsze maszyny JVM automatycznie określają, który z -server lub -client działa najlepiej (zwykle): docs.oracle.com/javase/7/docs/technotes/guides/vm/ ...
jontejj
2
@jontejj w praktyce nie jest takie proste. Jeśli używasz 32-bitowej maszyny JVM w systemie Windows, maszyna JVM zawsze będzie domyślnie działać jako klient.
ceklock
7

Pierwsze użycie str.charAtpowinno być szybsze.

Jeśli zagłębisz się w kod źródłowy Stringklasy, zobaczymy, że charAtjest zaimplementowany w następujący sposób:

public char charAt(int index) {
    if ((index < 0) || (index >= count)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index + offset];
}

Tutaj wszystko, co robi, to indeksowanie tablicy i zwracanie wartości.

Teraz, jeśli zobaczymy implementację toCharArray, znajdziemy poniżej:

public char[] toCharArray() {
    char result[] = new char[count];
    getChars(0, count, result, 0);
    return result;
}

public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
    if (srcBegin < 0) {
        throw new StringIndexOutOfBoundsException(srcBegin);
    }
    if (srcEnd > count) {
        throw new StringIndexOutOfBoundsException(srcEnd);
    }
    if (srcBegin > srcEnd) {
        throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
    }
    System.arraycopy(value, offset + srcBegin, dst, dstBegin,
         srcEnd - srcBegin);
}

Jak widzisz, robi to, System.arraycopyco z pewnością będzie odrobinę wolniejsze niż nie robienie tego.

adarshr
źródło
2
To głupie, że String # charAt powinien wykonać dodatkowe sprawdzenie indeksu, gdy indeks jest sprawdzany mimo to przy dostępie do tablicy.
Ingo
1
Ryzyko ożywienia 8-letniego wątku ... Tablica znaków za łańcuchem może być większa niż sam ciąg. Oznacza to, że jeśli miałeś łańcuch „abcde”, a następnie użyłeś podłańcucha do wyodrębnienia „bcd” do nowego ciągu, nowy ciąg będzie wspierany przez dokładnie taką samą tablicę znaków jak pierwszy łańcuch. Dlatego klasa string zachowuje przesunięcie i liczbę - dzięki czemu wie, które znaki w tablicy są tymi, które reprezentują ten ciąg. Zatem sprawdzenie zakresu jest ważne, w przeciwnym razie możliwy byłby dostęp do znaków spoza tego ciągu.
dty
3

Pomimo odpowiedzi @Saint Hill, jeśli weźmiesz pod uwagę złożoność czasową str.toCharArray () ,

pierwsza jest szybsza nawet dla bardzo dużych strun. Możesz uruchomić poniższy kod, aby zobaczyć to na własne oczy.

        char [] ch = new char[1_000_000_00];
    String str = new String(ch); // to create a large string

    // ---> from here
    long currentTime = System.nanoTime();
    for (int i = 0, n = str.length(); i < n; i++) {
        char c = str.charAt(i);
    }
    // ---> to here
    System.out.println("str.charAt(i):"+(System.nanoTime()-currentTime)/1000000.0 +" (ms)");

    /**
     *   ch = str.toCharArray() itself takes lots of time   
     */
    // ---> from here
    currentTime = System.nanoTime();
    ch = str.toCharArray();
    for (int i = 0, n = str.length(); i < n; i++) {
        char c = ch[i];
    }
    // ---> to  here
    System.out.println("ch = str.toCharArray() + c = ch[i] :"+(System.nanoTime()-currentTime)/1000000.0 +" (ms)");

wynik:

str.charAt(i):5.492102 (ms)
ch = str.toCharArray() + c = ch[i] :79.400064 (ms)
Grafika C.
źródło
2

Wygląda na to, że niether jest szybszy lub wolniejszy

    public static void main(String arguments[]) {


        //Build a long string
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < 10000; j++) {
            sb.append("a really, really long string");
        }
        String str = sb.toString();
        for (int testscount = 0; testscount < 10; testscount ++) {


            //Test 1
            long start = System.currentTimeMillis();
            for(int c = 0; c < 10000000; c++) {
                for (int i = 0, n = str.length(); i < n; i++) {
                    char chr = str.charAt(i);
                    doSomethingWithChar(chr);//To trick JIT optimistaion
                }
            }

            System.out.println("1: " + (System.currentTimeMillis() - start));

            //Test 2
            start = System.currentTimeMillis();
            char[] chars = str.toCharArray();
            for(int c = 0; c < 10000000; c++) {
                for (int i = 0, n = chars.length; i < n; i++) {
                    char chr = chars[i];
                    doSomethingWithChar(chr);//To trick JIT optimistaion
                }
            }
            System.out.println("2: " + (System.currentTimeMillis() - start));
            System.out.println();
        }


    }


    public static void doSomethingWithChar(char chr) {
        int newInt = chr << 2;
    }

Na długie struny wybiorę pierwszy. Po co kopiować długie struny? Dokumentacja mówi:

public char [] toCharArray () Konwertuje ten ciąg na nową tablicę znaków.

Zwraca: nowo przydzieloną tablicę znaków, której długość jest długością tego ciągu i której zawartość jest inicjowana tak, aby zawierała sekwencję znaków reprezentowaną przez ten ciąg.

// Edycja 1

Zmieniłem test, aby oszukać optymalizację JIT.

// Edycja 2

Powtórz test 10 razy, aby JVM się rozgrzał.

// Edycja 3

Wnioski:

Przede wszystkim str.toCharArray();kopiuje cały ciąg do pamięci. Długie ciągi mogą zajmować dużo pamięci. Metoda String.charAt( )wyszukuje znaki w tablicy znaków wewnątrz klasy String sprawdzającej indeks wcześniej. Wygląda na to, że dla wystarczająco krótkich łańcuchów pierwsza metoda (tj. chatAtMetoda) jest nieco wolniejsza z powodu tego sprawdzenia indeksu. Ale jeśli String jest wystarczająco długi, kopiowanie całej tablicy znaków jest wolniejsze, a pierwsza metoda jest szybsza. Im dłuższa jest struna, tym wolniej toCharArraydziała. Spróbuj zmienić limit w for(int j = 0; j < 10000; j++)pętli, aby to zobaczyć. Jeśli pozwolimy, aby JVM rozgrzał się, kod działa szybciej, ale proporcje są takie same.

W końcu to tylko mikro-optymalizacja.

Piotr Gwiazda
źródło
Czy mógłbyś wypróbować tę for:inopcję, dla samej przyjemności?
dasblinkenlight
2
Twój benchmark jest wadliwy: nie pozwala JIT na dokonywanie optymalizacji; JIT mógłby całkowicie usunąć pętle, ponieważ nic nie robią.
JB Nizet
Ciąg nie jest na Iterableani tablicą.
Piotr Gwiazda
2
To nie jest ważny test, „rozgrzałeś” swoją maszynę JVM za pomocą testu 1, co może wypaczyć wyniki na korzyść testu 2. Całe pytanie OP i tak pachnie mikrooptymalizacją.
Percepcja
1
Prawdziwe. Po rozgrzaniu (patrz Edycja 2) oba czasy są mniejsze, ale wciąż blisko siebie. W moim przykładzie drugi test jest nieco szybszy. Ale jeśli wydłużę strunę, pierwsza będzie szybsza. Im dłuższy ciąg, tym wolniejszy drugi test z powodu kopiowania tablicy znaków. Po prostu zrób to w pierwszy sposób.
Piotr Gwiazda
2

String.toCharArray()tworzy nową tablicę znaków, oznacza alokację pamięci o długości łańcucha, następnie kopiuje oryginalną tablicę znaków za pomocą, System.arraycopy()a następnie zwraca tę kopię do wywołującego. String.charAt () zwraca znak na pozycji iz oryginalnej kopii, dlatego String.charAt()będzie szybszy niż String.toCharArray(). Chociaż String.toCharArray()zwraca copy, a nie znak z oryginalnej tablicy String, gdzie String.charAt()zwraca znak z oryginalnej tablicy znaków. Poniższy kod zwraca wartość o określonym indeksie tego ciągu.

public char charAt(int index) {
    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

Poniższy kod zwraca nowo przydzieloną tablicę znaków, której długość jest długością tego ciągu

public char[] toCharArray() {
    // Cannot use Arrays.copyOf because of class initialization order issues
    char result[] = new char[value.length];
    System.arraycopy(value, 0, result, 0, value.length);
    return result;
}
viki s
źródło
1

Drugi powoduje utworzenie nowej tablicy znaków i skopiowanie wszystkich znaków ze String do nowej tablicy znaków, więc domyślam się, że pierwsza jest szybsza (i mniej wymagająca pamięci).

JB Nizet
źródło