Apakah ada cara praktis untuk struktur simpul yang terhubung agar tidak berubah?

26

Saya memutuskan untuk menulis daftar yang terhubung sendiri, dan mempunyai rencana untuk membuat struktur simpul yang terhubung internal tidak dapat diubah.

Tapi aku mengalami kesulitan. Katakanlah saya memiliki simpul tertaut berikut (dari addoperasi sebelumnya ):

1 -> 2 -> 3 -> 4

dan mengatakan saya ingin menambahkan 5.

Untuk melakukan ini, karena simpul 4tidak dapat diubah, saya perlu membuat salinan baru 4, tetapi ganti nextbidangnya dengan simpul baru yang mengandung a 5. Masalahnya sekarang, 3adalah merujuk yang lama 4; yang tanpa menambahkan 5. Sekarang saya perlu menyalin 3, dan mengganti nextbidangnya untuk referensi 4salinan, tetapi sekarang 2referensi yang lama 3...

Atau dengan kata lain, untuk melakukan penambahan, seluruh daftar tampaknya perlu disalin.

Pertanyaan saya:

  • Apakah pemikiran saya benar? Apakah ada cara untuk melakukan penambahan tanpa menyalin seluruh struktur?

  • Rupanya "Java Efektif" berisi rekomendasi:

    Kelas harus abadi kecuali ada alasan yang sangat bagus untuk membuat mereka bisa berubah ...

    Apakah ini kasus yang bagus untuk berubah-ubah?

Saya tidak berpikir ini adalah duplikat dari jawaban yang disarankan karena saya tidak berbicara tentang daftar itu sendiri; yang jelas harus bisa diubah agar sesuai dengan antarmuka (tanpa melakukan sesuatu seperti menyimpan daftar baru secara internal dan mengambilnya melalui pengambil. Pada pemikiran kedua, meskipun itu akan memerlukan beberapa mutasi; itu hanya akan dijaga agar tetap minimum). Saya sedang berbicara tentang apakah internal daftar harus tidak berubah.

Carcigenicate
sumber
Saya akan mengatakan ya - koleksi abadi yang tidak dapat diubah di Jawa adalah yang dengan metode mutasi yang diganti untuk dilemparkan, atau kelas yang sangat mahal yang CopyOnWritexxxdigunakan untuk multi-threading. Tidak ada yang mengharapkan koleksi menjadi benar-benar abadi (walaupun itu membuat beberapa kebiasaan)
Ordous
9
(Mengomentari kutipan.) Itu, kutipan yang bagus, sering sangat disalahpahami. Ketidakmampuan harus diterapkan pada ValueObject karena manfaatnya , tetapi jika Anda berkembang di Jawa, tidak praktis untuk menggunakan kekekalan di tempat-tempat di mana kemantapan diantisipasi. Sebagian besar waktu, sebuah kelas memiliki aspek-aspek tertentu yang harus berubah, dan aspek-aspek tertentu yang perlu diubah berdasarkan persyaratan.
rwong
2
related (mungkin duplikat): Apakah objek koleksi lebih baik tidak berubah? "Tanpa overhead kinerja, bisakah koleksi ini (kelas LinkedList) diperkenalkan sebagai koleksi abadi?"
nyamuk
Mengapa Anda membuat daftar tertaut yang tidak dapat diubah? Manfaat terbesar dari daftar tertaut adalah mutabilitas, bukankah Anda akan lebih baik dengan array?
Pieter B
3
Bisakah Anda membantu saya memahami kebutuhan Anda? Anda ingin memiliki daftar yang tidak dapat diubah, yang ingin Anda mutasi? Bukankah itu kontradiksi? Apa yang Anda maksud dengan "internal" daftar? Apakah maksud Anda bahwa node yang ditambahkan sebelumnya tidak boleh dimodifikasi nanti, tetapi hanya memungkinkan menambahkan ke node terakhir dalam daftar?
null

Jawaban:

46

Dengan daftar dalam bahasa fungsional, Anda hampir selalu bekerja dengan kepala dan ekor, elemen pertama dan sisanya dari daftar. Prepending jauh lebih umum karena, seperti yang Anda duga, menambahkan harus menyalin seluruh daftar (atau struktur data malas lainnya yang tidak persis menyerupai daftar tertaut).

Dalam bahasa imperatif, menambahkan jauh lebih umum, karena cenderung terasa lebih alami secara semantik, dan Anda tidak peduli tentang membatalkan referensi ke versi daftar sebelumnya.

Sebagai contoh mengapa tidak perlu menyalin seluruh daftar, pertimbangkan Anda memiliki:

2 -> 3 -> 4

Prepending a 1memberi Anda:

1 -> 2 -> 3 -> 4

Tetapi perhatikan bahwa tidak masalah jika orang lain masih memegang referensi 2sebagai kepala daftar mereka, karena daftar tersebut tidak dapat diubah dan tautannya hanya berjalan satu arah. Tidak ada cara untuk mengetahui 1apakah bahkan ada jika Anda hanya memiliki referensi 2. Sekarang, jika Anda menambahkan daftar 5ke salah satu daftar, Anda harus membuat salinan dari seluruh daftar, karena jika tidak, daftar itu juga akan muncul di daftar yang lain.

Karl Bielefeldt
sumber
Ahh, poin bagus tentang mengapa tidak perlu perlu menyalin dulu; Saya tidak memikirkan itu.
Carcigenicate
17

Anda benar, menambahkan harus menyalin seluruh daftar jika Anda tidak mau bermutasi di tempat. Karena kita perlu mengatur nextpointer dari simpul kedua ke terakhir (sekarang), yang dalam pengaturan yang tidak berubah menciptakan simpul baru, dan kemudian kita perlu mengatur nextpointer dari simpul ketiga ke terakhir, dan seterusnya.

Saya pikir masalah intinya di sini bukanlah ketidakberdayaan, juga bukan appendoperasi yang keliru. Keduanya baik-baik saja di domain masing-masing. Menggabungkannya adalah buruk: Antarmuka alami (efisien) untuk daftar yang tidak dapat diubah menekankan manipulasi di bagian depan daftar, tetapi untuk daftar yang dapat diubah, sering kali lebih alami untuk membuat daftar dengan berturut-turut menambahkan item dari pertama hingga terakhir.

Oleh karena itu saya menyarankan agar Anda mengambil keputusan: Apakah Anda ingin antarmuka sesaat atau yang gigih? Apakah sebagian besar operasi menghasilkan daftar baru dan membiarkan versi yang tidak dimodifikasi dapat diakses (persisten), atau Anda menulis kode seperti ini (singkat):

list.append(x);
list.prepend(y);

Kedua pilihan itu baik-baik saja, tetapi implementasinya harus mencerminkan antarmuka: Struktur data yang persisten diuntungkan oleh node yang tidak dapat diubah, sementara yang sementara membutuhkan kemampuan mutabilitas internal untuk benar-benar memenuhi kinerja yang dijanjikan secara implisit. java.util.Listdan antarmuka lainnya bersifat sementara: Mengimplementasikannya pada daftar yang tidak dapat diubah adalah tidak pantas dan bahkan merupakan bahaya kinerja. Algoritma yang baik pada struktur data yang dapat berubah seringkali sangat berbeda dari algoritma yang baik pada struktur data yang tidak dapat diubah, jadi mendandani struktur data yang tidak dapat diubah sebagai yang bisa berubah (atau sebaliknya) mengundang algoritma yang buruk.

Sementara daftar persisten memiliki beberapa kelemahan (tidak ada penambahan yang efisien), ini tidak perlu menjadi masalah serius ketika pemrograman secara fungsional: Banyak algoritma dapat diformulasikan secara efisien dengan menggeser pola pikir dan menggunakan fungsi tingkat tinggi seperti mapatau fold(untuk menyebutkan dua yang relatif primitif). ), atau dengan menuliskan ulang berulang kali. Selain itu, tidak ada yang memaksa Anda untuk hanya menggunakan struktur data ini: Ketika orang lain (sesaat, atau gigih tetapi lebih canggih) lebih tepat, gunakan mereka. Saya juga harus mencatat bahwa daftar persisten memiliki beberapa kelebihan untuk beban kerja lain: Mereka berbagi ekornya, yang dapat menghemat memori.


sumber
4

Jika Anda memiliki daftar yang terhubung sendiri, Anda akan bekerja dengan bagian depan jika lebih dari yang Anda lakukan dengan bagian belakang.

Bahasa fungsional seperti prolog dan haskel menyediakan cara mudah untuk mendapatkan elemen depan dan seluruh array. Menambahkan ke belakang adalah operasi O (n) dengan salinan setiap node.

ratchet freak
sumber
1
Saya telah menggunakan Haskell. Afaik, itu juga menghindari bagian dari masalah dengan menggunakan kemalasan. Saya melakukan menambahkan karena saya pikir itulah yang diharapkan oleh Listantarmuka (saya bisa saja salah di sana). Saya tidak berpikir bahwa sedikit benar-benar menjawab pertanyaan juga. Seluruh daftar masih perlu disalin; itu hanya akan membuat akses ke elemen terakhir ditambahkan lebih cepat karena lintasan penuh tidak diperlukan.
Carcigenicate
Membuat kelas sesuai dengan antarmuka yang tidak cocok dengan struktur data / algoritma yang mendasari adalah undangan untuk rasa sakit dan ketidakefisienan.
ratchet freak
JavaDocs secara eksplisit menggunakan kata "append". Anda mengatakan lebih baik mengabaikannya demi implementasi?
Carcigenicate
2
@Carcigenicate no Saya katakan bahwa ini adalah kesalahan untuk mencoba dan memasukkan daftar yang terhubung sendiri dengan node yang tidak dapat diubah ke dalam cetakanjava.util.List
ratchet freak
1
Dengan kemalasan tidak akan ada lagi daftar tertaut; tidak ada daftar, maka tidak ada mutasi (tambahkan). Sebaliknya ada beberapa kode yang menghasilkan item berikutnya berdasarkan permintaan. Tapi itu tidak bisa digunakan di mana-mana di mana daftar digunakan. Yaitu, jika Anda menulis metode di Jawa yang berharap untuk mengubah daftar yang diteruskan sebagai argumen, daftar itu harus bisa diubah di tempat pertama. Pendekatan generator memerlukan restrukturisasi lengkap (reorganisasi) kode untuk membuatnya bekerja - dan untuk memungkinkan untuk menghilangkan daftar secara fisik.
rwong
4

Seperti yang telah ditunjukkan orang lain, Anda benar bahwa daftar yang terhubung secara tunggal dan tidak dapat diubah mensyaratkan menyalin seluruh daftar ketika melakukan operasi penambahan.

Seringkali Anda dapat menggunakan solusi menerapkan algoritma Anda dalam hal consoperasi (tergantung), dan kemudian membalikkan daftar akhir sekali. Ini masih perlu menyalin daftar sekali, tetapi kompleksitas overhead linear dalam panjang daftar, sedangkan dengan menggunakan append berulang kali Anda dapat dengan mudah mendapatkan kompleksitas kuadratik.

Daftar perbedaan (lihat misalnya di sini ) adalah alternatif yang menarik. Daftar perbedaan membungkus daftar dan menyediakan operasi penambahan dalam waktu yang konstan. Anda pada dasarnya bekerja dengan pembungkus selama Anda perlu menambahkan, dan kemudian mengonversi kembali ke daftar ketika Anda selesai. Ini entah bagaimana mirip dengan apa yang Anda lakukan ketika Anda menggunakan a StringBuilderuntuk membangun string, dan pada akhirnya mendapatkan hasilnya sebagai String(tidak dapat diubah!) Dengan memanggil toString. Satu perbedaan adalah bahwa a StringBuilderbisa berubah, tetapi daftar perbedaan tidak berubah. Juga, ketika Anda mengubah daftar perbedaan kembali ke daftar, Anda masih harus membangun seluruh daftar baru tetapi, sekali lagi, Anda hanya perlu melakukan ini sekali.

Seharusnya cukup mudah untuk mengimplementasikan DListkelas yang tidak berubah yang menyediakan antarmuka yang mirip dengan Haskell Data.DList.

Giorgio
sumber
4

Anda harus menonton video hebat ini dari 2015 React conf oleh Immutable.js , pencipta Lee Byron. Ini akan memberi Anda petunjuk dan struktur untuk memahami bagaimana menerapkan daftar abadi yang efisien yang tidak menggandakan konten. Ide-ide dasar adalah: - selama dua daftar menggunakan node yang identik (nilai yang sama, node berikutnya yang sama), node yang sama digunakan - ketika daftar mulai berbeda, sebuah struktur dibuat pada node divergence, yang memegang pointer ke simpul khusus berikutnya dari setiap daftar

Gambar ini dari tutorial reaksi mungkin lebih jelas daripada bahasa Inggris saya yang rusak:masukkan deskripsi gambar di sini

feydaykyn
sumber
2

Ini bukan sepenuhnya Java, tapi saya sarankan Anda membaca artikel ini pada struktur data persisten yang tidak berubah, tetapi performan diindeks ditulis dalam Scala:

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala

Karena ini adalah struktur data Scala, ini dapat digunakan dari Jawa juga (dengan verbosity sedikit lebih). Ini didasarkan pada struktur data yang tersedia di Clojure, dan saya yakin ada lebih banyak perpustakaan "asli" Jawa yang menawarkannya juga.

Juga, catatan tentang membangun struktur data yang tidak dapat diubah: apa yang biasanya Anda inginkan adalah semacam "Builder", yang memungkinkan Anda untuk "mengubah" struktur data "dalam pembangunan" dengan menambahkan elemen ke dalamnya (dalam satu utas); setelah selesai menambahkan, Anda memanggil metode pada objek "sedang dibangun" seperti .build()atau .result(), yang "membangun" objek, memberi Anda struktur data yang tidak dapat diubah yang kemudian dapat Anda bagikan dengan aman.

Sandro Gržičić
sumber
1
Ada pertanyaan tentang porta Java dari PersistentVector di stackoverflow.com/questions/15997996/…
James_pic
1

Suatu pendekatan yang kadang-kadang bisa membantu adalah memiliki dua kelas objek yang memegang daftar - objek daftar maju dengan finalreferensi ke simpul pertama dalam daftar yang ditautkan ke depan dan non- finalreferensi awalnya-nol yang (ketika tidak -null) mengidentifikasi objek daftar terbalik yang memegang item yang sama dalam urutan yang berlawanan, dan objek daftar terbalik dengan finalreferensi ke item terakhir dari daftar yang ditautkan terbalik dan referensi non-final awalnya-nol yang (ketika tidak -null) mengidentifikasi objek daftar depan yang memegang item yang sama dalam urutan yang berlawanan.

Mem-prapingkan item ke daftar-maju atau menambahkan item ke daftar-balik hanya akan membutuhkan membuat simpul baru yang terhubung ke simpul yang diidentifikasi oleh finalreferensi dan membuat objek daftar baru dengan jenis yang sama seperti aslinya, dengan finalreferensi ke simpul baru itu.

Menambahkan item ke daftar maju atau menambahkan ke daftar terbalik akan membutuhkan daftar jenis yang berlawanan; pertama kali dilakukan dengan daftar tertentu, ia harus membuat objek baru dari tipe yang berlawanan dan menyimpan referensi; mengulangi tindakan harus menggunakan kembali daftar.

Perhatikan bahwa keadaan eksternal objek daftar akan dianggap sama apakah rujukannya ke daftar tipe-lawan adalah nol atau mengidentifikasi daftar urutan-lawan. Tidak perlu membuat variabel apa pun final, bahkan ketika menggunakan kode multi-ulir, karena setiap objek daftar akan memiliki finalreferensi ke salinan lengkap isinya.

Jika kode pada satu utas membuat dan menyimpan salinan yang terbalik dari daftar, dan bidang di mana salinan itu di-cache tidak mudah menguap, mungkin saja kode pada utas lain mungkin tidak melihat daftar yang di-cache, tetapi satu-satunya efek buruk dari situlah thread lain perlu melakukan pekerjaan ekstra membangun salinan daftar yang terbalik. Karena tindakan seperti itu akan paling buruk merusak efisiensi, tetapi tidak akan memengaruhi kebenaran, dan karena volatilevariabel membuat penurunan efisiensi mereka sendiri, sering kali akan lebih baik untuk membuat variabel menjadi tidak mudah menguap dan menerima kemungkinan operasi yang berlebihan sesekali.

supercat
sumber