In Java, für eine Zeichenfolge x, was sind die Laufzeitkosten von s.length()? Ist es O (1) oder O (n)?

Mir wurde gesagt, dass Code wie zum Beispiel:In Java, für eine Zeichenfolge x, was sind die Laufzeitkosten von s.length()? Ist es O (1) oder O (n)?

for (int i = 0; i < x.length(); i++) { 
    // blah 
}

ist eigentlich O (n^2) wegen der wiederholten Aufrufe von x.length(). Stattdessen sollte ich verwenden:

int l = x.length(); 
for (int i = 0; i < l; i++) { 
    // blah 
}

Ist das wahr? Ist die Stringlänge als privates Ganzzahlattribut der String-Klasse gespeichert? Oder läuft String.length() wirklich die ganze Saite, nur um ihre Länge zu bestimmen?

Quelle

2008-10-31 someguy

Auch wenn die Länge der Zeichenfolge O (n) ist, wäre die Gesamtkomplexität immer noch nicht O (n^2). Die Länge wird einmal berechnet und als Grenzwert in der for-Schleife verwendet. Sie wird nicht bei jeder Iteration berechnet. –

Soweit ich weiß, werden Grenzwerte nicht zwischengespeichert. Was wäre, wenn die Grenze in der Schleife geändert würde? –

Die Grenze wird jedes Mal berechnet. Denken Sie daran, dass die Prüfung der for-Schleife nur ein beliebiger Ausdruck ist. Der Compiler kümmert sich nicht wirklich darum, was da drin ist und kann keine Annahmen machen. Sie könnten leicht eine Methode aufrufen, die jedes Mal etwas anderes zurückgibt. – Herms

Nein, die Länge eines Java-Strings ist O (1), da die String-Klasse von java die Länge als Feld speichert.

Der Hinweis, den Sie erhalten haben, gilt unter anderen Sprachen für C, aber nicht für Java. C strlen geht das Char-Array auf der Suche nach dem Zeichenende. Joel hat darüber im Podcast gesprochen, aber im Zusammenhang mit C.

Quelle

2008-10-31 19:54:26 sblundy

Beachten Sie, dass der Code den Methodenaufruf weiterhin bei jeder Iteration ausführt (der Compiler weiß nicht, dass sich der Wert nicht ändert). Durch Verschieben des Anrufs außerhalb der Schleifensteuerung wird der Methodenaufruf aufgehoben. Nichtsdestoweniger ist es nicht wahrscheinlich, dass viel Änderung in der Ausführungszeit dieser Schleife verursachen wird –

Ein modernes JIT wird wahrscheinlich bemerken, dass length() ein einfacher Getter einer letzten Klasse ist, die einen endgültigen primitiven Wert zurückgibt und das ersetzt Methodenaufruf mit dem int-Wert selbst. –

sk - Ich erinnere mich daran, einen Blog gesehen zu haben, der die JIT-Optimierung von length() getestet hat und bewiesen hat, dass es wahr ist. –

-2

Nach this ist die Länge ein Feld des String-Objekts.

Quelle

2008-10-31 19:55:44

Ich weiß nicht, wie gut der Link übersetzen wird, aber sehen Sie die source of String#length. Kurz gesagt, #length() hat O (1) Komplexität, weil es nur ein Feld zurückgibt. Dies ist einer der vielen Vorteile von unveränderlichen Strings.

Quelle

2008-10-31 19:56:22

Unveränderlichkeit hat damit nichts zu tun. Sie können eine änderbare String-Klasse haben, die ihre Länge verfolgt, genauso wie Sie es mit einer unveränderlichen Zeichenkette (zum Beispiel StringBuilder) tun können. Und Sie können einen unveränderlichen String haben, der das nicht hat (const char * in C). – Herms

Die Unveränderlichkeit garantiert jedoch, dass Sie den Wert für die Länge beim Erstellen des Objekts nur einmal berechnen müssen. Wenn das Objekt veränderbar wäre, würde es für jeden Aufruf einer Mutator-Methode eine neue Berechnung erfordern. Bezahle mich jetzt oder bezahle mich später, wie das Sprichwort sagt. – laz

Genau genommen haben Sie beide Recht; aber Nebenläufigkeit wirft einen Schraubenschlüssel in die ganze Angelegenheit. Der Versuch, ein Hilfsfeld zu aktualisieren, wenn sich die Datenstruktur asynchron ändert, ist im Wesentlichen unmöglich. Deshalb wird länge() in mutierbaren String-Implementierungen oft berechnet und nicht darauf zugegriffen. –

Im Gegensatz zu dem, was bisher gesagt wurde, gibt es keine Garantie, dass String.length() eine konstante Zeitoperation in der Anzahl der Zeichen in der Zeichenfolge ist. Weder die Javadocs für die Klasse String noch die Java Language Specification erfordern String.length als eine konstante Zeitoperation.

In der Implementierung von Sun ist String.length() jedoch eine konstante Zeitoperation. Letztendlich ist es schwer vorstellbar, warum bei einer Implementierung eine nicht konstante Zeitimplementierung für diese Methode verwendet wird.

Quelle

2008-11-01 00:22:12 Alexander

Nichtsdestotrotz glaube ich, dass es sicher ist anzunehmen * dass String.length * immer * konstante Zeit sein wird ... aus den von Ihnen angegebenen Gründen. –

Sie sollten wissen, dass die Methode length() die Anzahl der UTF-16-Codepunkte zurückgibt, die nicht unbedingt mit der Anzahl der Zeichen in allen Fällen übereinstimmen müssen.

OK, die Chancen, dass Sie tatsächlich beeinflussen Sie sind ziemlich schlank, aber es ist nicht schaden, es zu wissen.

Quelle

2008-11-01 02:06:25

http://java.sun.com/javase/6/docs/api/java/lang/Character.html#unicode Grundsätzlich müssen einige Zeichen durch zwei char-Werte dargestellt werden. Da length() die Größe des Arrays char [] hat, stimmt es möglicherweise nicht mit der Anzahl der Zeichen überein. Aber, wie Sadie sagte, das ist sehr selten. –

String speichert die Länge in einer separaten Variablen. Da String unveränderlich ist, wird sich die Länge niemals ändern. Es muss die Länge nur einmal berechnen, wenn es erstellt wird, was geschieht, wenn Speicher dafür reserviert ist. Daher sein O (1)

Quelle

2008-11-01 03:01:17 Satish

Im Fall, dass Sie nicht wissen, dass Sie es auf diese Weise schreiben konnte:

for (int i = 0, l = x.length(); i < l; i++) { 
    // Blah 
}

Es ist nur ein wenig sauberer, da l ‚s Umfang kleiner ist.

Quelle

2008-11-01 03:18:28

In Java, für eine Zeichenfolge x, was sind die Laufzeitkosten von s.length()? Ist es O (1) oder O (n)?

Antwort

Verwandte Themen