La forma más rápida de iterar sobre todos los caracteres en una Cadena

163

En Java, ¿cuál sería la forma más rápida de iterar sobre todos los caracteres en una Cadena, esto:

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

O esto:

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

EDITAR:

Lo que me gustaría saber es si el costo de llamar repetidamente al charAtmétodo durante una iteración larga termina siendo menor o mayor que el costo de realizar una sola llamada al toCharArrayprincipio y luego acceder directamente a la matriz durante la iteración.

Sería genial si alguien pudiera proporcionar un punto de referencia sólido para diferentes longitudes de cadena, teniendo en cuenta el tiempo de calentamiento de JIT, el tiempo de inicio de JVM, etc. y no solo la diferencia entre dos llamadas a System.currentTimeMillis().

Óscar López
fuente
18
¿Qué pasó con for (char c : chars)?
dasblinkenlight
El primero debería ser más rápido, y de todos modos una cadena de un conjunto de caracteres, en teoría.
Keagan Ladds
Google suele ser un buen recurso: mkyong.com/java/…
Johan Sjöberg
2
La pregunta no pide el rendimiento del uso de iteradores, foreach. Lo que me gustaría saber es si el costo de llamar repetidamente charAttermina siendo menor o mayor que el costo de realizar una sola llamada atoCharArray
Óscar López
1
¿Alguien ha hecho análisis con StringCharacterIterator ?
bdrx

Respuestas:

352

PRIMERA ACTUALIZACIÓN: antes de intentar esto en un entorno de producción (no recomendado), lea esto primero: http://www.javaspecialists.eu/archive/Issue237.html A partir de Java 9, la solución descrita ya no funcionará , porque ahora Java almacenará cadenas como byte [] de forma predeterminada.

SEGUNDA ACTUALIZACIÓN: A partir del 25/10/2016, en mi AMDx64 8core y fuente 1.8, no hay diferencia entre usar 'charAt' y acceso de campo. Parece que jvm está lo suficientemente optimizado para en línea y racionalizar cualquier llamada 'string.charAt (n)'.

Todo depende de la duración de la Stringinspección. Si, como dice la pregunta, es para cadenas largas , la forma más rápida de inspeccionar la cadena es usar la reflexión para acceder al respaldo char[]de la cadena.

Un punto de referencia completamente aleatorio con JDK 8 (win32 y win64) en un 64 AMD Phenom II 4 core 955 @ 3.2 GHZ (tanto en modo cliente como en modo servidor) con 9 técnicas diferentes (¡ver más abajo!) Muestra que usar String.charAt(n)es el más rápido para pequeños cadenas y que usar reflectionpara acceder a la matriz de respaldo de cadenas es casi el doble de rápido para cadenas grandes.

EL EXPERIMENTO

  • Se prueban 9 técnicas diferentes de optimización.

  • Todos los contenidos de la cadena son aleatorios

  • La prueba se realiza para tamaños de cuerda en múltiplos de dos, comenzando con 0,1,2,4,8,16, etc.

  • Las pruebas se realizan 1,000 veces por tamaño de cadena

  • Las pruebas se barajan en orden aleatorio cada vez. En otras palabras, las pruebas se realizan en orden aleatorio cada vez que se realizan, más de 1000 veces.

  • Todo el conjunto de pruebas se realiza hacia adelante y hacia atrás para mostrar el efecto del calentamiento de JVM en la optimización y los tiempos.

  • Toda la suite se realiza dos veces, una en -clientmodo y la otra en -servermodo.

CONCLUSIONES

-modo de cliente (32 bits)

Para cadenas de 1 a 256 caracteres de longitud , las llamadas string.charAt(i)ganan con un procesamiento promedio de 13.4 millones a 588 millones de caracteres por segundo.

Además, en general es 5.5% más rápido (cliente) y 13.9% (servidor) así:

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

que así con una variable de longitud final local:

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

Para cadenas largas, de 512 a 256K caracteres de longitud , usar la reflexión para acceder a la matriz de respaldo de la cadena es más rápido. Esta técnica es casi el doble de rápida que String.charAt (i) (178% más rápido). La velocidad promedio en este rango fue de 1.111 mil millones de caracteres por segundo.

El campo debe obtenerse con anticipación y luego puede reutilizarse en la biblioteca en diferentes cadenas. Curiosamente, a diferencia del código anterior, con acceso de campo, es un 9% más rápido tener una variable de longitud final local que usar 'chars.length' en la verificación de bucle. Así es como el acceso de campo se puede configurar como más rápido:

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

Comentarios especiales sobre el modo servidor

El acceso de campo comienza a ganar después de cadenas de 32 caracteres en modo servidor en una máquina Java de 64 bits en mi máquina AMD 64. Eso no se vio hasta 512 caracteres de longitud en modo cliente.

También vale la pena señalar que creo que cuando estaba ejecutando JDK 8 (compilación de 32 bits) en modo servidor, el rendimiento general fue un 7% más lento para cadenas grandes y pequeñas. Esto fue con la versión 121 de diciembre de 2013 de la versión temprana de JDK 8. Entonces, por ahora, parece que el modo de servidor de 32 bits es más lento que el modo de cliente de 32 bits.

Dicho esto ... parece que el único modo de servidor que vale la pena invocar es en una máquina de 64 bits. De lo contrario, en realidad obstaculiza el rendimiento.

Para la compilación de 32 bits que se ejecuta en -server modeun AMD64, puedo decir esto:

  1. String.charAt (i) es el claro ganador en general. Aunque entre los tamaños de 8 a 512 caracteres hubo ganadores entre 'nuevo' 'reutilización' y 'campo'.
  2. String.charAt (i) es un 45% más rápido en modo cliente
  3. El acceso de campo es dos veces más rápido para cadenas grandes en modo cliente.

También vale la pena decir que String.chars () (Stream y la versión paralela) son un fracaso. Mucho más lento que cualquier otro. La StreamsAPI es una forma bastante lenta de realizar operaciones generales de cadena.

Lista de deseos

Java String podría tener un predicado que acepte métodos optimizados tales como contiene (predicado), forEach (consumer), forEachWithIndex (consumer). Por lo tanto, sin la necesidad de que el usuario conozca la duración o repita las llamadas a los métodos String, estos podrían ayudar a analizar las bibliotecas beep-beep beepacelerando.

Sigue soñando :)

Happy Strings!

~ SH

La prueba utilizó los siguientes 9 métodos para probar la cadena en busca de espacios en blanco:

"charAt1" - COMPRUEBE EL CONTENIDO DE LA CADENA DE LA MANERA habitual:

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" - LO MISMO QUE ARRIBA PERO UTILICE String.length () EN LUGAR DE HACER UNA INT. LOCAL FINAL POR LA LONGITUD

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

"stream" - USE EL NUEVO IntStream de String JAVA-8 Y PÁGELO PREDICADO PARA HACER LA COMPROBACIÓN

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

"streamPara" - LO MISMO QUE ARRIBA, PERO OH-LA-LA - ¡¡VAYA PARALELO !!!

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

"reutilizar" - RELLENE UN CARGADOR REUTILIZABLE [] CON EL CONTENIDO DE LAS CUERDAS

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" - OBTENGA UNA NUEVA COPIA DEL CHAR [] DESDE LA CADENA

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" - IGUAL QUE ARRIBA, PERO USE "PARA CADA"

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

"campo1" - FANCY !! OBTENGA CAMPO PARA ACCEDER AL CHAR INTERNO DE LA CADENA []

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" - MISMO QUE ARRIBA, PERO USE "PARA CADA"

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

RESULTADOS COMPUESTOS PARA -clientMODO CLIENTE (pruebas de avance y retroceso combinadas)

Nota: que el modo de cliente con Java de 32 bits y el modo de servidor con Java de 64 bits son los mismos que a continuación en mi máquina 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

RESULTADOS COMPUESTOS PARA EL -serverMODO DE SERVIDOR (pruebas de avance y retroceso combinadas)

Nota: esta es la prueba para Java 32 bits que se ejecuta en modo servidor en un AMD64. El modo de servidor para Java de 64 bits era el mismo que el de Java de 32 bits en modo cliente, excepto que el acceso de campo comenzó a ganar después del tamaño de 32 caracteres.

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

CÓDIGO DE PROGRAMA EJECUTABLE COMPLETO

(para probar en Java 7 y versiones anteriores, elimine las dos pruebas de secuencias)

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("");
    }
}
El coordinador
fuente
1
¿Se ejecutó esta prueba en el servidor JVM o el cliente JVM? Las mejores optimizaciones solo se realizan en el servidor JVM. Si ejecutó utilizando la JVM predeterminada de 32 bits y sin argumentos, ejecutó en modo cliente.
ceklock
2
Obtener el buffer de respaldo es problemático en el caso de las subcadenas, o cadenas creadas usando String (char [], int, int), ya que obtienes el buffer completo (al menos en Android), pero tu indexación estará basada en cero. Sin embargo, si sabe que no tiene una subcadena, funcionará bien.
prewett
55
¿Alguna idea de por qué "for (int i = 0; i <data.length (); i ++)" es más rápido que definir data.length () como una variable local final?
skyin
2
Definir una variable, en absoluto, requiere una operación de pila en el código de bytes del método. Pero las optimizaciones, desde el reconocimiento de su algoritmo, podrían acelerar la operación repetida en el código de máquina real, sin la sobrecarga de la ubicación variable. Tales optimizaciones a veces existen en los compiladores de bytecode, a veces no. Todo depende de si el jvm es lo suficientemente inteligente :-)
El Coordinador el
2
@DavidS los números son la tasa (en nanosegundos) por carácter inspeccionado. Más pequeño es mejor.
El coordinador
14

Esto no es más que una microoptimización de la que no debe preocuparse.

char[] chars = str.toCharArray();

le devuelve una copia de strmatrices de caracteres (en JDK, devuelve una copia de caracteres llamando System.arrayCopy).

Aparte de eso, str.charAt()solo verifica si el índice está realmente dentro de los límites y devuelve un carácter dentro del índice de la matriz.

El primero no crea memoria adicional en JVM.

Buhake Sindi
fuente
No responde la pregunta. Esta pregunta es sobre el rendimiento. Por lo que sabes, el OP puede haber descubierto que iterar sobre cadenas es un costo importante en su aplicación.
rghome
9

Solo por curiosidad y para comparar con la respuesta de Saint Hill.

Si necesita procesar datos pesados, no debe usar JVM en modo cliente. El modo cliente no está hecho para optimizaciones.

Comparemos los resultados de los puntos de referencia de @Saint Hill utilizando una JVM en modo Cliente y modo Servidor.

Core2Quad Q6600 G0 @ 2.4GHz
JavaSE 1.7.0_40

Ver también: ¿ Diferencias reales entre "java -server" y "java -client"?


MODO CLIENTE:

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) 

MODO DE SERVIDOR:

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) 

CONCLUSIÓN:

Como puede ver, el modo servidor es mucho más rápido.

ceklock
fuente
2
Gracias por publicar. Entonces, para cadenas grandes, el acceso de campo sigue siendo 2 veces más rápido que charAt (). De hecho, el acceso de campo se volvió aún más rápido en general, ya que lideró después de 28 cadenas de longitud (¡loco!) Entonces ... el modo de servidor hace que todo sea más rápido. ¡Muy interesante!
El coordinador el
1
Sí, el método reflexivo es realmente más rápido. Interesante.
ceklock
2
por cierto: las JVM más nuevas descubren automáticamente cuál de los servidores o clientes funciona mejor (generalmente): docs.oracle.com/javase/7/docs/technotes/guides/vm/…
jontejj
2
@jontejj en la práctica no es tan simple. Si está ejecutando una JVM de 32 bits en Windows, la JVM siempre será predeterminada para el cliente.
ceklock
7

El primero que use str.charAtdebería ser más rápido.

Si cava dentro del código fuente de la Stringclase, podemos ver que charAtse implementa de la siguiente manera:

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

Aquí, todo lo que hace es indexar una matriz y devolver el valor.

Ahora, si vemos la implementación de toCharArray, encontraremos lo siguiente:

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

Como puede ver, está haciendo algo System.arraycopyque definitivamente va a ser un poco más lento que no hacerlo.

adarshr
fuente
2
Es una tontería que el String # charAt haga una comprobación adicional del índice, cuando el índice se verifica de todos modos en el acceso a la matriz.
Ingo
1
A riesgo de revivir un hilo de 8 años ... La matriz de caracteres detrás de una cadena podría ser más grande que la cadena misma. Es decir, si tenía una cadena "abcde" y luego usó la subcadena para extraer "bcd" en una nueva cadena, la nueva cadena estará respaldada por exactamente la misma matriz de caracteres que la primera cadena. Es por eso que la clase de cadena mantiene un desplazamiento y un recuento, por lo que sabe qué caracteres en la matriz son los que representan esta cadena. Por lo tanto, la verificación del rango es importante; de ​​lo contrario, sería posible acceder a los caracteres más allá de los extremos de esta cadena.
dty
3

A pesar de la respuesta de @Saint Hill si considera la complejidad temporal de str.toCharArray () ,

el primero es más rápido incluso para cadenas muy grandes. Puede ejecutar el siguiente código para verlo usted mismo.

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

salida:

str.charAt(i):5.492102 (ms)
ch = str.toCharArray() + c = ch[i] :79.400064 (ms)
Gráficos en C
fuente
2

Parece que niether es más rápido o más lento

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

Para cadenas largas, elegiré el primero. ¿Por qué copiar cadenas largas? La documentación dice:

public char [] toCharArray () Convierte esta cadena en una nueva matriz de caracteres.

Devuelve: una matriz de caracteres recién asignada cuya longitud es la longitud de esta cadena y cuyo contenido se inicializa para contener la secuencia de caracteres representada por esta cadena.

// Editar 1

He cambiado la prueba para engañar a la optimización JIT.

// Editar 2

Repita la prueba 10 veces para dejar que JVM se caliente.

// Editar 3

Conclusiones:

En primer lugar, str.toCharArray();copia la cadena completa en la memoria. Puede consumir memoria para cadenas largas. El método String.charAt( )busca char en una matriz de caracteres dentro del índice de comprobación de la clase String antes Parece que el primer método de Strings lo suficientemente corto (es decir, chatAtmétodo) es un poco más lento debido a esta comprobación de índice. Pero si la cadena es lo suficientemente larga, la copia de toda la matriz de caracteres se vuelve más lenta y el primer método es más rápido. Cuanto más larga es la cadena, más lento se toCharArrayrealiza. Intenta cambiar el límite en for(int j = 0; j < 10000; j++)bucle para verlo. Si dejamos que el código de calentamiento JVM se ejecute más rápido, pero las proporciones son las mismas.

Después de todo, es solo micro-optimización.

Piotr Gwiazda
fuente
¿Podría probar la for:inopción, solo por el gusto de hacerlo?
dasblinkenlight
2
Su punto de referencia es defectuoso: no permite que el JIT haga sus optimizaciones; el JIT podría eliminar los bucles por completo, ya que no hacen nada.
JB Nizet
La cadena no es na Iterableni matriz.
Piotr Gwiazda
2
Esta no es una prueba válida, ha 'calentado' su JVM con la Prueba 1, que puede sesgar los resultados hacia el favor de la Prueba 2. Toda la pregunta del OP huele a micro optimización de todos modos.
Percepción el
1
Cierto. Después del calentamiento (ver Edición 2) ambas veces son más pequeñas pero aún están cerca una de la otra. En mi ejemplo, la segunda prueba es un poco más rápida. Pero si alargo la Cadena, la primera es más rápida. La cadena más larga es la segunda prueba más lenta, debido a la copia de la matriz de caracteres. Solo hazlo de la primera manera.
Piotr Gwiazda
2

String.toCharArray()crea una nueva matriz de caracteres, significa la asignación de memoria de la longitud de la cadena, luego copia la matriz de caracteres original de la cadena utilizando System.arraycopy()y luego devuelve esta copia a la persona que llama. String.charAt () devuelve el carácter en la posición ide la copia original, por eso String.charAt()será más rápido que String.toCharArray(). Sin embargo, String.toCharArray()devuelve una copia y no un carácter de la matriz de cadenas original, donde String.charAt()devuelve el carácter de la matriz de caracteres original. El siguiente código devuelve el valor en el índice especificado de esta cadena.

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

el siguiente código devuelve una matriz de caracteres recién asignada cuya longitud es la longitud de esta cadena

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

El segundo hace que se cree una nueva matriz de caracteres, y todos los caracteres de la Cadena se copien en esta nueva matriz de caracteres, por lo que supongo que el primero es más rápido (y requiere menos memoria).

JB Nizet
fuente