Complexidade de tempo da substring do Java ()

Qual é a complexidade de tempo do String#substring() método em Java?

Nova resposta

A partir da atualização 6 dentro do tempo de vida do Java 7, o comportamento de substringmudou para criar uma cópia - então, cada Stringse refere a um char[]que não é compartilhado com nenhum outro objeto, pelo que eu sei. Então, nesse ponto,substring() tornou-se uma operação O (n) onde n são os números na substring.

Resposta antiga: pré-Java 7

Não documentado - mas na prática O (1) se você assumir que nenhuma coleta de lixo é necessária, etc.

Ele simplesmente cria um novo Stringobjeto referindo-se ao mesmo subjacente, char[]mas com diferentes valores de deslocamento e contagem. Portanto, o custo é o tempo gasto para realizar a validação e construir um único objeto novo (razoavelmente pequeno). Isso é O (1) na medida em que seja sensato falar sobre a complexidade das operações que podem variar no tempo com base na coleta de lixo, caches de CPU etc. Em particular, não depende diretamente do comprimento da string original ou da substring .

Era O (1) em versões anteriores do Java - como Jon afirmou, ele apenas criou uma nova String com o mesmo char [] subjacente e um deslocamento e comprimento diferentes.

No entanto, isso realmente mudou a partir da atualização 6 do Java 7.

O compartilhamento de char [] foi eliminado e os campos de deslocamento e comprimento foram removidos. substring () agora apenas copia todos os caracteres em uma nova String.

Portanto, a substring é O (n) na atualização 6 do Java 7

Agora é uma complexidade linear. Isso depois de corrigir um problema de vazamento de memória para a substring.

Portanto, a partir do Java 1.7.0_06, lembre-se de que String.substring agora tem uma complexidade linear em vez de constante.

Adicionando prova à resposta de Jon. Tive a mesma dúvida e queria verificar se o comprimento da string tem algum efeito na função da substring. Escrito a seguir o código para verificar de qual substring de parâmetro realmente depende.

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

}

A saída na execução em Java 8 é:

 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

A função de comprovação da substring depende do comprimento da substring solicitada e não do comprimento da string.

O (1) porque nenhuma cópia da string original é feita, ele apenas cria um novo objeto wrapper com informações de deslocamento diferentes.

Julgue por si mesmo a partir do seguinte, mas as desvantagens de desempenho do Java estão em outro lugar, não aqui na substring de uma string. 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");
    }

Resultado:

substring 32768 vezes
Soma dos comprimentos das divisões = 1494414
Decorrido 2,446679 ms

Se é O (1) ou não, depende. Se você apenas referenciar a mesma String na memória, então imagine uma String muito longa, você faz substring e pára de referenciar uma longa. Não seria bom liberar memória por muito tempo?

Antes do Java 1.7.0_06: O (1).

Após Java 1.7.0_06: O (n). Isso foi alterado devido ao vazamento de memória. Depois que os campos offsete countforam removidos de String, a implementação da substring tornou-se O (n).

Para obter mais detalhes, consulte: http://java-performance.info/changes-to-string-java-1-7-0_06/