Complexité temporelle de la sous-chaîne de Java ()

Quelle est la complexité temporelle de la String#substring()méthode en Java?

Nouvelle réponse

A partir de la mise à jour 6 au sein de la vie de Java 7, le comportement de substringchangé pour créer une copie - de sorte que chaque Stringfait référence à un char[]qui est pas partagé avec un autre objet, pour autant que je suis au courant. Donc, à ce stade, substring()est devenue une opération O (n) où n est les nombres de la sous-chaîne.

Ancienne réponse: pré-Java 7

Non documenté - mais en pratique O (1) si vous supposez qu'aucun garbage collection n'est requis, etc.

Il construit simplement un nouvel Stringobjet faisant référence au même sous-jacent char[]mais avec des valeurs de décalage et de comptage différentes. Le coût est donc le temps nécessaire pour effectuer la validation et construire un seul nouvel objet (raisonnablement petit). C'est O (1) dans la mesure où il est raisonnable de parler de la complexité des opérations qui peuvent varier dans le temps en fonction du ramasse-miettes, des caches CPU, etc. En particulier, cela ne dépend pas directement de la longueur de la chaîne d'origine ou de la sous-chaîne .

C'était O (1) dans les anciennes versions de Java - comme Jon l'a dit, il venait de créer une nouvelle chaîne avec le même char sous-jacent [], et un décalage et une longueur différents.

Cependant, cela a en fait changé depuis la mise à jour 6 de Java 7.

Le partage char [] a été éliminé, et les champs offset et length ont été supprimés. substring () copie maintenant simplement tous les caractères dans une nouvelle chaîne.

Ergo, la sous-chaîne est O (n) dans Java 7 mise à jour 6

C'est maintenant une complexité linéaire. C'est après avoir résolu un problème de fuite de mémoire pour la sous-chaîne.

Donc, à partir de Java 1.7.0_06, rappelez-vous que String.substring a maintenant une complexité linéaire au lieu d'une constante.

Ajout de preuves à la réponse de Jon. J'avais le même doute et je voulais vérifier si la longueur de la chaîne avait des effets sur la fonction de la sous-chaîne. Code suivant écrit pour vérifier de quelle sous-chaîne de paramètre dépend réellement.

import org.apache.commons.lang.RandomStringUtils;

public class Dummy {

    private static final String pool[] = new String[3];
    private static int substringLength;

    public static void main(String args[]) {
        pool[0] = RandomStringUtils.random(2000);
        pool[1] = RandomStringUtils.random(10000);
        pool[2] = RandomStringUtils.random(100000);
        test(10);
        test(100);
        test(1000);
    }

    public static void test(int val) {
        substringLength = val;
        StatsCopy statsCopy[] = new StatsCopy[3];
        for (int j = 0; j < 3; j++) {
            statsCopy[j] = new StatsCopy();
        }
        long latency[] = new long[3];
        for (int i = 0; i < 10000; i++) {
            for (int j = 0; j < 3; j++) {
                latency[j] = latency(pool[j]);
                statsCopy[j].send(latency[j]);
            }
        }
        for (int i = 0; i < 3; i++) {
            System.out.println(
                    " Avg: "
                            + (int) statsCopy[i].getAvg()
                            + "\t String length: "
                            + pool[i].length()
                            + "\tSubstring Length: "
                            + substringLength);
        }
        System.out.println();
    }

    private static long latency(String a) {
        long startTime = System.nanoTime();
        a.substring(0, substringLength);
        long endtime = System.nanoTime();
        return endtime - startTime;
    }

    private static class StatsCopy {
        private  long count = 0;
        private  long min = Integer.MAX_VALUE;
        private  long max = 0;
        private  double avg = 0;

        public  void send(long latency) {
            computeStats(latency);
            count++;
        }

        private  void computeStats(long latency) {
            if (min > latency) min = latency;
            if (max < latency) max = latency;
            avg = ((float) count / (count + 1)) * avg + (float) latency / (count + 1);
        }

        public  double getAvg() {
            return avg;
        }

        public  long getMin() {
            return min;
        }

        public  long getMax() {
            return max;
        }

        public  long getCount() {
            return count;
        }
    }

}

La sortie lors de l'exécution dans Java 8 est:

 Avg: 128    String length: 2000    Substring Length: 10
 Avg: 127    String length: 10000   Substring Length: 10
 Avg: 124    String length: 100000  Substring Length: 10

 Avg: 172    String length: 2000    Substring Length: 100
 Avg: 175    String length: 10000   Substring Length: 100
 Avg: 177    String length: 100000  Substring Length: 100

 Avg: 1199   String length: 2000    Substring Length: 1000
 Avg: 1186   String length: 10000   Substring Length: 1000
 Avg: 1339   String length: 100000  Substring Length: 1000

La preuve de la fonction de sous-chaîne dépend de la longueur de la sous-chaîne demandée et non de la longueur de la chaîne.

O (1) car aucune copie de la chaîne d'origine n'est effectuée, il crée simplement un nouvel objet wrapper avec des informations de décalage différentes.

Jugez par vous-même de la suite, mais les inconvénients de performance de Java se trouvent ailleurs, pas ici dans la sous-chaîne d'une chaîne. Code:

public static void main(String[] args) throws IOException {

        String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + 
                "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" +
                "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx";
        int[] indices = new int[32 * 1024];
        int[] lengths = new int[indices.length];
        Random r = new Random();
        final int minLength = 6;
        for (int i = 0; i < indices.length; ++i)
        {
            indices[i] = r.nextInt(longStr.length() - minLength);
            lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength);
        }

        long start = System.nanoTime();

        int avoidOptimization = 0;
        for (int i = 0; i < indices.length; ++i)
            //avoidOptimization += lengths[i]; //tested - this was cheap
            avoidOptimization += longStr.substring(indices[i],
                    indices[i] + lengths[i]).length();

        long end = System.nanoTime();
        System.out.println("substring " + indices.length + " times");
        System.out.println("Sum of lengths of splits = " + avoidOptimization);
        System.out.println("Elapsed " + (end - start) / 1.0e6 + " ms");
    }

Production:

sous-chaîne 32768 fois
Somme des longueurs des divisions = 1494414
Ms 2.446679 écoulé

Si c'est O (1) ou non, cela dépend. Si vous référencez simplement la même chaîne en mémoire, puis imaginez une chaîne très longue, vous créez une sous-chaîne et arrêtez de référencer une chaîne longue. Ne serait-il pas agréable de libérer de la mémoire pendant longtemps?

Avant Java 1.7.0_06: O (1).

Après Java 1.7.0_06: O (n). Cela a été modifié en raison d'une fuite de mémoire. Une fois que les champs offsetet countont été retirés de la chaîne, la mise en œuvre est devenu sous - chaîne O (n).

Pour plus de détails, veuillez vous référer à: http://java-performance.info/changes-to-string-java-1-7-0_06/