Zeitliche Komplexität von Javas Teilzeichenfolge ()

Was ist die zeitliche Komplexität der String#substring()Methode in Java?

Neue Antwort

Ab Update 6 in Java 7 Lebzeiten das Verhalten substringgeändert , um eine Kopie zu erstellen - so dass jeder Stringauf eine bezieht , char[]die sich nicht mit einem anderen Objekt geteilt, soweit mir bekannt ist . Zu diesem Zeitpunkt substring()wurde also eine O (n) -Operation, bei der n die Zahlen in der Teilzeichenfolge sind.

Alte Antwort: vor Java 7

Undokumentiert - aber in der Praxis O (1), wenn Sie davon ausgehen, dass keine Speicherbereinigung erforderlich ist usw.

Es wird einfach ein neues StringObjekt erstellt, das sich auf denselben Basiswert bezieht, char[]jedoch unterschiedliche Offset- und Zählwerte aufweist. Die Kosten sind also die Zeit, die benötigt wird, um die Validierung durchzuführen und ein einzelnes neues (relativ kleines) Objekt zu erstellen. Das ist O (1), soweit es sinnvoll ist, über die Komplexität von Vorgängen zu sprechen, die je nach Speicherbereinigung, CPU-Caches usw. zeitlich variieren können. Insbesondere hängt dies nicht direkt von der Länge der ursprünglichen Zeichenfolge oder des Teilstrings ab .

In älteren Java-Versionen war es O (1) - wie Jon sagte, wurde gerade ein neuer String mit demselben zugrunde liegenden Zeichen [] und einem anderen Versatz und einer anderen Länge erstellt.

Dies hat sich jedoch tatsächlich geändert, beginnend mit Java 7 Update 6.

Die char [] -Freigabe wurde entfernt und die Felder Versatz und Länge wurden entfernt. substring () kopiert jetzt nur alle Zeichen in einen neuen String.

Ergo ist der Teilstring in Java 7 Update 6 O (n)

Es ist jetzt lineare Komplexität. Dies erfolgt nach Behebung eines Speicherverlustproblems für Teilzeichenfolgen.

Denken Sie also ab Java 1.7.0_06 daran, dass String.substring jetzt eine lineare Komplexität anstelle einer konstanten hat.

Hinzufügen von Beweisen zu Jons Antwort. Ich hatte den gleichen Zweifel und wollte überprüfen, ob die Länge der Zeichenfolge Auswirkungen auf die Teilzeichenfolgenfunktion hat. Der folgende Code wurde geschrieben, um zu überprüfen, von welchem ​​Parameter Teilzeichenfolge tatsächlich abhängt.

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

}

Die Ausgabe bei der Ausführung in Java 8 lautet:

 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

Der Nachweis der Teilzeichenfolgenfunktion hängt von der Länge der angeforderten Teilzeichenfolge ab, nicht von der Länge der Zeichenfolge.

O (1) Da die ursprüngliche Zeichenfolge nicht kopiert wird, wird lediglich ein neues Wrapper-Objekt mit unterschiedlichen Versatzinformationen erstellt.

Überzeugen Sie sich selbst davon, aber Javas Leistungsnachteile liegen woanders, nicht hier in der Teilzeichenfolge eines Strings. 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");
    }

Ausgabe:

Teilzeichenfolge 32768 mal
Summe der Teilungslängen = 1494414
Verstrichene 2,446679 ms

Ob es O (1) ist oder nicht, hängt davon ab. Wenn Sie nur auf denselben String im Speicher verweisen , stellen Sie sich einen sehr langen String vor. Sie erstellen einen Teilstring und beenden den Verweis auf einen langen String. Wäre es nicht schön, Speicher für lange Zeit freizugeben?

Vor Java 1.7.0_06: O (1).

Nach Java 1.7.0_06: O (n). Dies wurde aufgrund eines Speicherverlusts geändert. Nachdem die Felder offsetund countaus String entfernt wurden, wurde die Teilstring Implementierung O (n).

Weitere Informationen finden Sie unter: http://java-performance.info/changes-to-string-java-1-7-0_06/