Berapa banyak string yang dibuat dalam memori ketika menggabungkan string di Jawa?

Saya ditanya tentang string yang tidak dapat diubah di Jawa. Saya ditugaskan menulis fungsi yang menggabungkan sejumlah "a" ke string.

Apa yang saya tulis:

public String foo(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a"
    }
    return s;
}

Saya kemudian ditanya berapa banyak string yang dihasilkan program ini, dengan asumsi pengumpulan sampah tidak terjadi. Pikiranku untuk n = 3 adalah

1. ""
2. "Sebuah"
3. "Sebuah"
4. "A A"
5. "Sebuah"
6. "aaa"
7. "Sebuah"

Intinya 2 string dibuat di setiap iterasi dari loop. Namun, jawabannya adalah n ² . String apa yang akan dibuat dalam memori oleh fungsi ini dan mengapa demikian?

Saya kemudian ditanya berapa banyak string yang dihasilkan program ini, dengan asumsi pengumpulan sampah tidak terjadi. Pikiranku untuk n = 3 adalah (7)

String 1 ( "") dan 2 ( "a") adalah konstanta dalam program, ini tidak dibuat sebagai bagian dari hal-hal tetapi 'diinternir' karena mereka adalah konstanta yang diketahui kompiler. Baca lebih lanjut tentang ini di String magang di Wikipedia.

Ini juga menghilangkan string 5 dan 7 dari hitungan karena mereka sama "a" dengan String # 2. Ini menyisakan string # 3, # 4, dan # 6. Jawabannya adalah "3 string dibuat untuk n = 3" menggunakan kode Anda.

Hitungan n ² jelas salah karena pada n = 3, ini akan menjadi 9 dan bahkan dengan jawaban kasus terburuk Anda, itu hanya 7. Jika string non-magang Anda benar, jawabannya harus 2n +1.

Jadi, pertanyaan bagaimana Anda harus melakukan ini?

Karena String tidak dapat diubah , Anda menginginkan benda yang dapat berubah - sesuatu yang dapat Anda ubah tanpa membuat objek baru. Itu adalah StringBuilder .

Hal pertama yang harus dilihat adalah konstruktor. Dalam hal ini kita tahu berapa lama string akan, dan ada konstruktor StringBuilder(int capacity) yang berarti kita mengalokasikan persis seperti yang kita butuhkan.

Selanjutnya, "a"tidak perlu menjadi String , tetapi itu bisa berupa karakter 'a'. Ini memiliki beberapa peningkatan kinerja kecil saat memanggil append(String)vs append(char)- dengan append(String), metode perlu mengetahui berapa lama String dan melakukan beberapa pekerjaan pada itu. Di samping itu,char selalu tepat satu karakter.

Perbedaan kode dapat dilihat di StringBuilder.append (String) vs StringBuilder.append (char) . Ini bukan sesuatu yang terlalu diperhatikan, tetapi jika Anda mencoba mengesankan majikan, sebaiknya gunakan praktik terbaik yang ada.

Jadi, bagaimana ini terlihat ketika Anda menyatukannya?

public String foo(int n) {
    StringBuilder sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) {
        sb.append('a');
    }
    return sb.toString();
}

Satu StringBuilder dan satu String telah dibuat. Tidak ada string tambahan yang perlu diinternir.

Tulis beberapa program sederhana lainnya di Eclipse. Instal pmd dan jalankan pada kode yang Anda tulis. Catat apa yang dikeluhkan dan perbaiki hal-hal itu. Ini akan menemukan modifikasi dari String dengan + dalam satu lingkaran, dan jika Anda mengubah bahwa untuk StringBuilder, itu akan mungkin menemukan kapasitas awal, tapi itu pasti akan menangkap perbedaan antara .append("a")dan.append('a')

Pada setiap iterasi, yang baru Stringdibuat oleh +operator dan ditugaskan untuk s. Setelah kembali, mereka semua tetapi yang terakhir adalah sampah.

Konstanta string suka ""dan "a"tidak dibuat setiap saat, ini adalah string yang diinternir . Karena string tidak dapat diubah, string dapat dengan bebas dibagikan; ini terjadi pada konstanta string.

Untuk menggabungkan string secara efisien, gunakan StringBuilder.

Seperti yang dijelaskan MichaelT dalam jawabannya, kode Anda mengalokasikan string O (n). Tetapi juga mengalokasikan O (n ² ) byte memori dan berjalan dalam waktu O (n ² ).

Ini mengalokasikan O (n ² ) byte, karena string yang Anda alokasikan memiliki panjang 0, 1, 2,…, n-1, n, yang berjumlah hingga (n ² + n) / 2 = O (n ² ).

Waktunya juga O (n ² ), karena mengalokasikan string ke-i memerlukan penyalinan (ke-1) -t string, yang memiliki panjang i-1. Ini berarti setiap byte yang dialokasikan harus disalin, yang akan memakan waktu O (n ² ) waktu.

Mungkin ini yang dimaksud pewawancara?