A maneira mais rápida de iterar sobre todos os caracteres em uma String

163

Em Java, qual seria a maneira mais rápida de iterar todos os caracteres em uma String?

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

Ou isto:

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

EDIT:

O que eu gostaria de saber é se o custo de chamar o charAtmétodo repetidamente durante uma iteração longa acaba sendo menor ou maior que o custo de executar uma única chamada toCharArrayno início e acessar diretamente a matriz durante a iteração.

Seria ótimo se alguém pudesse fornecer uma referência robusta para diferentes comprimentos de string, tendo em mente o tempo de aquecimento do JIT, o tempo de inicialização da JVM, etc., e não apenas a diferença entre duas chamadas para System.currentTimeMillis().

Óscar López
fonte
18
Com o que aconteceu for (char c : chars)?
precisa saber é o seguinte
O primeiro deve ser mais rápido e, de qualquer maneira, uma string, uma matriz de caracteres, teoricamente.
Keagan Ladds
O Google geralmente é um bom recurso: mkyong.com/java/…
Johan Sjöberg
2
A questão não pede o desempenho do uso de iteradores, foreach. O que eu gostaria de saber é se o custo de ligar repetidamente charAtacaba sendo menor ou maior que o custo de realizar uma única ligação paratoCharArray
Óscar López
1
Alguém já fez uma análise com StringCharacterIterator ?
bdrx

Respostas:

352

PRIMEIRA ATUALIZAÇÃO: Antes de tentar isso em um ambiente de produção (não recomendado), leia primeiro: http://www.javaspecialists.eu/archive/Issue237.html A partir do Java 9, a solução descrita não funcionará mais , porque agora o Java armazenará seqüências de caracteres como byte [] por padrão.

SEGUNDA ATUALIZAÇÃO: A partir de 25/10/2016, no meu AMDx64 8core e na fonte 1.8, não há diferença entre usar 'charAt' e acesso ao campo. Parece que a jvm está suficientemente otimizada para alinhar e otimizar qualquer chamada 'string.charAt (n)'.

Tudo depende da duração da Stringinspeção. Se, como diz a pergunta, for para cadeias longas , a maneira mais rápida de inspecionar a cadeia é usar a reflexão para acessar o respaldo char[]da cadeia.

Um benchmark totalmente randomizado com JDK 8 (win32 e win64) em um AMD Phenom II 4 core 955 a 3.2 GHZ 64 (no modo cliente e no servidor) com 9 técnicas diferentes (veja abaixo!) Mostra que o uso String.charAt(n)é o mais rápido para pequenas empresas. strings e o uso reflectionpara acessar a matriz de apoio String é quase duas vezes mais rápido para strings grandes.

O EXPERIMENTO

  • São testadas 9 técnicas de otimização diferentes.

  • Todo o conteúdo da string é randomizado

  • O teste é feito para tamanhos de string em múltiplos de dois começando com 0,1,2,4,8,16 etc.

  • Os testes são feitos 1.000 vezes por tamanho de string

  • Os testes são embaralhados em ordem aleatória a cada vez. Em outras palavras, os testes são feitos em ordem aleatória toda vez que são feitos, mais de 1000 vezes.

  • Todo o conjunto de testes é feito para a frente e para trás, para mostrar o efeito do aquecimento da JVM na otimização e nos tempos.

  • Todo o conjunto é feito duas vezes, uma no -clientmodo e a outra no -servermodo.

CONCLUSÕES

modo de cliente (32 bits)

Para cadeias de caracteres de 1 a 256 caracteres , a chamada string.charAt(i)vence com um processamento médio de 13,4 a 588 milhões de caracteres por segundo.

Além disso, é globalmente 5,5% mais rápido (cliente) e 13,9% (servidor) como este:

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

do que assim com uma variável local de comprimento final:

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

Para seqüências longas, o tamanho de 512 a 256K caracteres , o uso da reflexão para acessar o array de backup da String é mais rápido. Essa técnica é quase duas vezes mais rápida que String.charAt (i) (178% mais rápida). A velocidade média nesse intervalo foi de 1.111 bilhões de caracteres por segundo.

O campo deve ser obtido com antecedência e, em seguida, pode ser reutilizado na biblioteca em diferentes cadeias. Curiosamente, ao contrário do código acima, com o acesso ao campo, é 9% mais rápido ter uma variável de comprimento final local do que usar 'chars.length' na verificação do loop. Aqui está como o acesso ao campo pode ser configurado o mais 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);
   }

Comentários especiais no modo -server

O acesso ao campo começa a ganhar depois de 32 caracteres de comprimento no modo servidor em uma máquina Java de 64 bits na minha máquina AMD 64. Isso não foi visto até os 512 caracteres de comprimento no modo cliente.

Também vale a pena notar que, quando eu estava executando o JDK 8 (compilação de 32 bits) no modo de servidor, o desempenho geral foi 7% mais lento para cadeias grandes e pequenas. Isso ocorreu com a versão 121 de dezembro de 2013 da versão inicial do JDK 8. Portanto, por enquanto, parece que o modo de servidor de 32 bits é mais lento que o modo de cliente de 32 bits.

Dito isto ... parece que o único modo de servidor que vale a pena chamar está em uma máquina de 64 bits. Caso contrário, ele realmente prejudica o desempenho.

Para compilação de 32 bits rodando em -server modeum AMD64, posso dizer o seguinte:

  1. String.charAt (i) é o vencedor claro em geral. Embora entre os tamanhos de 8 a 512 caracteres, houve vencedores entre 'novo' 'reutilizar' e 'campo'.
  2. String.charAt (i) é 45% mais rápido no modo cliente
  3. O acesso ao campo é duas vezes mais rápido para Strings grandes no modo cliente.

Também vale a pena dizer, String.chars () (Stream e a versão paralela) são um fracasso. Muito mais lento do que qualquer outro caminho. A StreamsAPI é uma maneira bastante lenta de executar operações gerais de string.

Lista de Desejos

O Java String pode ter um predicado que aceita métodos otimizados, como contains (predicado), forEach (consumidor), forEachWithIndex (consumidor). Portanto, sem a necessidade do usuário saber o tamanho ou repetir as chamadas para os métodos String, isso pode ajudar a analisar a beep-beep beepaceleração das bibliotecas .

Continue sonhando :)

Cordas felizes!

~ SH

O teste usou os 9 métodos a seguir para testar a cadeia de caracteres quanto à presença de espaço em branco:

"charAt1" - VERIFIQUE O CONTEÚDO DA CORDA DA MANEIRA USUAL:

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" - O MESMO ACIMA, MAS USE String.length () EM VEZ DE FAZER UM LOCAL FINAL int PARA O COMPRIMENTO

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

"stream" - USE o IntStream do novo JAVA-8 String e passe um predicado para a verificação

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

"streamPara" - O MESMO ACIMA, MAS OH-LA-LA - VAI PARALELO !!!

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

"reutilizar" - recarregue um caractere reutilizável [] COM O CONTEÚDO DAS CORDAS

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" - OBTENHA UMA NOVA CÓPIA DO char [] DA 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" - O MESMO ACIMA, MAS USE "PARA CADA"

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

"campo1" - FANTÁSTICO !! OBTENHA UM CAMPO PARA ACESSO AO CARACTER INTERNA DO 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" - O MESMO ACIMA, MAS USAR "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 COMPOSITOS PARA O -clientMODO CLIENTE (testes para frente e para trás combinados)

Nota: que o modo -client com Java de 32 bits e o modo -server com Java de 64 bits são os mesmos que abaixo na minha 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 COMPOSITOS PARA O -serverMODO SERVIDOR (testes para frente e para trás combinados)

Nota: este é o teste para Java de 32 bits em execução no modo de servidor em um AMD64. O modo de servidor para Java de 64 bits era igual ao Java de 32 bits no modo de cliente, exceto que o acesso ao campo começou a ganhar após o tamanho 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 RUNNABLE COMPLETO

(para testar no Java 7 e versões anteriores, remova os dois testes de fluxos)

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("");
    }
}
O coordenador
fonte
1
Este teste foi executado na JVM do servidor ou JVM do cliente? As melhores otimizações são feitas apenas na JVM do servidor. Se você executou usando a JVM padrão de 32 bits e nenhum argumento, executou no modo cliente.
ceklock
2
Obter o buffer de backup é problemático no caso de substrings ou strings criadas usando String (char [], int, int), pois você obtém o buffer inteiro (pelo menos no Android), mas sua indexação será baseada em zero. No entanto, se você souber que não possui uma substring, ele funcionará bem.
Prewett
5
Alguma idéia de por que "for (int i = 0; i <data.length (); i ++)" é mais rápido do que definir data.length () como uma variável local final?
skyin
2
A definição de uma variável requer uma operação de pilha no código de método byte. Porém, as otimizações, ao reconhecer seu algoritmo, podem rastrear rapidamente essa operação repetida no código de máquina real, sem a sobrecarga da alocação de variáveis. Essas otimizações às vezes existem nos compiladores de bytecode, às vezes não. Tudo depende se o JVM é inteligente o suficiente :-)
O Coordenador
2
@ David, os números são a taxa (em nanossegundos) por caractere inspecionado. Menor é melhor.
The Coordinator
14

É apenas uma micro-otimização com a qual você não deve se preocupar.

char[] chars = str.toCharArray();

retorna uma cópia das strmatrizes de caracteres (no JDK, retorna uma cópia dos caracteres chamando System.arrayCopy).

Fora isso, str.charAt()apenas verifica se o índice está realmente dentro dos limites e retorna um caractere no índice da matriz.

O primeiro não cria memória adicional na JVM.

Buhake Sindi
fonte
Não responde a pergunta. Esta pergunta é sobre desempenho. Pelo que você sabe, o OP pode ter descoberto que a iteração sobre seqüências de caracteres é um custo importante em sua aplicação.
rghome
9

Apenas por curiosidade e para comparar com a resposta de Saint Hill.

Se você precisar processar dados pesados, não deverá usar a JVM no modo cliente. O modo cliente não é feito para otimizações.

Vamos comparar os resultados dos benchmarks do @Saint Hill usando uma JVM nos modos Client e Server.

Core2Quad Q6600 G0 @ 2.4GHz
JavaSE 1.7.0_40

Veja também: Diferenças reais entre "servidor java" e "cliente java"?


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

CONCLUSÃO:

Como você pode ver, o modo servidor é muito mais rápido.

ceklock
fonte
2
Obrigado por publicar. Portanto, para cadeias grandes, o acesso ao campo ainda é 2x mais rápido que o charAt (). De fato, o acesso ao campo tornou-se ainda mais rápido, levando-o depois de 28 strings de comprimento (louco !!) Então ... o modo servidor torna tudo mais rápido. Muito interessante!
The Coordinator
1
Sim, o método reflexivo é realmente mais rápido. Interessante.
ceklock
2
btw: JVMs mais recentes figuras automaticamente quais dos -server ou -client que funciona melhor (geralmente): docs.oracle.com/javase/7/docs/technotes/guides/vm/...
jontejj
2
@jontejj na prática, não é tão simples. Se você estiver executando uma JVM de 32 bits no Windows, a JVM sempre assumirá o padrão como cliente.
ceklock
7

O primeiro a usar str.charAtdeve ser mais rápido.

Se você digitar dentro do código-fonte da Stringclasse, podemos ver que charAté implementado da seguinte maneira:

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

Aqui, tudo o que faz é indexar uma matriz e retornar o valor.

Agora, se observarmos a implementação de toCharArray, encontraremos o seguinte:

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 você vê, está fazendo um System.arraycopyque definitivamente será um pouco mais lento do que não fazê-lo.

adarshr
fonte
2
É bobagem que a String # charAt faça uma verificação extra do índice, quando o índice for verificado de qualquer maneira no acesso ao array.
Ingo
1
Correndo o risco de reviver um encadeamento de 8 anos ... O array de caracteres atrás de uma string pode ser maior que a própria string. Ou seja, se você tivesse uma string "abcde" e usasse a substring para extrair "bcd" em uma nova string, a nova string será apoiada exatamente pelo mesmo array de caracteres da primeira string. É por isso que a classe da string mantém um deslocamento e uma contagem - para saber quais caracteres na matriz são os que representam essa string. Portanto, a verificação do intervalo é importante, caso contrário, seria possível acessar caracteres além das extremidades dessa sequência.
dty
3

Apesar da resposta de @Saint Hill, se você considerar a complexidade de tempo de str.toCharArray () ,

o primeiro é mais rápido, mesmo para cordas muito grandes. Você pode executar o código abaixo para ver por si mesmo.

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

resultado:

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

Parece que niether é mais rápido ou mais 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 cordas longas, escolherei a primeira. Por que copiar em seqüências longas? A documentação diz:

public char [] toCharArray () Converte essa string em uma nova matriz de caracteres.

Retorna: uma matriz de caracteres recém-alocada cujo comprimento é o comprimento dessa sequência e cujo conteúdo é inicializado para conter a sequência de caracteres representada por essa sequência.

// Editar 1

Mudei o teste para enganar a otimização do JIT.

// Editar 2

Repita o teste 10 vezes para permitir que a JVM se aqueça.

// Editar 3

Conclusões:

Primeiro, str.toCharArray();copia toda a sequência na memória. Pode consumir memória para seqüências longas. O método String.charAt( )procura char na matriz char dentro da classe String, verificando o índice antes. Parece que, por um curto período de tempo, o primeiro método Strings ( chatAtmétodo) é um pouco mais lento devido a essa verificação de índice. Mas se a String for longa o suficiente, a cópia de toda a matriz de caracteres fica mais lenta e o primeiro método é mais rápido. Quanto mais longa a string, mais lenta será a toCharArrayexecução. Tente alterar o limite no for(int j = 0; j < 10000; j++)loop para vê-lo. Se permitirmos que o código de aquecimento da JVM seja executado mais rapidamente, mas as proporções são as mesmas.

Afinal, é apenas micro-otimização.

Piotr Gwiazda
fonte
Você poderia tentar a for:inopção, apenas por diversão?
precisa saber é o seguinte
2
Seu benchmark é falho: não permite que o JIT faça suas otimizações; o JIT pode remover completamente os loops, pois eles não fazem nada.
JB Nizet
String não é Iterablenem matriz.
Piotr Gwiazda
2
Este não é um teste válido, você 'aqueceu' sua JVM com o Teste 1, o que pode inclinar os resultados para o favor do Teste 2. A questão do OP cheira a micro otimização de qualquer maneira.
Percepção
1
Verdade. Após o aquecimento (consulte a Edição 2), os dois tempos são menores, mas ainda próximos um do outro. No meu exemplo, o segundo teste é um pouco mais rápido. Mas se eu prolongar a String, a primeira será mais rápida. Quanto maior a string, o segundo teste mais lento é devido à cópia da matriz de caracteres. Apenas faça da primeira maneira.
Piotr Gwiazda
2

String.toCharArray()cria uma nova matriz de caracteres, significa alocação de memória do comprimento da string, copia a matriz original da string de caracteres usando System.arraycopy()e retorna essa cópia para o chamador. String.charAt () retorna o caractere na posição ida cópia original, é por isso String.charAt()que será mais rápido que String.toCharArray(). Embora, String.toCharArray()retorne cópia e não char da matriz String original, onde String.charAt()retorna caracteres da matriz char original. O código abaixo retorna o valor no índice especificado dessa sequência.

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

O código abaixo retorna uma matriz de caracteres recém-alocada cujo comprimento é o comprimento dessa string

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

O segundo faz com que um novo array de caracteres seja criado, e todos os caracteres da String sejam copiados para esse novo array de caracteres, portanto, acho que o primeiro é mais rápido (e consome menos memória).

JB Nizet
fonte