Wie viele Zeichenfolgen werden im Speicher erstellt, wenn Zeichenfolgen in Java verkettet werden?

17

Ich wurde nach unveränderlichen Strings in Java gefragt. Ich wurde beauftragt, eine Funktion zu schreiben, die eine Reihe von "a" zu einer Zeichenkette verkettet.

Was ich schrieb:

public String foo(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a"
    }
    return s;
}

Ich wurde dann gefragt, wie viele Zeichenfolgen dieses Programm generieren würde, vorausgesetzt, dass keine Garbage Collection stattfindet. Meine Gedanken für n = 3 waren

  1. ""
  2. "ein"
  3. "ein"
  4. "aa"
  5. "ein"
  6. "aaa"
  7. "ein"

Im Wesentlichen werden 2 Zeichenfolgen in jeder Iteration der Schleife erstellt. Die Antwort war jedoch n 2 . Welche Zeichenfolgen werden durch diese Funktion im Speicher erstellt und warum ist das so?

ahalbert
quelle
15
Wenn dir dieser Job angeboten wird,
renn
@mattnz aus mehreren Gründen (und nicht nur wegen des geschriebenen Codes).
3
Dies benötigt die Laufzeit von O (n ^ 2), es sei denn, die JIT optimiert die Schleife, erstellt jedoch keine n ^ 2-Zeichenfolgen.
user2357112 unterstützt Monica

Antworten:

26

Ich wurde dann gefragt, wie viele Zeichenfolgen dieses Programm generieren würde, vorausgesetzt, dass keine Garbage Collection stattfindet. Meine Gedanken für n = 3 waren (7)

Die Zeichenfolgen 1 ( "") und 2 ( "a") sind die Konstanten im Programm. Diese werden nicht als Teil von Dingen erstellt, sondern sind "interniert", da es sich um Konstanten handelt, die dem Compiler bekannt sind. Lesen Sie mehr darüber bei String Interning auf Wikipedia.

Dadurch werden auch die Zeichenfolgen 5 und 7 aus der Zählung entfernt, da sie mit der Zeichenfolge "a"2 identisch sind . Dies lässt die Saiten Nr. 3, Nr. 4 und Nr. 6 übrig. Die Antwort lautet "3 Zeichenfolgen werden für n = 3 erstellt" unter Verwendung Ihres Codes.

Die Zahl n 2 ist offensichtlich falsch , weil bei n = 3, 9 wäre und sogar von Ihrem schlimmsten Fall Antwort, die nur 7. Wenn Ihr nicht internierten Strings war richtig war, die Antwort sollte gewesen sein 2n + 1.

Also, die Frage, wie soll man das machen?

Da der String unveränderlich ist , möchten Sie eine veränderbare Sache - etwas, das Sie ändern können, ohne neue Objekte zu erstellen. Das ist der StringBuilder .

Das erste, was wir uns ansehen müssen, sind die Konstrukteure. In diesem Fall wissen wir, wie lang der String sein wird, und es gibt einen Konstruktor, StringBuilder(int capacity) was bedeutet, dass wir genau so viel zuweisen, wie wir brauchen.

Als nächstes "a"muss keine sein String , sondern es kann ein Zeichen sein 'a'. Dies hat einige geringfügige Leistungssteigerungen beim Aufrufen von append(String)vs append(char)- mit der append(String)muss die Methode herausfinden, wie lang der String ist, und etwas daran arbeiten. Andererseits charist immer genau ein Zeichen lang.

Die Codeunterschiede sind bei StringBuilder.append (String) und StringBuilder.append (char) zu sehen . Es ist nicht etwas zu auch besorgt mit, aber wenn Sie versuchen , den Arbeitgeber zu beeindrucken ist es am besten , um die bestmöglichen Praktiken zu verwenden.

Wie sieht das aus, wenn Sie es zusammensetzen?

public String foo(int n) {
    StringBuilder sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) {
        sb.append('a');
    }
    return sb.toString();
}

Ein StringBuilder und ein String wurden erstellt. Es mussten keine zusätzlichen Zeichenfolgen interniert werden.


Schreiben Sie einige andere einfache Programme in Eclipse. Installieren Sie pmd und führen Sie es mit dem von Ihnen geschriebenen Code aus. Beachten Sie, worüber es sich beschwert, und beheben Sie diese Probleme. Es hätte die Änderung eines Strings mit + in einer Schleife gefunden, und wenn Sie dies in StringBuilder geändert hätten, hätte es möglicherweise die ursprüngliche Kapazität gefunden, aber es würde sicherlich den Unterschied zwischen .append("a")und erkennen.append('a')

Gemeinschaft
quelle
9

Bei jeder Iteration Stringwird vom +Operator ein neuer erstellt und zugewiesen s. Nach der Rückkehr werden alle außer den letzten mit dem Müll eingesammelt.

String-Konstanten mögen ""und "a"werden nicht jedes Mal erstellt, dies sind interne Strings . Da Strings unveränderlich sind, können sie frei geteilt werden. Das passiert mit String-Konstanten.

Verwenden Sie, um Zeichenfolgen effizient zu verketten StringBuilder.

9000
quelle
Die Befragten diskutierten tatsächlich darüber, ob es sich um ein Literal handelte oder nicht, und entschieden, dass die Literale jedes Mal erstellt wurden. Das macht aber mehr Sinn.
27.
6
How do you „Debatte“ , was eine Sprache der Fall ist, sicher lesen Sie die Spezifikation und sicher wissen, oder es ist nicht definiert und daher gibt es keine richtige Antwort .....
mattnz
@mattnz Es könnte interessant sein zu wissen, was der von Ihnen verwendete Compiler / die von Ihnen verwendete Laufzeit macht, selbst wenn es um Implementierungsdetails geht. Dies gilt insbesondere für die Leistung.
Svick
1
@svick: Sie können viel gewinnen, indem Sie Annahmen treffen, dann den Compiler aktualisieren, eine Optimierung ändern usw. Das Verhalten ändert sich und führt zu Fehlern, da Sie sich auf nicht angegebenes Verhalten und nicht auf das definierte Verhalten verlassen. Sie wissen, was sie über Optimierung sagen - a) überlassen Sie es Experten und b) Sie sind noch kein Experte. :) Wenn die Abhängigkeit nur von der Leistung, aber immer noch von der Sprachspezifikation abhängt, verliert man nur die Leistung. Oft habe ich gesehen, dass Code, der sich auf ein nicht angegebenes oder compilerspezifisches Verhalten stützte, auf unerwartete Weise kaputt ging (hauptsächlich in C und C ++).
Mattnz
@mattnz Wie schlagen Sie also vor, Entscheidungen in Bezug auf die Leistung zu treffen? Das Beste, was Sie aus der Spezifikation / Dokumentation herausholen können, sind normalerweise große Komplexitäten, aber das reicht nicht aus. In jedem Fall hängt die Leistung immer von der Implementierung ab. Ich denke, es ist in Ordnung, sich bei der Leistung auf die Implementierungsdetails zu verlassen.
Svick
4

Wie MichaelT in seiner Antwort erklärt, weist Ihr Code O (n) Zeichenfolgen zu. Es reserviert aber auch O (n 2 ) Byte Speicher und läuft in O (n 2 ) Zeit.

Sie weist O (n 2 ) Bytes zu, da die von Ihnen zugewiesenen Zeichenfolgen die Längen 0, 1, 2, ..., n-1, n haben, was (n 2 + n) / 2 = O (n 2 ) ergibt .

Die Zeit ist auch O (n 2 ), da das Zuweisen der i-ten Zeichenfolge das Kopieren der (i-1) -ten Zeichenfolge mit der Länge i-1 erfordert. Dies bedeutet, dass jedes zugewiesene Byte kopiert werden muss, was 0 (n 2 ) Zeit in Anspruch nimmt .

Vielleicht haben die Interviewer das so gemeint?

svick
quelle
Sollte die Gleichung nicht (n ^ 2 + n) / 2 sein, wie hier ?
HeyJude