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

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 ² . Welche Zeichenfolgen werden durch diese Funktion im Speicher erstellt und warum ist das so?

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 ² 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')

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.

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

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

Die Zeit ist auch O (n ² ), 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 ² ) Zeit in Anspruch nimmt .

Vielleicht haben die Interviewer das so gemeint?