Optimiser la concaténation de chaînes avec StringBuilder

Suppose une compréhension de la notation Big O. Les exemples sont en JavaScript. Références d'informations "Cracking the Coding Interview" par Gayle Laakmann McDowell

Imaginez que vous souhaitiez concaténer un grand nombre de chaînes ensemble. En supposant que les chaînes ont toutes la même longueur x et qu'il y a n chaînes, cela prend $O(x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx)$O(x+2x+...+nx) temps. À chaque concaténation, nous créons une copie de la chaîne précédente et copions la nouvelle chaîne. Ainsi, la première itération nécessiterait de copier x caractères. La prochaine itération nécessiterait de copier 2x caractères, et ainsi de suite.

Nous pouvons en fait simplifier davantage le runtime indiqué précédemment :

$$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

Par conséquent, la concaténation de chaînes dans ce cas prend $O(x{n}^2)$O(xn 2) le temps de terminer. Assez long si vous me demandez. Voici l'algorithme :

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

Classe StringBuilder

Une classe StringBuilder peut vous aider à éviter ce long temps d'exécution. Simplement, cette classe crée un tableau redimensionnable de toutes les chaînes et les recopie dans une chaîne uniquement lorsque cela est nécessaire.

En JavaScript, on peut simplement utiliser la méthode join sur un tableau redimensionnable pour copier la liste des chaînes dans une chaîne.

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

    return sentence.join("");
}

Maintenant, ajouter une chaîne au tableau prend $O(1)$O(1) temps par opération. La dernière étape de copie du tableau dans une seule chaîne prend $O(n)$O(n) time, où n est le nombre de chaînes dans le tableau.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!