Optimieren der String-Verkettung mit StringBuilder

Setzt Verständnis der Big-O-Notation voraus. Beispiele sind in JavaScript. Informationsreferenzen „Cracking the Coding Interview“ von Gayle Laakmann McDowell

Stellen Sie sich vor, Sie möchten eine große Anzahl von Zeichenfolgen miteinander verketten. Unter der Annahme, dass die Zeichenfolgen alle die gleiche Länge x haben und es n Zeichenfolgen gibt, dauert es $O(x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx)$O(x+2x+...+nx) Zeit. Bei jeder Verkettung erstellen wir eine Kopie der vorherigen Zeichenfolge und kopieren die neue Zeichenfolge. Daher würde die erste Iteration das Kopieren von x Zeichen erfordern. Die nächste Iteration würde das Kopieren von 2x Zeichen usw. erfordern.

Wir können die zuvor angegebene Laufzeit tatsächlich noch weiter vereinfachen:

$$x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx=x(1+2+\mathrm{.}\mathrm{.}\mathrm{.}+n)=x(\frac{n(n-1)}{2})=x{n}^2$$x+2x+...+nx=x(1 +2+...+n)=x(2n(n−1)​)=xn2

Daher dauert das Verketten von Zeichenfolgen in dieser Angelegenheit $O(x{n}^2)$O(xn 2) Zeit zum Abschluss. Ziemlich lange, wenn du mich fragst. Hier ist der Algorithmus:

function joinWords(words) {
    let sentence = "";
    for (let w of words) {
        sentence = sentence + w;
    }
    return sentence;
}

StringBuilder-Klasse

Eine StringBuilder-Klasse kann Ihnen helfen, diese lange Laufzeit zu vermeiden. Diese Klasse erstellt einfach ein in der Größe veränderbares Array aller Strings und kopiert sie nur bei Bedarf zurück in einen String.

In JavaScript können wir einfach die Join-Methode für ein Array mit veränderbarer Größe verwenden, um die Liste der Zeichenfolgen in eine Zeichenfolge zu kopieren.

function joinWords(words) {
    let sentence = [];
    for (let w of words) {
        sentence.push(w);
    }

    return sentence.join("");
}

Das Anhängen einer Zeichenfolge an das Array dauert nun $O(1)$O(1) Zeit pro Vorgang. Der letzte Schritt des Kopierens des Arrays in eine einzelne Zeichenfolge dauert $O(n)$O(n) Zeit, wobei n die Anzahl der Strings im Array ist.

Das obige ist der detaillierte Inhalt vonOptimieren der String-Verkettung mit StringBuilder. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!