Zeitkomplexität des Java-Substrings()

Question

Was ist die Zeitkomplexität der String#substring()-Methode in Java?

Answer 1

Neue Antwort

Ab Update 6 in Java 7 Lebzeiten, das Verhalten von substring geändert, um eine Kopie zu erstellen - so dass jeder String auf eine char[] bezieht, die nicht geteilt mit einem anderen Objekt ist, wie soweit ich weiß. An diesem Punkt wurde substring() zu einer O (n) -Operation, wobei n die Zahlen in der Teilkette ist.

Alte Antwort: pre-Java 7

Undocumented - aber in der Praxis O (1), wenn Sie übernehmen keine Garbage Collection erforderlich ist, usw.

Es baut einfach ein neues String Objekt mit Bezug auf das gleiche zugrundeliegende char[] aber mit unterschiedlichen Offset- und Zählwerten. Die Kosten sind also die Zeit, die benötigt wird, um eine Validierung durchzuführen und ein einzelnes neues (relativ kleines) Objekt zu konstruieren. Das ist O (1), soweit es sinnvoll ist, über die Komplexität von Operationen zu sprechen, die sich aufgrund von Garbage-Collection, CPU-Caches usw. zeitlich ändern können. Insbesondere hängt sie nicht direkt von der Länge der ursprünglichen oder Teilzeichenfolge ab .

Answer 2

O (1) Da kein Kopieren der ursprünglichen Zeichenfolge durchgeführt wird, wird nur ein neues Wrapper-Objekt mit unterschiedlichen Offset-Informationen erstellt.

Answer 3

Beurteilen Sie selbst von folgenden, aber Java Leistungseinbußen liegen woanders, nicht hier in Teilstring einer Zeichenfolge. 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"); 
    } 

Ausgang:

substring 32768 times 
Sum of lengths of splits = 1494414 
Elapsed 2.446679 ms

Wenn es O (1) ist oder nicht, hängt davon ab. Wenn Sie nur den gleichen String im Speicher referenzieren, dann stellen Sie sich sehr long String vor, machen Sie Teilstring und stoppen Sie den Verweis auf lange. Wäre es nicht schön, die Erinnerung für lange Zeit freizugeben?

Answer 4

Es war O (1) in älteren Versionen von Java - wie Jon sagte, es hat nur einen neuen String mit dem gleichen zugrunde liegenden char [], und einen anderen Offset und Länge.

Dies hat jedoch tatsächlich begonnen änderte sich mit Java 7 Update 6.

Die char [] teilte eliminiert und die Offset- und Längenfelder wurden entfernt. substring() kopiert jetzt nur alle Zeichen in einen neuen String.

Ergo ist Teilzeichenfolge O (n) in Java 7 Update 6

Answer 5

Es ist jetzt lineare Komplexität. Dies ist nach dem Beheben eines Speicherverlustproblems für Teilzeichenfolge.

So von Java 1.7.0_06 erinnern, dass Stringstring jetzt eine lineare Komplexität anstelle einer konstanten Komplexität hat.