StringBuilder を使用した文字列連結の最適化

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参照先「Cracking thecoding Interview」ゲイル・ラークマン・マクダウェル著

多数の文字列を連結したいと想像してください。文字列の長さがすべて同じ x で、文字列が n 個あると仮定すると、 がかかります。 $O(x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx)$O(x+2x+...+nx) 時間。連結するたびに、前の文字列のコピーを作成し、新しい文字列をコピーします。したがって、最初の反復では x 文字をコピーする必要があります。次の反復では、2 倍の文字をコピーする必要があり、以下同様です。

実際には、前述のランタイムをさらに単純化することができます。

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

したがって、この問題における文字列の連結には時間がかかります $O(x{n}^2)$O(xn 2) 完了するまでの時間。私に言わせればかなり長いです。アルゴリズムは次のとおりです:

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

StringBuilder クラス

StringBuilder クラスは、この長い実行時間を回避するのに役立ちます。単純に、このクラスはすべての文字列のサイズ変更可能な配列を作成し、必要な場合にのみそれらを文字列にコピーして戻します。

JavaScript では、サイズ変更可能な配列で join メソッドを使用するだけで、文字列のリストを文字列にコピーできます。

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

    return sentence.join("");
}

ここで、配列に文字列を追加するには、 $O(1)$O(1) 操作ごとの時間。配列を単一の文字列にコピーする最後のステップは、 $O(n)$O(n) 時間。n は配列内の文字列の数です。

以上がStringBuilder を使用した文字列連結の最適化の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。