Jika string tidak dapat diubah dalam. NET, lalu mengapa Substring membutuhkan waktu O (n)?

Mengingat bahwa string tidak dapat diubah dalam. NET, saya bertanya-tanya mengapa mereka dirancang sedemikian rupa sehingga string.Substring()membutuhkan waktu O ( substring.Length), bukan O(1)?

yaitu apa pengorbanan, jika ada?

UPDATE: Saya sangat menyukai pertanyaan ini, saya hanya menulis blognya. Lihat String, kekekalan, dan ketekunan

Jawaban singkatnya adalah: O (n) adalah O (1) jika n tidak tumbuh besar. Kebanyakan orang mengekstraksi substring kecil dari string kecil, jadi bagaimana kompleksitas tumbuh asimptotik sama sekali tidak relevan .

Jawaban panjangnya adalah:

Struktur data yang tidak dapat diubah yang dibangun sedemikian rupa sehingga operasi berdasarkan contoh mengizinkan penggunaan kembali memori sumber asli dengan hanya sejumlah kecil (biasanya O (1) atau O (lg n)) penyalinan atau alokasi baru disebut "persisten" struktur data tidak berubah. String dalam. NET tidak dapat diubah; pertanyaan Anda pada dasarnya adalah "mengapa mereka tidak gigih"?

Karena ketika Anda melihat operasi yang biasanya dilakukan pada string dalam program .NET, dalam segala hal yang relevan sama sekali lebih buruk sama sekali untuk hanya membuat string yang sama sekali baru. Biaya dan kesulitan membangun struktur data persisten yang kompleks tidak membayar untuk dirinya sendiri.

Orang biasanya menggunakan "substring" untuk mengekstraksi string pendek - katakanlah, sepuluh atau dua puluh karakter - dari string yang agak lebih panjang - mungkin beberapa ratus karakter. Anda memiliki satu baris teks dalam file yang dipisahkan koma dan Anda ingin mengekstrak bidang ketiga, yang merupakan nama belakang. Panjang barisnya mungkin beberapa ratus karakter, namanya beberapa lusin. Alokasi string dan penyalinan memori lima puluh byte sangat cepat pada perangkat keras modern. Bahwa membuat struktur data baru yang terdiri dari pointer ke tengah string yang ada ditambah panjangnya juga sangat cepat tidak relevan; "cukup cepat" menurut definisi cukup cepat.

Substring yang diekstraksi biasanya berukuran kecil dan pendek seumur hidup; pengumpul sampah akan mendapatkan kembali mereka segera, dan mereka tidak mengambil banyak ruang di tumpukan di tempat pertama. Jadi menggunakan strategi gigih yang mendorong penggunaan kembali sebagian besar memori juga bukan merupakan kemenangan; semua yang Anda lakukan adalah membuat pengumpul sampah Anda menjadi lebih lambat karena sekarang harus khawatir tentang penanganan pointer interior.

Jika operasi substring yang biasanya dilakukan orang pada string sama sekali berbeda, maka masuk akal untuk menggunakan pendekatan yang gigih. Jika orang biasanya memiliki string jutaan karakter, dan mengekstraksi ribuan substring yang tumpang tindih dengan ukuran dalam kisaran seratus ribu karakter, dan substring tersebut bertahan lama di heap, maka masuk akal jika menggunakan substring yang persisten. pendekatan; akan sia-sia dan bodoh untuk tidak melakukannya. Tetapi kebanyakan programmer lini bisnis tidak melakukan apa-apa bahkan secara samar-samar seperti hal-hal semacam itu. .NET bukan platform yang dirancang untuk kebutuhan Proyek Genom Manusia; Pemrogram analisis DNA harus menyelesaikan masalah dengan karakteristik penggunaan string tersebut setiap hari; kemungkinan besar Anda tidak melakukannya. Beberapa yang memang membangun struktur data persisten mereka sendiri yang sangat cocok dengan skenario penggunaannya.

Misalnya, tim saya menulis program yang melakukan analisis langsung kode C # dan VB saat Anda mengetiknya. Beberapa file kode itu sangat besar dan karenanya kita tidak dapat melakukan manipulasi string O (n) untuk mengekstraksi substring atau menyisipkan atau menghapus karakter. Kami telah membangun sekelompok struktur data berubah terus-menerus untuk mewakili suntingan ke buffer teks yang memungkinkan kita untuk dengan cepat dan efisien kembali menggunakan sebagian besar data string yang ada dan analisis leksikal dan sintaksis yang ada di atas sunting khas. Ini adalah masalah yang sulit untuk dipecahkan dan solusinya secara sempit disesuaikan dengan domain spesifik dari pengeditan kode C # dan VB. Tidak realistis mengharapkan tipe string bawaan untuk menyelesaikan masalah ini bagi kami.

Justru karena String tidak dapat diubah, .Substringharus membuat salinan setidaknya sebagian dari string asli. Membuat salinan n byte harus memakan waktu O (n).

Bagaimana menurut Anda Anda akan menyalin banyak byte dalam waktu yang konstan ?

EDIT: Mehrdad menyarankan untuk tidak menyalin string sama sekali, tetapi menyimpan referensi untuk sepotong itu.

Pertimbangkan dalam. Net, string multi-megabyte, tempat seseorang memanggil .SubString(n, n+3)(untuk sembarang n di tengah-tengah string).

Sekarang, SELURUH string tidak dapat Dikumpulkan Sampah hanya karena satu referensi berpegang pada 4 karakter? Itu tampak seperti pemborosan ruang.

Selanjutnya, melacak referensi ke substring (yang bahkan mungkin berada di dalam substring), dan mencoba menyalin pada waktu yang optimal untuk menghindari mengalahkan GC (seperti dijelaskan di atas), membuat konsep mimpi buruk. Adalah jauh lebih sederhana, dan lebih dapat diandalkan, untuk menyalin .SubString, dan memelihara model yang tidak berubah secara langsung.

EDIT: Ini sedikit bacaan yang bagus tentang bahaya menyimpan referensi ke substring dalam string yang lebih besar.

Java (sebagai lawan dari .NET) menyediakan dua cara untuk melakukan Substring(), Anda dapat mempertimbangkan apakah Anda ingin hanya menyimpan referensi atau menyalin seluruh substring ke lokasi memori baru.

Sederhana .substring(...)berbagi chararray yang digunakan secara internal dengan objek String asli, yang kemudian Anda new String(...)dapat salin ke array baru, jika diperlukan (untuk menghindari pengumpulan sampah menghalangi yang asli).

Saya pikir fleksibilitas semacam ini adalah pilihan terbaik bagi pengembang.

Java digunakan untuk referensi string yang lebih besar, tetapi:

Java mengubah perilakunya menjadi penyalinan juga, untuk menghindari kebocoran memori.

Saya merasa seperti itu dapat ditingkatkan: mengapa tidak melakukan penyalinan secara kondisional?

Jika substring setidaknya setengah ukuran induk, orang dapat mereferensikan induk. Kalau tidak, orang hanya dapat membuat salinan. Ini menghindari kebocoran banyak memori sambil tetap memberikan manfaat yang signifikan.

Tidak ada jawaban di sini yang membahas "masalah bracketing", yaitu untuk mengatakan bahwa string dalam. NET direpresentasikan sebagai kombinasi dari BStr (panjang yang disimpan dalam memori "sebelum" pointer) dan CStr (string berakhir dengan '\ 0').

String "Hello there" dengan demikian direpresentasikan sebagai

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(jika ditugaskan ke char*dalam- fixedpernyataan yang pointer akan menunjuk ke 0x48.)

Struktur ini memungkinkan pencarian cepat dari panjang string (berguna dalam banyak konteks) dan memungkinkan penunjuk untuk diteruskan dalam API P / Invoke to Win32 (atau lainnya) yang mengharapkan string yang diakhiri dengan null.

Ketika Anda melakukan Substring(0, 5)"oh, tapi saya berjanji akan ada karakter nol setelah karakter terakhir" aturan mengatakan Anda perlu membuat salinan. Bahkan jika Anda mendapatkan substring di akhir maka tidak akan ada tempat untuk meletakkan panjang tanpa merusak variabel lainnya.

Namun, kadang-kadang, Anda benar-benar ingin berbicara tentang "tengah-tengah string", dan Anda tidak perlu peduli dengan perilaku P / Invoke. Struktur yang baru ditambahkan ReadOnlySpan<T>dapat digunakan untuk mendapatkan substring tanpa salinan:

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

The ReadOnlySpan<char>"substring" toko panjang secara independen, dan hal itu bukan jaminan bahwa ada '\ 0' setelah akhir nilai. Ini dapat digunakan dalam banyak cara "seperti string", tetapi itu bukan "string" karena tidak memiliki karakteristik BStr atau CStr (apalagi keduanya). Jika Anda tidak pernah (secara langsung) P / Aktifkan maka tidak ada banyak perbedaan (kecuali API yang ingin Anda panggil tidak memiliki ReadOnlySpan<char>kelebihan).

ReadOnlySpan<char>tidak dapat digunakan sebagai bidang tipe referensi, jadi ada juga ReadOnlyMemory<char>( s.AsMemory(0, 5)), yang merupakan cara tidak langsung untuk memiliki ReadOnlySpan<char>, sehingga perbedaan-dari-yang sama stringada.

Beberapa jawaban / komentar pada jawaban sebelumnya berbicara tentang pemborosan untuk membuang sampah dengan jutaan karakter, sementara Anda terus berbicara sekitar 5 karakter. Itulah perilaku yang bisa Anda dapatkan dengan ReadOnlySpan<char>pendekatan itu. Jika Anda hanya melakukan perhitungan singkat, pendekatan ReadOnlySpan mungkin lebih baik. Jika Anda perlu bertahan sebentar dan Anda hanya akan menyimpan sebagian kecil dari string asli, melakukan substring yang tepat (untuk memotong kelebihan data) mungkin lebih baik. Ada titik transisi di suatu tempat di tengah, tetapi itu tergantung pada penggunaan khusus Anda.