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

Question

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

Answer 1

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

Cependant, cela a en fait commencé avec Java 7 mise à jour 6.

Le partage char[] a été supprimé, et les champs offset et length ont été supprimés.subing () ne fait plus que copier tous les caractères dans une nouvelle chaîne.

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

Answer 2

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

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

Answer 3

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 a des effets sur la fonction de sous-chaîne. Ecrit le code suivant pour vérifier sur quel paramètre la sous-chaîne 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 à l'exécution en 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 démonstration de la fonction de sous-chaîne dépend de la longueur de sous-chaîne demandée et non de la longueur de la chaîne.

Answer 4

O(1) parce qu'aucune copie de la chaîne originale n'est faite, il suffit de créer un nouvel objet wrapper avec des informations de décalage différentes.