[Java] Il modo più veloce per iterare su tutti i caratteri in una stringa


Answers

Questa è solo una micro-ottimizzazione di cui non dovresti preoccuparti.

char[] chars = str.toCharArray();

restituisce una copia degli array di caratteri str (in JDK restituisce una copia di caratteri chiamando System.arrayCopy ).

Oltre a questo, str.charAt() controlla solo se l'indice è effettivamente in limiti e restituisce un carattere all'interno dell'indice dell'array.

Il primo non crea memoria aggiuntiva in JVM.

Question

In Java, quale sarebbe il modo più veloce per scorrere tutti i caratteri in una stringa, questo:

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

O questo:

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

MODIFICARE :

Quello che mi piacerebbe sapere è se il costo di chiamare ripetutamente il metodo charAt durante una lunga iterazione finisce per essere inferiore o superiore al costo di eseguire una singola chiamata a toCharArray all'inizio e quindi accedere direttamente alla matrice durante iterazione.

Sarebbe bello se qualcuno potesse fornire un solido punto di riferimento per lunghezze di stringa diverse, avendo in mente il tempo di riscaldamento JIT, l'ora di avvio JVM, ecc. E non solo la differenza tra due chiamate a System.currentTimeMillis() .




La seconda causa la creazione di un nuovo array di caratteri e tutti i caratteri della stringa da copiare in questo nuovo array di caratteri, quindi suppongo che il primo sia più veloce (e meno affamato di memoria).




Nonostante la risposta di @Saint Hill se si considera la complessità temporale di str.toCharArray () ,

il primo è più veloce anche per stringhe molto grandi. Puoi eseguire il codice qui sotto per vederlo da solo.

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

produzione:

str.charAt(i):5.492102 (ms)
ch = str.toCharArray() + c = ch[i] :79.400064 (ms)



Il primo che usa str.charAt dovrebbe essere più veloce.

Se si scava all'interno del codice sorgente della classe String , possiamo vedere che charAt è implementato come segue:

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

Qui, tutto ciò che fa è indicizzare una matrice e restituire il valore.

Ora, se vediamo l'implementazione di toCharArray , troveremo il seguente:

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

Come vedi, sta facendo un System.arraycopy che sarà sicuramente un po 'più lento del non farlo.