Mengapa senar sangat lambat?

23

Sejak kelas pemrograman pertama saya di sekolah menengah, saya telah mendengar bahwa operasi string lebih lambat - yaitu lebih mahal - daripada mitos "operasi rata-rata." Mengapa membuatnya begitu lambat? (Pertanyaan ini sengaja dibiarkan melebar.)

computer-science strings Pops
sumber
11
Jika Anda tahu bahwa "operasi rata-rata" ini adalah mitos, bisakah Anda setidaknya memberi tahu kami beberapa di antaranya? Mengingat Anda mengajukan pertanyaan yang samar-samar, sulit untuk mempercayai pernyataan Anda bahwa operasi yang tidak ditentukan ini benar-benar mitos.
seh
1
@ Seh, sayangnya, saya sebenarnya tidak bisa menjawabnya. Beberapa kali saya benar-benar bertanya kepada orang-orang string apa yang lebih lambat daripada, mereka hanya mengangkat bahu dan berkata "mereka hanya lambat." Selain itu, jika saya memiliki informasi yang lebih spesifik, ini akan menjadi pertanyaan untuk SO, bukan Programmer; sudah agak batas.
Pops
Apa intinya ? Jika string yang diceritakan benar-benar lambat, apakah Anda akan berhenti menggunakannya?
Tulains Córdova
Lupakan. Jika seseorang memberi tahu Anda omong kosong seperti itu, pertanyaan tandingannya adalah: "Benarkah? Apakah mereka? Haruskah kita menggunakan int-array?"
Ingo

Jawaban:

47

"Operasi rata-rata" berlangsung pada primitif. Tetapi bahkan dalam bahasa di mana string diperlakukan sebagai primitif, mereka masih array di bawah tenda, dan melakukan apa pun yang melibatkan seluruh string membutuhkan waktu O (N), di mana N adalah panjang string.

Misalnya, menambahkan dua angka biasanya membutuhkan 2-4 instruksi ASM. Menggabungkan ("menambahkan") dua string memerlukan alokasi memori baru dan satu atau dua salinan string, yang melibatkan seluruh string.

Faktor-faktor bahasa tertentu dapat memperburuknya. Dalam C, misalnya, string hanyalah sebuah penunjuk ke array karakter yang diakhiri null. Ini berarti bahwa Anda tidak tahu berapa lama, jadi tidak ada cara untuk mengoptimalkan loop penyalinan string dengan operasi gerakan cepat; Anda perlu menyalin satu karakter pada satu waktu sehingga Anda dapat menguji setiap byte untuk terminator nol.

Mason Wheeler
sumber
4
Dan bahasa-bahasa tertentu membuatnya jauh lebih baik: Pengkodean panjang string Delphi pada awal array membuat penggabungan string sangat cepat.
Frank Shearar
4
@ Gablin: Ini juga membantu dengan membuat penyalinan string lebih cepat. Ketika Anda mengetahui ukuran di muka, Anda tidak perlu menyalin satu byte pada satu waktu dan memeriksa setiap byte untuk terminator nol, sehingga Anda dapat menggunakan ukuran penuh register apa pun, termasuk yang SIMD, untuk pergerakan data, membuat itu hingga 16 kali lebih cepat.
Mason Wheeler
4
@mathepic: Ya, dan itu tidak masalah untuk sejauh yang akan Anda lakukan, tetapi ketika Anda mulai berinteraksi dengan libc atau kode eksternal lainnya, ia mengharapkan char*, bukan strbuf, dan Anda kembali ke titik 1. Hanya ada begitu banyak Anda dapat dilakukan ketika desain yang buruk dimasukkan ke dalam bahasa.
Mason Wheeler
6
@ mathepic: Tentu saja bufpetunjuknya ada di sana. Saya tidak pernah bermaksud mengatakan bahwa itu tidak tersedia; sebaliknya, itu perlu. Kode apa pun yang tidak tahu tentang tipe string Anda yang dioptimalkan-tetapi-tidak-standar, termasuk hal-hal mendasar seperti pustaka standar , masih harus kembali pada lambat, tidak aman char*. Anda dapat memanggil FUD itu jika Anda mau, tetapi itu tidak membuatnya tidak benar.
Mason Wheeler
7
Teman-teman, ada kolom Joel Spolsky tentang poin Frank Shearer: Kembali ke Dasar
user16764
14

Ini adalah utas lama dan saya pikir jawaban lainnya bagus, tetapi mengabaikan sesuatu, jadi inilah (sen) 2 sen saya.

Gula-Lapisan Sintaksis Menyembunyikan Kompleksitas

Masalah dengan string adalah bahwa mereka adalah warga negara kelas dua di sebagian besar bahasa, dan pada kenyataannya sebagian besar waktu sebenarnya bukan bagian dari spesifikasi bahasa itu sendiri: mereka adalah konstruksi yang diimplementasikan oleh perpustakaan dengan beberapa lapisan gula sintaksis sesekali di bagian atas untuk membuat mereka kurang dari rasa sakit untuk digunakan.

Konsekuensi langsung dari ini adalah bahwa bahasa menyembunyikan bagian yang sangat besar dari kerumitannya jauh dari pandangan Anda, dan Anda membayar untuk efek samping licik karena Anda tumbuh menjadi kebiasaan menganggap mereka seperti entitas atom tingkat rendah, seperti tipe primitif lainnya (seperti yang dijelaskan oleh jawaban terpilih dan lainnya).

Detail Implementasi

Array Ol Baik

Salah satu elemen dari "kompleksitas" yang mendasarinya adalah sebagian besar implementasi string akan menggunakan struktur data sederhana dengan beberapa ruang memori yang berdekatan untuk merepresentasikan string: array yang baik dari Anda.

Ini masuk akal, ingatlah, karena Anda ingin akses ke string secara keseluruhan menjadi cepat. Tapi itu menyiratkan kemungkinan biaya yang mengerikan ketika Anda ingin memanipulasi string ini. Mengakses elemen di tengah mungkin cepat jika Anda tahu indeks apa yang Anda cari, tetapi mencari elemen berdasarkan suatu kondisi tidak.

Bahkan mengembalikan ukuran string mungkin mahal, jika bahasa Anda tidak men-cache panjang string dan perlu dijalankan untuk menghitung karakter.

Untuk alasan yang sama, menambahkan elemen ke string Anda akan terbukti mahal karena kemungkinan besar Anda perlu mengalokasikan kembali sejumlah memori agar operasi ini dapat terjadi.

Jadi, bahasa yang berbeda mengambil pendekatan yang berbeda untuk masalah ini. Java, misalnya, mengambil kebebasan membuat string tidak berubah untuk beberapa alasan yang valid (panjang caching, keamanan thread) dan untuk rekan-rekan yang bisa berubah (StringBuffer dan StringBuilder) akan memilih untuk mengalokasikan ukuran menggunakan potongan berukuran lebih besar untuk tidak perlu mengalokasikan setiap saat, tetapi lebih berharap untuk skenario kasus terbaik. Ini umumnya bekerja dengan baik, tetapi sisi buruknya adalah terkadang membayar dampak memori.

Dukungan Unicode

Juga, dan sekali lagi ini disebabkan oleh fakta bahwa lapisan gula sintaksis bahasa Anda menyembunyikan ini dari Anda untuk bermain bagus, Anda sering tidak menganggapnya sebagai dukungan unicode (terutama selama Anda tidak benar-benar membutuhkannya) dan menabrak dinding itu). Dan beberapa bahasa, sebagai pemikiran ke depan, tidak menerapkan string dengan array mendasar dari primitif char 8-bit sederhana. Mereka dipanggang dalam dukungan UTF-8 atau UTF-16 atau apa pun yang Anda miliki untuk Anda, dan konsekuensinya adalah konsumsi memori yang jauh lebih besar, yang sering kali tidak diperlukan, dan waktu pemrosesan yang lebih besar untuk mengalokasikan memori, memproses string, dan mengimplementasikan semua logika yang sejalan dengan memanipulasi poin kode.

Hasil dari semua ini, adalah ketika Anda melakukan sesuatu yang setara dalam pseudo-code ke:

hello = "hello,"
world = " world!"
str = hello + world

Mungkin tidak - terlepas dari semua upaya terbaik yang dilakukan pengembang bahasa untuk membuat mereka berperilaku seperti yang Anda inginkan - sesederhana:

a = 1;
b = 2;
shouldBeThree = a + b

Sebagai tindak lanjut, Anda mungkin ingin membaca:

haylem
sumber
Tambahan yang bagus untuk diskusi saat ini.
Abel
Saya baru menyadari ini adalah jawaban terbaik karena pernyataan mistis dapat diterapkan untuk apa pun seperti enkripsi RSA lambat. Satu-satunya alasan string diletakkan di tempat yang memalukan ini adalah karena operator plus menyediakan string dalam sebagian besar bahasa, yang membuat pemula tidak menyadari biaya di balik operasi.
Codism
@ Bel: terima kasih, bagi saya sepertinya ada ruang untuk detail yang lebih umum.
haylem
@Codism: terima kasih, senang Anda menyukainya. Saya memang berpikir ini dapat diterapkan pada banyak kasus di mana itu hanya masalah kompleksitas yang disembunyikan (dan dari kita tidak terlalu memperhatikan detail level yang lebih rendah lagi sampai akhirnya kita perlu karena kita menabrak bottleneck atau brickwall semacam) ).
haylem
1

Ungkapan "operasi rata-rata" mungkin singkatan untuk operasi tunggal dari mesin Program Acak-Tersimpan Program teoritis . Ini adalah mesin teoretis yang biasa digunakan untuk menganalisis waktu berjalan berbagai algoritma.

Operasi generik biasanya diambil untuk memuat, menambah, mengurangi, menyimpan, cabang. Mungkin juga membaca, mencetak, dan berhenti.

Tetapi sebagian besar operasi string memerlukan beberapa operasi mendasar ini. Misalnya, menduplikasi string biasanya membutuhkan operasi penyalinan, dan karenanya sejumlah operasi yang sebanding dengan panjang string (yaitu, "linier"). Menemukan substring di dalam string lain juga memiliki kompleksitas linier.

James Youngman
sumber
1

Ini sepenuhnya tergantung pada operasi, bagaimana string diwakili, dan optimasi apa yang ada. Jika panjang string 4 atau 8 byte (dan disejajarkan), mereka tidak akan selalu lebih lambat - banyak operasi akan sama cepatnya dengan primitif. Atau, jika semua string memiliki hash 32-bit atau 64-bit, banyak operasi juga akan sama cepat (meskipun Anda membayar biaya hashing di depan).

Ini juga tergantung pada apa yang Anda maksud dengan "lambat". Sebagian besar program akan memproses string dengan cepat untuk apa yang dibutuhkan. Perbandingan string mungkin tidak secepat membandingkan dua int, tetapi hanya profil yang akan mengungkapkan apa artinya "lambat" untuk program Anda.

Kevin Hsu
sumber
0

Biarkan saya menjawab pertanyaan Anda dengan pertanyaan. Mengapa mengucapkan serangkaian kata lebih lama daripada mengucapkan satu kata?

Kekacauan Kekacauan
sumber
2
Itu belum tentu.
user16764
3
Supercalifragilisticexpialidocious
Spoike
s / word / syllable / g
Caleb
Biarkan saya menjawab pertanyaan-jawaban Anda dengan pertanyaan: mengapa Anda tidak mengatakan apa arti jawaban Anda? Lagi pula, jauh dari kejelasan bagaimana hal itu dapat diartikan sebagai penerapan pada sistem run-time.
PJTraill