Mengapa penghapusan biasanya lebih sulit untuk diterapkan daripada penyisipan dalam banyak struktur data?

33

Bisakah Anda memikirkan alasan khusus mengapa penghapusan biasanya jauh lebih sulit untuk diterapkan daripada penyisipan untuk banyak (kebanyakan?) Struktur data?

Contoh cepat: daftar tertaut. Penyisipan itu sepele, tetapi penghapusan memiliki beberapa kasus khusus yang membuatnya lebih sulit. Pohon pencarian biner yang menyeimbangkan diri sendiri seperti AVL dan Merah-hitam adalah contoh klasik implementasi penghapusan yang menyakitkan.

Saya ingin mengatakan itu ada hubungannya dengan cara kebanyakan orang berpikir: lebih mudah bagi kita untuk mendefinisikan sesuatu secara konstruktif, yang mengarah dengan baik ke penyisipan yang mudah.

algorithms data-structures Leo Brito
sumber
4
Bagaimana pop, extract-min?
coredump
5
"Lebih sulit untuk diterapkan" lebih merupakan masalah psikologi (kognisi dan kekuatan & kelemahan pikiran manusia) daripada pemrograman (sifat struktur data & algoritma).
outis
1
Seperti yang saya pikir coredump disinggung, tumpukan harus setidaknya semudah untuk menghapus seperti menambahkan (untuk stack yang didukung array, popping hanyalah penurunan pointer [1] sedangkan mendorong dapat memerlukan salinan array keseluruhan jika Anda menekan ukuran maksimum dari array). Juga ada beberapa kasus penggunaan di mana diasumsikan bahwa penyisipan akan sering dan penghapusan kurang begitu tetapi itu akan menjadi struktur data yang sangat ajaib di mana jumlah penghapusan melebihi penyisipan. [1] Anda mungkin juga harus membatalkan referensi yang sekarang tidak terlihat ke objek yang muncul untuk menghindari kebocoran memori, yang saya ingat karena buku teks Liskov tidak
Foon
43
"Pelayan, bisakah kamu menambahkan lebih banyak mayo ke sandwich ini?" "Tentu, tidak masalah, Tuan." "Bisakah kamu juga menghapus semua mustard?" "Uh ......"
cobaltduck
3
Mengapa pengurangan lebih rumit daripada penambahan? Divisi (atau faktorisasi utama) lebih rumit daripada perkalian? Akar lebih rumit daripada eksponensial?
mu terlalu pendek

Jawaban:

69

Ini lebih dari sekadar kondisi pikiran; ada alasan fisik (yaitu digital) mengapa penghapusan lebih sulit.

Ketika Anda menghapus, Anda meninggalkan lubang di mana sesuatu dulu. Istilah teknis untuk entropi yang dihasilkan adalah "fragmentasi." Dalam daftar tertaut, ini mengharuskan Anda untuk "menambal" simpul yang dihapus dan membatalkan alokasi memori yang digunakannya. Pada pohon biner, itu menyebabkan ketidakseimbangan pohon. Dalam sistem memori, ini menyebabkan memori tidak digunakan untuk sementara waktu jika blok yang baru dialokasikan lebih besar daripada blok yang ditinggalkan oleh penghapusan.

Singkatnya, penyisipan lebih mudah karena Anda bisa memilih di mana Anda akan memasukkan. Penghapusan lebih sulit karena Anda tidak dapat memperkirakan sebelumnya item mana yang akan dihapus.

Robert Harvey
sumber
3
Fragmentasi bukan masalah di mana pointer & tipuan ikut bermain, baik untuk struktur di memori atau dalam diagram. Dalam memori, tidak masalah di mana setiap node ada karena tipuan. Untuk daftar, menghapus simpul internal (yang merupakan tempat Anda memiliki lubang dalam diagram) melibatkan operasi yang sedikit lebih sedikit daripada penyisipan (1 penugasan pointer dan 1 alokasi gratis vs. 1 alokasi dan 2 penunjuk pointer). Untuk pohon, memasukkan simpul bisa membuat pohon tidak seimbang seperti halnya penghapusan. Ini kasus tepi yang menyebabkan kesulitan mengacu pada brito, di mana fragmentasi tidak masalah.
outis
12
Saya tidak setuju bahwa penyisipan dan penghapusan berbeda dalam prediktabilitas. "Menambal" simpul daftar adalah apa yang terjadi secara terbalik jika simpul yang sama yang akan dimasukkan. Tidak ada ketidakpastian di kedua arah pada titik mana pun, dan dalam wadah apa pun tanpa struktur intrinsik untuk elemen-elemennya (misalnya pohon biner seimbang, susunan dengan hubungan yang ketat antara offset elemen) tidak ada "lubang" sama sekali. Karena itu, saya khawatir saya tidak tahu apa yang Anda bicarakan di sini.
sqykly
2
Sangat menarik, tapi menurut saya argumennya ketinggalan. Anda dapat mengatur struktur data sekitar penghapusan sederhana / cepat tanpa masalah. Itu hanya kurang umum, kemungkinan besar juga kurang bermanfaat.
Luk32
@sqykly Saya pikir daftar adalah contoh pilihan yang buruk karena penyisipan tengah dan hubungan tengah sama-sama sulit. Satu case mengalokasikan memori di mana yang lain dialokasikan kembali. Satu membuka lubang di mana yang lain menutup lubang. Jadi tidak semua case terhapus lebih kompleks dari pada add.
ydobonebi
36

Mengapa cenderung lebih sulit untuk dihapus daripada disisipkan? Struktur data dirancang lebih dengan mempertimbangkan penyisipan daripada penghapusan, dan memang seharusnya begitu.

Pertimbangkan ini - untuk menghapus sesuatu dari struktur data, itu harus ada di tempat pertama. Jadi, Anda perlu menambahkannya terlebih dahulu, yang berarti bahwa paling banyak Anda memiliki penghapusan sebanyak yang Anda miliki sisipan. Jika Anda mengoptimalkan struktur data untuk penyisipan, Anda dijamin akan mendapatkan setidaknya sebanyak manfaat seolah-olah telah dioptimalkan untuk dihapus.

Selain itu, apa gunanya menghapus setiap elemen secara berurutan? Mengapa tidak memanggil beberapa fungsi yang menghapusnya sekaligus (mungkin hanya dengan membuat yang baru)? Juga, struktur data paling berguna ketika mereka benar-benar mengandung sesuatu. Jadi kasus penghapusan sebanyak insersi, dalam praktiknya, tidak akan menjadi sangat umum.

Ketika Anda mengoptimalkan sesuatu, Anda ingin mengoptimalkan hal-hal yang paling banyak dilakukan dan yang paling lama. Dalam penggunaan normal, penghapusan elemen struktur data lebih jarang terjadi daripada penyisipan.

Rob Watts
sumber
4
Ada satu kasus penggunaan yang bisa saya bayangkan. Struktur data yang disiapkan untuk penyisipan awal dan kemudian konsumsi individu. Tentu saja ini jarang terjadi, dan tidak terlalu menarik secara algoritmik, karena seperti yang Anda katakan, operasi semacam itu tidak dapat mendominasi penyisipan tanpa gejala. Mungkin ada beberapa harapan pada kenyataannya bahwa penyisipan batch dapat memiliki biaya diamortisasi cukup bagus dan cepat dan mudah untuk dihapus, sehingga akan memiliki penyisipan batch yang rumit namun praktis dan penghapusan individu sederhana dan cepat. Tentu saja kebutuhan praktis yang tidak biasa.
Luk32
1
Ummm, saya pikir contoh bisa menjadi vektor urutan terbalik. Anda dapat menambahkan sejumlah kelemen dengan cukup cepat: membalikkan input dan bergabung dengan vektor yang ada - O(k log k + n). Maka Anda memiliki struktur dengan penyisipan yang cukup rumit tetapi mengonsumsi uelemen-elemen top adalah sepele dan cepat. Ambil yang terakhir udan pindahkan ujung vektor. Padahal, jika ada yang membutuhkan hal seperti itu, aku akan terkutuk. Saya harap ini setidaknya memperkuat argumen Anda.
Luk32
Tidakkah Anda ingin mengoptimalkan untuk pola penggunaan rata-rata daripada apa yang paling Anda lakukan?
Shiv
Antrian kerja FIFO sederhana biasanya akan mencoba mengosongkan sebagian besar waktu. Antrian yang dirancang dengan baik akan dioptimalkan dengan baik (yaitu O (1)) untuk kedua penyisipan dan penghapusan (dan yang sangat baik juga akan mendukung operasi bersamaan cepat, tapi itu masalah yang berbeda).
Kevin
6

Itu tidak sulit.

Dengan daftar tertaut ganda, saat Anda memasukkan, Anda akan mengalokasikan memori, dan kemudian Anda akan menghubungkan dengan kepala atau simpul sebelumnya, dan dengan ekor atau simpul berikutnya. Ketika Anda menghapus, Anda akan memutuskan tautan dari yang persis sama, dan kemudian membebaskan memori. Semua operasi ini simetris.

Ini mengasumsikan bahwa dalam kedua kasus Anda memiliki simpul untuk memasukkan / menghapus. (Dan dalam hal penyisipan, bahwa Anda juga memiliki simpul untuk disisipkan sebelumnya, jadi dengan cara, penyisipan dapat dianggap sebagai sedikit lebih rumit.) Jika Anda mencoba untuk menghapus tidak memiliki simpul untuk dihapus, tetapi payload dari node, maka tentu saja Anda harus terlebih dahulu mencari daftar payload, tapi itu bukan kekurangan penghapusan, bukan?

Dengan pohon seimbang, hal yang sama berlaku: pohon umumnya perlu menyeimbangkan segera setelah penyisipan dan juga segera setelah penghapusan. Merupakan ide bagus untuk mencoba dan hanya memiliki satu rutin penyeimbang, dan menerapkannya setelah setiap operasi, terlepas dari apakah itu penyisipan atau penghapusan. Jika Anda mencoba menerapkan penyisipan yang selalu membuat pohon seimbang, dan juga penghapusan yang selalu membuat pohon seimbang, tanpa keduanya memiliki rutinitas penyeimbang yang sama, Anda tidak perlu mempersulit hidup Anda.

Singkatnya, tidak ada alasan mengapa seseorang harus lebih keras daripada yang lain, dan jika Anda menemukan itu, maka sebenarnya mungkin Anda adalah korban dari kecenderungan (yang sangat manusiawi) untuk menemukan bahwa lebih alami untuk berpikir. konstruktif daripada subtraktif, artinya Anda mungkin menerapkan penghapusan dengan cara yang lebih rumit daripada yang seharusnya. Tapi itu masalah manusia. Dari sudut pandang matematika, tidak ada masalah.

Mike Nakis
sumber
1
Saya harus tidak setuju. Algoritma penghapusan AVL lebih kompleks daripada penyisipan. Untuk penghapusan simpul tertentu, Anda mungkin harus menyeimbangkan seluruh pohon, yang biasanya dilakukan secara rekursif tetapi juga dapat dilakukan secara non-rekursif. Anda tidak harus melakukan ini untuk penyisipan. Saya tidak mengetahui kemajuan algoritma di mana penyeimbangan ulang seluruh pohon dapat dihindari dalam semua kasus.
Dennis
@ Dennis: bisa jadi pohon AVL mengikuti pengecualian daripada aturan.
outis
@outis IIRC, semua pohon pencarian seimbang memiliki rutinitas penghapusan lebih rumit (daripada penyisipan).
Raphael
Bagaimana dengan tabel hash tertutup hashing ? Penyisipan (relatif) mudah, penghapusan setidaknya lebih sulit untuk dikonsep karena Anda harus memperbaiki semua "hal yang seharusnya berada di indeks X saat ini di indeks Y dan kita harus mencari dan meletakkannya kembali" masalah.
Kevin
3

Dalam hal run-time, melihat perbandingan kompleksitas waktu operasi struktur data di Wikipedia, perhatikan operasi insert dan delete memiliki kompleksitas yang sama. Operasi penghapusan diprofilkan ada penghapusan oleh indeks, di mana Anda memiliki referensi ke elemen struktur yang akan dihapus; penyisipan adalah dengan item. Semakin lama waktu berjalan untuk dihapus dalam praktik adalah karena Anda biasanya memiliki item untuk dihapus dan bukan indeksnya, sehingga Anda juga memerlukan operasi pencarian. Sebagian besar struktur data dalam tabel tidak memerlukan penemuan tambahan untuk memasukkan karena posisi penempatan tidak tergantung pada item, atau posisi ditentukan secara implisit selama penyisipan.

Adapun kompleksitas kognitif, ada jawaban dalam pertanyaan: kasus tepi. Penghapusan mungkin memiliki lebih banyak daripada penyisipan (ini belum ditetapkan dalam kasus umum). Namun, setidaknya beberapa kasus tepi ini dapat dihindari dalam desain tertentu (misalnya, memiliki simpul sentinel dalam daftar tertaut).

outis
sumber
2
"Sebagian besar struktur data tidak memerlukan penemuan untuk memasukkan." -- seperti? Saya akan mengajukan klaim sebaliknya. (Anda "menemukan" posisi penyisipan, yang sama mahalnya dengan menemukan elemen yang sama lagi nanti.)
Raphael
@Raphael: Jawaban ini harus dibaca dalam konteks tabel kompleksitas operasi yang tertaut, yang tidak termasuk operasi pencarian sebagai bagian dari penghapusan. Untuk menjawab pertanyaan Anda, saya mengkategorikan struktur berdasarkan nama umum. Dari array, daftar, pohon, tabel hash, tumpukan, antrian, tumpukan, dan set, pohon dan set memerlukan penemuan untuk memasukkan; yang lain menggunakan indeks yang tidak terhubung ke item (untuk tumpukan dasar, antrian dan tumpukan, hanya 1 indeks yang terbuka, dan temuan tidak didukung) atau menghitungnya dari item. Grafik bisa jalan baik, tergantung bagaimana mereka digunakan.
outis
... Mencoba bisa dianggap pohon; Namun, jika diklasifikasikan sebagai struktur mereka sendiri, apakah ada "menemukan" selama penyisipan lebih merupakan masalah perdebatan, jadi saya tidak memasukkannya. Perhatikan bahwa daftar struktur data tidak memperhitungkan antarmuka vs implementasi. Juga, bagaimana Anda menghitung sangat tergantung pada bagaimana Anda mengategorikannya. Saya akan melihat apakah saya bisa memikirkan pernyataan yang lebih objektif.
outis
Saya akui saya memiliki kamus / set antarmuka dalam pikiran (seperti yang umum di CS). Bagaimanapun, tabel itu menyesatkan dan (iirc) bahkan salah di beberapa tempat - Wikipedia, lubang informasi CS yang salah. : /
Raphael
0

Di atas semua masalah yang disebutkan ada integritas referensial data yang terlibat. Untuk membangun struktur data yang paling tepat seperti database dalam SQL, integritas referensial Oracle sangat penting.
Untuk memastikan bahwa Anda tidak sengaja menghancurkannya, banyak hal yang berbeda ditemukan.
Misalnya kaskade pada penghapusan yang tidak hanya menghapus apa yang pernah Anda coba hapus tetapi juga memicu pembersihan data terkait.
Ini membersihkan database dari data sampah serta menjaga integritas data tetap utuh.
Misalnya Anda memiliki tabel dengan orang tua dan jenis sebagai catatan terkait di tabel kedua.
Di mana orang tua adalah tabel utama. Jika Anda tidak memiliki integritas referensial yang diperkuat, Anda dapat menghapus catatan apa pun di tabel mana pun dan nanti Anda tidak akan tahu cara mendapatkan informasi keluarga lengkap karena Anda memiliki data di tabel anak dan tidak ada apa pun di tabel induk.
Itu sebabnya pemeriksaan integritas referensial tidak akan membiarkan Anda menghapus catatan dari tabel induk sampai catatan dari tabel anak dibersihkan.
Dan itulah sebabnya di sebagian besar sumber data lebih sulit untuk menghapus data.

Alex
sumber
Saya pikir pertanyaannya adalah bertanya tentang struktur di dalam memori seperti daftar yang ditautkan, tabel hash, dll. Bukan dari basis data, tetapi integritas referensial adalah masalah utama bahkan dengan struktur di dalam memori.
supercat