Complejidad temporal de la subcadena de Java ()

¿Cuál es la complejidad temporal del String#substring()método en Java?

Nueva respuesta

A partir de la actualización 6 dentro de la vida útil de Java 7, el comportamiento de substringcambió para crear una copia, por lo que cada se Stringrefiere a una char[]que no se comparte con ningún otro objeto, hasta donde yo sé. Entonces, en ese punto, se substring()convirtió en una operación O (n) donde n son los números en la subcadena.

Respuesta anterior: pre-Java 7

Indocumentado, pero en la práctica O (1) si asume que no se requiere recolección de basura, etc.

Simplemente crea un nuevo Stringobjeto que hace referencia al mismo subyacente char[]pero con diferentes valores de compensación y recuento. Por tanto, el coste es el tiempo necesario para realizar la validación y construir un único objeto nuevo (razonablemente pequeño). Eso es O (1) en la medida en que sea sensato hablar sobre la complejidad de las operaciones que pueden variar en el tiempo según la recolección de basura, las cachés de CPU, etc. En particular, no depende directamente de la longitud de la cadena original o la subcadena .

Era O (1) en versiones anteriores de Java; como dijo Jon, acaba de crear una nueva Cadena con el mismo carácter subyacente [], y un desplazamiento y una longitud diferentes.

Sin embargo, esto realmente ha cambiado a partir de la actualización 6 de Java 7.

Se eliminó el uso compartido de caracteres [] y se eliminaron los campos de desplazamiento y longitud. substring () ahora simplemente copia todos los caracteres en una nueva Cadena.

Ergo, la subcadena es O (n) en la actualización 6 de Java 7

Ahora es una complejidad lineal. Esto es después de solucionar un problema de pérdida de memoria para la subcadena.

Entonces, de Java 1.7.0_06 recuerde que String.substring ahora tiene una complejidad lineal en lugar de una constante.

Añadiendo pruebas a la respuesta de Jon. Tenía la misma duda y quería comprobar si la longitud de la cadena tiene algún efecto en la función de subcadena. Escrito el siguiente código para verificar de qué subcadena de parámetros depende realmente.

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

}

El resultado de la ejecución en Java 8 es:

 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

Probar la función de subcadena depende de la longitud de la subcadena solicitada, no de la longitud de la cadena.

O (1) debido a que no se realiza ninguna copia de la cadena original, simplemente crea un nuevo objeto contenedor con diferente información de compensación.

Juzgue usted mismo a partir de lo siguiente, pero los inconvenientes de rendimiento de Java se encuentran en otro lugar, no aquí en la subcadena de una cadena. Código:

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

Salida:

subcadena 32768 veces
Suma de longitudes de divisiones = 1494414
Respuesta 2.446679 ms

Si es O (1) o no, depende. Si solo hace referencia a la misma cadena en la memoria, imagine una cadena muy larga, crea una subcadena y deja de hacer referencia a una larga. ¿No sería bueno liberar la memoria por mucho tiempo?

Antes de Java 1.7.0_06: O (1).

Después de Java 1.7.0_06: O (n). Esto se cambió debido a una pérdida de memoria. Después de que los campos offsety countse eliminaron de String, la implementación de la subcadena se convirtió en O (n).

Para obtener más detalles, consulte: http://java-performance.info/changes-to-string-java-1-7-0_06/