Der schnellste Weg, um alle Zeichen in einem String zu durchlaufen

163

Was wäre in Java der schnellste Weg, um alle Zeichen in einem String zu durchlaufen:

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

Oder dieses:

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

EDIT:

Ich möchte wissen, ob die Kosten für das wiederholte Aufrufen der charAtMethode während einer langen Iteration geringer oder höher sind als die Kosten für das Ausführen eines einzelnen Aufrufs zu toCharArrayBeginn und den direkten Zugriff auf das Array während der Iteration.

Es wäre großartig, wenn jemand einen robusten Benchmark für verschiedene Saitenlängen liefern könnte, unter Berücksichtigung der JIT-Aufwärmzeit, der JVM-Startzeit usw. und nicht nur des Unterschieds zwischen zwei Aufrufen von System.currentTimeMillis().

Óscar López
quelle
17
Was ist mit passiert for (char c : chars)?
Dasblinkenlight
Der erste sollte schneller sein und theoretisch ein String ein char-Array.
Keagan Ladds
Google ist oft eine gute Ressource: mkyong.com/java/…
Johan Sjöberg
2
Die Frage fragt nicht nach der Leistung der Verwendung von Iteratoren, foreach. Was ich gerne wissen würde, ist, ob die Kosten für wiederholte Anrufe charAtentweder kleiner oder höher sind als die Kosten für einen einzelnen Anruf beitoCharArray
Óscar López
1
Hat jemand eine Analyse mit StringCharacterIterator durchgeführt ?
Bdrx

Antworten:

351

ERSTES UPDATE: Bevor Sie dies in einer Produktionsumgebung versuchen (nicht empfohlen), lesen Sie zuerst Folgendes : http://www.javaspecialists.eu/archive/Issue237.html Ab Java 9 funktioniert die beschriebene Lösung nicht mehr , da Java jetzt Zeichenfolgen standardmäßig als Byte [] speichert.

ZWEITES UPDATE: Ab dem 25.10.2016 gibt es auf meinem AMDx64 8core und Source 1.8 keinen Unterschied zwischen der Verwendung von 'charAt' und dem Feldzugriff. Es scheint, dass das JVM ausreichend optimiert ist, um alle Aufrufe von 'string.charAt (n)' zu inline und zu rationalisieren.

Es hängt alles von der Länge der StringInspektion ab. Wenn es sich, wie die Frage sagt, um lange Zeichenfolgen handelt, besteht die schnellste Möglichkeit, die Zeichenfolge zu überprüfen, darin, mithilfe der Reflexion auf die Rückseite char[]der Zeichenfolge zuzugreifen .

Ein vollständig randomisierter Benchmark mit JDK 8 (win32 und win64) auf einem 64 AMD Phenom II 4 Core 955 mit 3,2 GHz (sowohl im Client- als auch im Servermodus) mit 9 verschiedenen Techniken (siehe unten!) Zeigt, dass die Verwendung String.charAt(n)für kleine Unternehmen am schnellsten ist Zeichenfolgen und die Verwendung reflectionfür den Zugriff auf das String-Backing-Array ist bei großen Zeichenfolgen fast doppelt so schnell.

DAS EXPERIMENT

  • Es werden 9 verschiedene Optimierungstechniken ausprobiert.

  • Alle Zeichenfolgeninhalte sind zufällig angeordnet

  • Der Test wird für Saitengrößen in Vielfachen von zwei durchgeführt, beginnend mit 0,1,2,4,8,16 usw.

  • Die Tests werden 1.000 Mal pro Zeichenfolgengröße durchgeführt

  • Die Tests werden jedes Mal in zufälliger Reihenfolge gemischt. Mit anderen Worten, die Tests werden jedes Mal in zufälliger Reihenfolge durchgeführt, mehr als 1000 Mal.

  • Die gesamte Testsuite wird vorwärts und rückwärts ausgeführt, um die Auswirkung der JVM-Aufwärmphase auf Optimierung und Zeiten zu zeigen.

  • Die gesamte Suite wird zweimal ausgeführt, einmal im -clientModus und einmal im -serverModus.

SCHLUSSFOLGERUNGEN

-Client-Modus (32 Bit)

Bei Zeichenfolgen mit einer Länge von 1 bis 256 Zeichenstring.charAt(i) gewinnt der Aufruf mit einer durchschnittlichen Verarbeitung von 13,4 bis 588 Millionen Zeichen pro Sekunde.

Außerdem ist es insgesamt 5,5% schneller (Client) und 13,9% (Server) wie folgt:

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

als so mit einer lokalen endgültigen Längenvariablen:

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

Bei langen Zeichenfolgen mit einer Länge von 512 bis 256 KB ist die Verwendung der Reflexion für den Zugriff auf das Hintergrundarray der Zeichenfolge am schnellsten. Diese Technik ist fast doppelt so schnell wie String.charAt (i) (178% schneller). Die durchschnittliche Geschwindigkeit in diesem Bereich betrug 1,111 Milliarden Zeichen pro Sekunde.

Das Feld muss im Voraus abgerufen werden und kann dann in der Bibliothek für verschiedene Zeichenfolgen wiederverwendet werden. Interessanterweise ist es im Gegensatz zum obigen Code beim Feldzugriff 9% schneller, eine lokale endgültige Längenvariable zu haben, als 'chars.length' bei der Schleifenprüfung zu verwenden. So kann der Feldzugriff am schnellsten eingerichtet werden:

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

Besondere Kommentare zum Server-Modus

Der Feldzugriff beginnt nach 32 Zeichenfolgen im Servermodus auf einem 64-Bit-Java-Computer auf meinem AMD 64-Computer zu gewinnen. Dies wurde erst mit einer Länge von 512 Zeichen im Client-Modus festgestellt.

Erwähnenswert ist auch, dass ich beim Ausführen von JDK 8 (32-Bit-Build) im Servermodus die Gesamtleistung sowohl für große als auch für kleine Zeichenfolgen um 7% langsamer war. Dies war mit Build 121 Dec 2013 von JDK 8 Early Release. Derzeit scheint der 32-Bit-Servermodus langsamer zu sein als der 32-Bit-Client-Modus.

Davon abgesehen ... scheint der einzige Servermodus, der es wert ist, aufgerufen zu werden, auf einem 64-Bit-Computer zu sein. Andernfalls wird die Leistung tatsächlich beeinträchtigt.

Für 32-Bit-Builds -server modeauf einem AMD64 kann ich Folgendes sagen:

  1. String.charAt (i) ist der klare Gesamtsieger. Obwohl zwischen den Größen 8 bis 512 Zeichen gab es Gewinner unter "Neu", "Wiederverwendung" und "Feld".
  2. String.charAt (i) ist im Client-Modus 45% schneller
  3. Der Feldzugriff ist für große Strings im Client-Modus doppelt so schnell.

Ebenfalls erwähnenswert ist, dass String.chars () (Stream und die parallele Version) eine Pleite sind. Viel langsamer als jeder andere Weg. Die StreamsAPI ist eine ziemlich langsame Methode, um allgemeine Zeichenfolgenoperationen auszuführen.

Wunschzettel

Java String kann Prädikate haben, die optimierte Methoden akzeptieren, wie z. B. enthält (Prädikat), forEach (Consumer), forEachWithIndex (Consumer). Ohne dass der Benutzer die Länge kennen oder Aufrufe von String-Methoden wiederholen muss, können diese das Parsen von Bibliotheken unterstützenbeep-beep beep beschleunigen.

Träum weiter :)

Happy Strings!

~ SH

Der Test verwendete die folgenden 9 Methoden zum Testen der Zeichenfolge auf das Vorhandensein von Leerzeichen:

"charAt1" - PRÜFEN SIE DEN STRING-INHALT AUF DIE GEWÖHNLICHE ART:

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" - GLEICH WIE OBEN, ABER VERWENDEN SIE String.length (), STATT EINE ENDGÜLTIGE LOKALE int FÜR DIE LÄNGE ZU MACHEN

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

"stream" - VERWENDEN Sie den IntStream des NEUEN JAVA-8-Strings und geben Sie ihm ein Prädikat für die Überprüfung

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

"streamPara" - GLEICH WIE OBEN, ABER OH-LA-LA - GO PARALLEL !!!

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

"wiederverwenden" - FÜLLEN SIE EIN WIEDERVERWENDBARES Zeichen [] MIT DEN INHALTEN DER STRINGS NACH

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" - ERHALTEN SIE EINE NEUE KOPIE DES char [] AUS DER 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;
}

"new2" - GLEICH WIE OBEN, ABER "FÜR JEDEN"

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

"field1" - FANTASTISCH !! ERHALTEN SIE EIN FELD FÜR DEN ZUGRIFF AUF DAS INTERNE Zeichen der STRING []

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" - GLEICH WIE OBEN, ABER "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;
}

VERBUNDENE ERGEBNISSE FÜR DEN KUNDENMODUS -client(Vorwärts- und Rückwärts-Tests kombiniert)

Hinweis: Der -client-Modus mit Java 32-Bit und der -server-Modus mit Java 64-Bit sind auf meinem AMD64-Computer dieselben wie unten.

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

ZUSAMMENGESETZTE ERGEBNISSE FÜR DEN SERVERMODUS -server(Vorwärts- und Rückwärts-Tests kombiniert)

Hinweis: Dies ist der Test für Java 32 Bit, das im Servermodus auf einem AMD64 ausgeführt wird. Der Servermodus für Java 64-Bit war der gleiche wie für Java 32-Bit im Client-Modus, außer dass der Feldzugriff nach 32 Zeichen beginnt.

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

VOLLSTÄNDIGER LAUFBARER PROGRAMMCODE

(Um auf Java 7 und früher zu testen, entfernen Sie die beiden Streams-Tests.)

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("");
    }
}
Der Koordinator
quelle
1
Wurde dieser Test in Server-JVM oder Client-JVM ausgeführt? Die besten Optimierungen werden nur in Server-JVM durchgeführt. Wenn Sie mit der Standard-32-Bit-JVM und ohne Argumente ausgeführt haben, wurden Sie im Client-Modus ausgeführt.
ceklock
2
Das Abrufen des Sicherungspuffers ist problematisch bei Teilzeichenfolgen oder Zeichenfolgen, die mit String (char [], int, int) erstellt wurden, da Sie den gesamten Puffer erhalten (zumindest unter Android), Ihre Indizierung jedoch auf Null basiert. Wenn Sie jedoch wissen, dass Sie keinen Teilstring haben, funktioniert dies einwandfrei.
Prewett
5
Gibt es eine Idee, warum "for (int i = 0; i <data.length (); i ++)" schneller ist als die Definition von data.length () als endgültige lokale Variable?
Skyin
2
Das Definieren einer Variablen erfordert überhaupt eine Stapeloperation im Methodenbytecode. Die Optimierungen, die sich aus der Erkennung Ihres Algorithmus ergeben, können diese Wiederholungsoperation im tatsächlichen Maschinencode jedoch schnell nachverfolgen, ohne den Aufwand für die Zuordnung von Variablen. Solche Optimierungen existieren manchmal in den Bytecode-Compilern, manchmal nicht. Es hängt alles davon ab, ob der JVM klug genug ist :-)
Der Koordinator
2
@DavidS Die Zahlen sind die Rate (in Nanosekunden) pro geprüftem Zeichen. Kleiner ist besser.
Der Koordinator
14

Dies ist nur eine Mikrooptimierung, über die Sie sich keine Sorgen machen sollten.

char[] chars = str.toCharArray();

Gibt Ihnen eine Kopie der strZeichenarrays zurück (in JDK wird durch Aufrufen eine Kopie der Zeichen zurückgegebenSystem.arrayCopy ).

Davon abgesehen, str.charAt() nur geprüft, ob der Index tatsächlich begrenzt ist, und es wird ein Zeichen innerhalb des Array-Index zurückgegeben.

Der erste erstellt keinen zusätzlichen Speicher in JVM.

Buhake Sindi
quelle
Beantwortet die Frage nicht. Bei dieser Frage geht es um Leistung. Nach allem, was Sie wissen, hat das OP möglicherweise festgestellt, dass das Iterieren über Zeichenfolgen einen erheblichen Kostenfaktor für die Anwendung darstellt.
rghome
9

Nur aus Neugier und zum Vergleich mit Saint Hills Antwort.

Wenn Sie schwere Daten verarbeiten müssen, sollten Sie JVM nicht im Client-Modus verwenden. Der Client-Modus ist nicht für Optimierungen vorgesehen.

Vergleichen wir die Ergebnisse von @ Saint Hill-Benchmarks mit einer JVM im Client- und Servermodus.

Core2Quad Q6600 G0 @ 2.4GHz
JavaSE 1.7.0_40

Siehe auch: Echte Unterschiede zwischen "Java-Server" und "Java-Client"?


KUNDENMODUS:

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) 

SERVER-MODUS:

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) 

FAZIT:

Wie Sie sehen können, ist der Servermodus viel schneller.

ceklock
quelle
2
Danke fürs Schreiben. Bei großen Zeichenfolgen ist der Feldzugriff also immer noch zweimal schneller als bei charAt (). Tatsächlich wurde der Feldzugriff insgesamt sogar noch schneller, da er nach 28 langen Zeichenfolgen führte (verrückt !!). Also ... der Servermodus macht alles schneller. Sehr interessant!
Der Koordinator
1
Ja, die Reflexionsmethode ist wirklich schneller. Interessant.
ceklock
2
Übrigens: Neuere JVMs ermitteln automatisch, welcher von -server oder -client (normalerweise) am besten funktioniert: docs.oracle.com/javase/7/docs/technotes/guides/vm/…
jontejj
2
@jontejj in der Praxis ist es nicht so einfach. Wenn Sie eine 32-Bit-JVM unter Windows ausführen, wird die JVM immer standardmäßig als Client verwendet.
ceklock
7

Die erste Verwendung str.charAtsollte schneller sein.

Wenn Sie in den Quellcode der StringKlasse graben , können wir sehen, dass dies charAtwie folgt implementiert ist:

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

Hier wird lediglich ein Array indiziert und der Wert zurückgegeben.

Wenn wir nun die Implementierung von sehen toCharArray, finden wir Folgendes:

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

Wie Sie sehen, macht es ein, System.arraycopywas definitiv ein bisschen langsamer sein wird, als es nicht zu tun.

adarshr
quelle
2
Es ist albern, dass der String # charAt eine zusätzliche Indexprüfung durchführt, wenn der Index beim Array-Zugriff trotzdem überprüft wird.
Ingo
1
Es besteht die Gefahr, dass ein 8 Jahre alter Thread wiederbelebt wird ... Das char-Array hinter einer Zeichenfolge ist möglicherweise größer als die Zeichenfolge selbst. Das heißt, wenn Sie eine Zeichenfolge "abcde" hatten und dann Teilzeichenfolge verwendet haben, um "bcd" in eine neue Zeichenfolge zu extrahieren, wird die neue Zeichenfolge durch genau dasselbe Zeichenarray wie die erste Zeichenfolge unterstützt. Aus diesem Grund behält die Zeichenfolgenklasse einen Offset und eine Anzahl bei, sodass sie weiß, welche Zeichen im Array diese Zeichenfolge darstellen. Daher ist die Bereichsprüfung wichtig, da sonst auf Zeichen über die Enden dieser Zeichenfolge hinaus zugegriffen werden kann.
21.
3

Trotz der Antwort von @Saint Hill, wenn Sie die zeitliche Komplexität von str.toCharArray () berücksichtigen ,

Der erste ist sogar für sehr große Saiten schneller. Sie können den folgenden Code ausführen, um sich selbst davon zu überzeugen.

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

Ausgabe:

str.charAt(i):5.492102 (ms)
ch = str.toCharArray() + c = ch[i] :79.400064 (ms)
C-Grafiken
quelle
2

Sieht so aus, als wäre nichts schneller oder langsamer

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

Für lange Saiten werde ich die erste wählen. Warum um lange Saiten kopieren? Dokumentationen sagt:

public char [] toCharArray () Konvertiert diese Zeichenfolge in ein neues Zeichenarray.

Rückgabe: Ein neu zugewiesenes Zeichenarray, dessen Länge der Länge dieser Zeichenfolge entspricht und dessen Inhalt so initialisiert wird, dass er die durch diese Zeichenfolge dargestellte Zeichenfolge enthält.

// Bearbeiten 1

Ich habe den Test geändert, um die JIT-Optimierung auszutricksen.

// Bearbeiten 2

Wiederholen Sie den Test 10 Mal, damit sich JVM aufwärmen kann.

// Bearbeiten 3

Schlussfolgerungen:

Zunächst einmal str.toCharArray();gesamte Zeichenfolge im Speicher kopiert. Es kann für lange Zeichenfolgen speicherintensiv sein. Die Methode String.charAt( )sucht zuvor nach char im char-Array im String-Klassenprüfungsindex. Es sieht so aus, als ob die erste Strings-Methode (dh die chatAtMethode) aufgrund dieser Indexprüfung etwas langsamer ist. Wenn der String jedoch lang genug ist, wird das Kopieren des gesamten char-Arrays langsamer und die erste Methode ist schneller. Je länger die Zeichenfolge ist, desto langsamer wird toCharArraydie Leistung. Versuchen Sie, das Limit in der for(int j = 0; j < 10000; j++)Schleife zu ändern, um es zu sehen. Wenn wir JVM aufwärmen lassen, läuft der Code schneller, aber die Proportionen sind gleich.

Immerhin ist es nur Mikrooptimierung.

Piotr Gwiazda
quelle
Könnten Sie die for:inOption ausprobieren , nur zum Spaß?
Dasblinkenlight
2
Ihr Benchmark ist fehlerhaft: Er lässt die JIT nicht optimieren. Die JIT könnte die Schleifen vollständig entfernen, da sie nichts tun.
JB Nizet
String ist weder na Iterablenoch Array.
Piotr Gwiazda
2
Dies ist kein gültiger Test. Sie haben Ihre JVM mit Test 1 "aufgewärmt", wodurch die Ergebnisse zu Gunsten von Test 2 verschoben werden können. Die ganze Frage des OP riecht sowieso nach Mikrooptimierung.
Wahrnehmung
1
Wahr. Nach dem Aufwärmen (siehe Bearbeiten 2) sind beide Male kleiner, aber immer noch nahe beieinander. In meinem Beispiel ist der zweite Test etwas schneller. Aber wenn ich den String länger mache, ist der erste schneller. Je länger die Zeichenfolge, desto langsamer der zweite Test aufgrund der Kopie des Char-Arrays. Mach es einfach auf die erste Weise.
Piotr Gwiazda
2

String.toCharArray()Erstellt ein neues Zeichenarray, bedeutet die Zuweisung von Speicher mit Zeichenfolgenlänge, kopiert dann das ursprüngliche Zeichenarray der Zeichenfolge mit System.arraycopy()und gibt diese Kopie an den Aufrufer zurück. String.charAt () gibt das Zeichen an der Position ider Originalkopie zurück. Deshalb String.charAt()ist es schneller als String.toCharArray(). Obwohl, String.toCharArray()kehrt kopieren und nicht char aus Original - String - Array, wo String.charAt()kehrt Zeichen von den ursprünglichen char - Array. Der folgende Code gibt den Wert am angegebenen Index dieser Zeichenfolge zurück.

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

Der folgende Code gibt ein neu zugewiesenes Zeichenarray zurück, dessen Länge der Länge dieser Zeichenfolge entspricht

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
quelle
1

Das zweite bewirkt, dass ein neues Zeichenarray erstellt und alle Zeichen aus dem String in dieses neue Zeichenarray kopiert werden. Ich würde also vermuten, dass das erste schneller (und weniger speicherhungrig) ist.

JB Nizet
quelle