Mengoptimumkan Penggabungan Rentetan dengan StringBuilder

Menganggap pemahaman tatatanda Big O. Contohnya adalah dalam JavaScript. Rujukan maklumat "Cracking the Coding Interview" oleh Gayle Laakmann McDowell

Bayangkan anda ingin menggabungkan sejumlah besar rentetan bersama-sama. Dengan mengandaikan semua rentetan adalah sama panjang x dan terdapat n rentetan, ia memerlukan $O(x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx)$O(x+2x+...+nx) masa. Pada setiap gabungan, kami mencipta salinan rentetan sebelumnya dan menyalin rentetan baharu. Oleh itu, lelaran pertama memerlukan penyalinan x aksara. Lelaran seterusnya memerlukan penyalinan 2x aksara, dan seterusnya.

Kami sebenarnya boleh memudahkan lagi masa jalan yang dinyatakan sebelum ini:

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

Oleh itu, rentetan penggabungan dalam perkara ini memerlukan $O(x{n}^2)$O(xn 2) masa untuk disiapkan. Agak panjang jika anda bertanya kepada saya. Inilah algoritmanya:

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

Kelas StringBuilder

Kelas

StringBuilder boleh membantu anda mengelakkan masa jalan yang panjang ini. Secara mudah, kelas ini mencipta tatasusunan boleh diubah saiz semua rentetan dan menyalinnya kembali ke rentetan hanya apabila perlu.

Dalam JavaScript, kita hanya boleh menggunakan kaedah gabungan pada tatasusunan boleh ubah saiz untuk menyalin senarai rentetan ke dalam rentetan.

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

    return sentence.join("");
}

Sekarang, menambahkan rentetan pada tatasusunan mengambil masa

$O(1\mathrm{})O(1)$O(1) masa setiap operasi. Langkah terakhir untuk menyalin tatasusunan kepada satu rentetan mengambil masa $O(n)O(n)$O(n) masa, dengan n ialah bilangan rentetan dalam tatasusunan.

Atas ialah kandungan terperinci Mengoptimumkan Penggabungan Rentetan dengan StringBuilder. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!