Dalam keadaan apa daftar tertaut berguna?

110

Sering kali saya melihat orang mencoba menggunakan daftar tertaut, menurut saya itu pilihan yang buruk (atau sangat buruk). Mungkin akan berguna untuk mengeksplorasi keadaan di mana daftar tertaut adalah atau bukan pilihan struktur data yang baik.

Idealnya, jawaban akan menjelaskan tentang kriteria yang akan digunakan dalam memilih struktur data, dan struktur data mana yang cenderung bekerja paling baik dalam keadaan tertentu.

Sunting: Saya harus mengatakan, saya cukup terkesan tidak hanya dengan jumlahnya, tetapi kualitas jawabannya. Saya hanya dapat menerima satu, tetapi ada dua atau tiga lagi yang harus saya katakan akan layak diterima jika sesuatu yang sedikit lebih baik tidak ada di sana. Hanya beberapa (terutama yang akhirnya saya terima) yang menunjukkan situasi di mana daftar tertaut memberikan keuntungan nyata. Menurut saya, Steve Jessop pantas mendapatkan penghargaan terhormat karena tidak hanya memberikan satu, tetapi tiga jawaban berbeda, yang semuanya menurut saya cukup mengesankan. Tentu saja, meskipun diposting hanya sebagai komentar, bukan jawaban, menurut saya entri blog Neil juga layak dibaca - tidak hanya informatif, tetapi juga cukup menghibur.

Jerry Coffin
sumber
34
Jawaban paragraf kedua Anda membutuhkan waktu sekitar satu semester.
Seva Alekseyev
2
Untuk pendapat saya, lihat punchlet.wordpress.com/2009/12/27/letter-the-fourth . Dan karena ini sepertinya survei, mungkin seharusnya CW.
1
@Neil, bagus, meskipun saya ragu CS Lewis akan menyetujuinya.
Tom
@Neil: Saya kira semacam survei. Sebagian besar ini merupakan upaya untuk melihat apakah ada orang yang dapat memberikan jawaban yang paling tidak dapat saya beli sebagai jawaban yang masuk akal. @Seva: ya, membacanya kembali, saya membuat kalimat terakhir sedikit lebih umum dari yang saya maksudkan semula.
Jerry Coffin
2
Orang-orang @Yar (termasuk saya, saya minta maaf untuk mengatakan) dulu menerapkan daftar tertaut tanpa petunjuk dalam bahasa seperti FORTRAN IV (yang tidak memiliki gagasan tentang petunjuk), seperti halnya pohon. Anda menggunakan array, bukan memori "nyata".

Jawaban:

40

Mereka dapat berguna untuk struktur data bersamaan. (Sekarang ada contoh penggunaan dunia nyata non-konkuren di bawah - yang tidak akan ada jika @Neil tidak menyebut FORTRAN. ;-)

Misalnya, ConcurrentDictionary<TKey, TValue>di .NET 4.0 RC menggunakan daftar tertaut ke item berantai yang memiliki hash ke keranjang yang sama.

Struktur data yang mendasari untuk ConcurrentStack<T>juga merupakan daftar tertaut.

ConcurrentStack<T>adalah salah satu struktur data yang berfungsi sebagai dasar untuk Thread Pool baru , (dengan "antrean" lokal diimplementasikan sebagai tumpukan, pada dasarnya). (Sedang struktur pendukung utama lainnya ConcurrentQueue<T>.)

Thread Pool baru pada gilirannya memberikan dasar untuk penjadwalan kerja dari Task Parallel Library baru .

Jadi mereka pasti bisa berguna - daftar tertaut saat ini berfungsi sebagai salah satu struktur pendukung utama dari setidaknya satu teknologi baru yang hebat.

(Daftar tertaut tunggal membuat pilihan bebas kunci yang menarik - tetapi tidak bebas menunggu - dalam kasus ini, karena operasi utama dapat dilakukan dengan satu CAS (+ percobaan ulang). Dalam lingkungan GC-d modern - seperti Java dan .NET - masalah ABA dapat dengan mudah dihindari. Cukup bungkus item yang Anda tambahkan ke node yang baru dibuat dan jangan gunakan kembali node tersebut - biarkan GC melakukan tugasnya. Halaman tentang masalah ABA juga menyediakan implementasi kunci- free stack - yang benar-benar berfungsi di .Net (& Java) dengan Node (GC-ed) yang menyimpan item.)

Edit : @Neil: sebenarnya, apa yang Anda sebutkan tentang FORTRAN mengingatkan saya bahwa jenis daftar tertaut yang sama dapat ditemukan dalam struktur data yang mungkin paling sering digunakan dan disalahgunakan di .NET: biasa .NET generik Dictionary<TKey, TValue>.

Bukan satu, tetapi banyak daftar tertaut disimpan dalam larik.

  • Ini menghindari melakukan banyak alokasi kecil (de) pada penyisipan / penghapusan.
  • Pemuatan awal tabel hash cukup cepat, karena array diisi secara berurutan (sangat bagus dengan cache CPU).
  • Belum lagi tabel hash yang berantai mahal dalam hal memori - dan "trik" ini memotong "ukuran pointer" menjadi dua pada x64.

Pada dasarnya, banyak daftar tertaut disimpan dalam larik. (satu untuk setiap bucket yang digunakan.) Daftar gratis node yang dapat digunakan kembali "terjalin" di antara mereka (jika ada penghapusan). Sebuah array dialokasikan di awal / saat rehash dan node rantai disimpan di dalamnya. Ada juga penunjuk gratis - indeks ke dalam array - yang mengikuti penghapusan. ;-) Jadi - percaya atau tidak - teknik FORTRAN masih terus berjalan. (... dan tidak di tempat lain, selain di salah satu struktur data .NET yang paling umum digunakan ;-).

Andras Vass
sumber
2
Jika Anda melewatkannya, berikut adalah komentar Neil: "Orang-orang (termasuk saya, maaf untuk mengatakannya) biasa menerapkan daftar tertaut tanpa petunjuk dalam bahasa seperti FORTRAN IV (yang tidak memiliki gagasan tentang petunjuk), seperti halnya pohon . Anda menggunakan array, bukan "memori" yang sebenarnya. "
Andras Vass
Saya harus menambahkan bahwa pendekatan "daftar tertaut dalam larik" dalam kasus Dictionarypenyimpanan secara signifikan lebih banyak di NET: jika tidak setiap node akan memerlukan objek terpisah di heap - dan setiap objek yang dialokasikan di heap memiliki beberapa overhead. ( en.csharp-online.net/Common_Type_System%E2%80%94Object_Layout )
Andras Vass
Juga baik untuk mengetahui bahwa default C ++ std::listtidak aman dalam konteks multithread tanpa kunci.
Mooing Duck
50

Daftar tertaut sangat berguna ketika Anda perlu melakukan banyak penyisipan dan penghapusan, tetapi tidak terlalu banyak mencari, pada daftar yang panjangnya sewenang-wenang (tidak diketahui pada waktu kompilasi).

Memisahkan dan menggabungkan daftar (ditautkan secara dua arah) sangat efisien.

Anda juga dapat menggabungkan daftar tertaut - misalnya struktur pohon dapat diimplementasikan sebagai daftar tertaut "vertikal" (hubungan induk / anak) yang menghubungkan bersama daftar tertaut horizontal (saudara kandung).

Menggunakan daftar berbasis larik untuk tujuan ini memiliki keterbatasan yang parah:

  • Menambahkan item baru berarti array harus dialokasikan kembali (atau Anda harus mengalokasikan lebih banyak ruang daripada yang Anda butuhkan untuk memungkinkan pertumbuhan di masa mendatang dan mengurangi jumlah realokasi)
  • Menghapus item menyisakan ruang yang terbuang atau membutuhkan realokasi
  • memasukkan item di mana saja kecuali akhir melibatkan (kemungkinan realokasi dan) menyalin banyak data ke satu posisi
Jason Williams
sumber
5
Jadi pertanyaannya mengurangi ke, saat melakukan yang perlu Anda lakukan banyak sisipan dan kepindahan di tengah berurutan, tapi tidak terlalu banyak pencarian dalam daftar dengan ordinal? Melintasi daftar tertaut biasanya sama atau lebih mahal daripada menyalin larik, jadi semua yang Anda katakan tentang menghapus dan menyisipkan item dalam larik sama buruknya dengan akses acak dalam daftar. Cache LRU adalah salah satu contoh yang dapat saya pikirkan, Anda perlu banyak menghapus di tengah, tetapi Anda tidak perlu berjalan dalam daftar.
Steve Jessop
2
Menambahkan ke daftar melibatkan alokasi memori untuk setiap elemen yang Anda tambahkan. Ini mungkin melibatkan panggilan sistem yang akan sangat mahal. Menambahkan ke larik hanya membutuhkan pemanggilan seperti itu jika larik harus dikembangkan. Faktanya, dalam kebanyakan bahasa (karena alasan ini) array adalah struktur data yang disukai dan daftar hampir tidak digunakan sama sekali.
1
Asumsikan yang mana? Alokasi itu sangat cepat terbukti - biasanya membutuhkan penambahan ukuran objek ke pointer. Total overhead untuk GC itu rendah? Terakhir kali saya mencoba mengukurnya di aplikasi nyata, poin kuncinya adalah bahwa Java melakukan semua pekerjaan ketika prosesor tidak bekerja, jadi tentu saja itu tidak banyak mempengaruhi kinerja yang terlihat. Dalam benchmark CPU yang sibuk, Java mudah terganggu, dan mendapatkan waktu alokasi kasus terburuk yang sangat buruk. Ini terjadi bertahun-tahun yang lalu, dan pengumpulan sampah dari generasi ke generasi telah sangat mengurangi total biaya GC sejak saat itu.
Steve Jessop
1
@ Steve: Anda salah tentang alokasi yang "sama" antara daftar dan array. Setiap kali Anda perlu mengalokasikan memori untuk daftar, Anda cukup mengalokasikan blok kecil - O (1). Untuk sebuah array Anda harus mengalokasikan blok baru yang cukup besar untuk keseluruhan daftar, dan kemudian menyalin seluruh daftar - O (n). Untuk menyisipkan ke lokasi yang diketahui dalam daftar, Anda memperbarui sejumlah penunjuk tetap - O (1), tetapi untuk menyisipkan ke dalam larik dan menyalin item berikutnya ke atas satu posisi untuk memberi ruang bagi penyisipan - O (n). Oleh karena itu, ada banyak kasus di mana array kurang efisien daripada LL.
Jason Williams
1
@ Jerry: Saya mengerti. Maksud saya adalah bahwa sebagian besar biaya realokasi array tidak mengalokasikan memori , itu adalah kebutuhan untuk menyalin seluruh konten array ke memori baru. Untuk memasukkan ke dalam item 0 dari sebuah larik Anda harus menyalin seluruh isi larik sampai satu posisi di memori. Saya tidak mengatakan array itu buruk; hanya saja ada situasi di mana akses acak tidak diperlukan, dan di mana penyisipan / penghapusan / penautan ulang LL yang benar-benar konstan lebih disukai.
Jason Williams
20

Daftar tertaut sangat fleksibel: Dengan modifikasi satu penunjuk, Anda dapat membuat perubahan besar, di mana operasi yang sama akan sangat tidak efisien dalam daftar larik.

Chris Lercher
sumber
Apakah mungkin untuk memotivasi mengapa menggunakan daftar sama sekali dan bukan set atau peta?
patrik
14

Array adalah struktur data yang biasanya dibandingkan dengan Daftar Berantai.

Biasanya daftar tertaut berguna ketika Anda harus membuat banyak modifikasi pada daftar itu sendiri sementara array bekerja lebih baik daripada daftar pada akses elemen langsung.

Berikut daftar operasi yang dapat dilakukan pada list dan array, dibandingkan dengan biaya operasi relatif (n = list / panjang array):

  • Menambahkan elemen:
    • pada daftar Anda hanya perlu mengalokasikan memori untuk elemen baru dan mengarahkan pointer. O (1)
    • pada array Anda harus merelokasi array. Di)
  • Menghapus sebuah elemen
    • pada daftar Anda hanya mengarahkan penunjuk. O (1).
    • pada array Anda menghabiskan O (n) waktu untuk merelokasi array jika elemen yang akan dihapus bukan elemen pertama atau terakhir dari array; jika tidak, Anda cukup merelokasi penunjuk ke awal larik atau mengurangi panjang larik
  • Mendapatkan elemen dalam posisi yang diketahui:
    • pada daftar Anda harus berjalan daftar dari elemen pertama ke elemen di posisi tertentu. Kasus terburuk: O (n)
    • pada array Anda dapat mengakses elemen dengan segera. O (1)

Ini adalah perbandingan tingkat yang sangat rendah dari dua struktur data populer dan dasar ini dan Anda dapat melihat bahwa daftar berkinerja lebih baik dalam situasi di mana Anda harus melakukan banyak modifikasi pada daftar itu sendiri (menghapus atau menambahkan elemen). Di sisi lain, array berkinerja lebih baik daripada daftar ketika Anda harus mengakses langsung elemen-elemen dari array.

Dari sudut pandang alokasi memori, list lebih baik karena tidak perlu ada semua elemen di samping satu sama lain. Di sisi lain ada overhead (kecil) untuk menyimpan pointer ke elemen berikutnya (atau bahkan ke sebelumnya).

Mengetahui perbedaan ini penting bagi pengembang untuk memilih antara daftar dan array dalam implementasinya.

Perhatikan bahwa ini adalah perbandingan list dan array. Ada solusi bagus untuk masalah yang dilaporkan di sini (misalnya: SkipLists, Dynamic Arrays, dll ...). Dalam jawaban ini saya telah memperhitungkan struktur data dasar yang harus diketahui setiap programmer.

Andrea Zilio
sumber
Ini agak benar untuk implementasi list yang baik dan implementasi array yang buruk. Kebanyakan implementasi array jauh lebih canggih dari yang Anda berikan. Dan saya rasa Anda tidak mengerti betapa mahalnya alokasi memori dinamis.
Jawaban ini tidak seharusnya mencakup program mata kuliah Data Structures University. Ini adalah perbandingan yang ditulis dengan mempertimbangkan daftar dan array Linked, yang diterapkan seperti yang Anda, saya, dan kebanyakan orang ketahui. Array yang berkembang secara geometris, Lewati Daftar, dll ... adalah solusi yang saya tahu, saya gunakan dan saya pelajari tetapi itu akan membutuhkan penjelasan yang lebih dalam dan itu tidak akan sesuai dengan jawaban stackoverflow.
Andrea Zilio
1
"Dari sudut pandang alokasi memori, daftar lebih baik karena tidak perlu memiliki semua elemen di samping satu sama lain." Sebaliknya, kontainer yang bersebelahan lebih baik karena mereka menyimpan elemen di samping satu sama lain. Di komputer modern, lokalitas data adalah raja. Semua yang melompat-lompat dalam memori membunuh kinerja cache Anda, dan mengarah ke program yang memasukkan elemen di lokasi acak (efektif) yang bekerja lebih cepat dengan larik dinamis seperti C ++ std::vectordaripada dengan daftar tertaut seperti C ++ std::list, hanya karena melintasi daftar sangat mahal.
David Stone
@DavidStone Mungkin saya tidak cukup jelas, tetapi dengan kalimat itu saya mengacu pada fakta bahwa Anda tidak perlu memiliki ruang yang berdekatan untuk menyimpan elemen Anda. Khususnya jika Anda ingin menyimpan sesuatu yang tidak terlalu kecil dan Anda memiliki memori terbatas yang tersedia, Anda mungkin tidak memiliki cukup ruang kosong yang berdekatan untuk menyimpan data Anda, tetapi Anda mungkin dapat memasukkan data Anda menggunakan daftar sebagai gantinya (meskipun Anda akan memiliki overhead petunjuk ... baik karena ruang yang mereka ambil dan masalah kinerja yang Anda sebutkan). Saya mungkin harus memperbarui jawaban saya agar lebih jelas.
Andrea Zilio
4

Daftar tertaut tunggal adalah pilihan yang baik untuk daftar gratis di pengalokasi sel atau kumpulan objek:

  1. Anda hanya memerlukan tumpukan, jadi daftar yang ditautkan tunggal sudah cukup.
  2. Semuanya sudah dibagi menjadi beberapa node. Tidak ada overhead alokasi untuk node daftar yang mengganggu, asalkan selnya cukup besar untuk memuat pointer.
  3. Vektor atau deque akan memberlakukan overhead satu penunjuk per blok. Ini penting mengingat saat Anda pertama kali membuat heap, semua sel gratis, jadi ini adalah biaya di muka. Dalam kasus terburuk, ini menggandakan kebutuhan memori per sel.
Steve Jessop
sumber
Baiklah, setuju. Tetapi berapa banyak programmer yang benar-benar membuat hal-hal seperti itu? Kebanyakan hanya mengimplementasikan ulang apa yang diberikan std :: list dll. Dan sebenarnya "mengganggu" biasanya memiliki arti yang sedikit berbeda dari yang Anda berikan - bahwa setiap elemen daftar yang memungkinkan berisi penunjuk yang terpisah dari data.
1
Berapa banyak? Lebih dari 0, kurang dari satu juta ;-) Apakah pertanyaan Jerry "berikan penggunaan yang baik dari daftar", atau "berikan penggunaan yang baik dari daftar yang digunakan setiap pemrogram setiap hari", atau sesuatu di antaranya? Saya tidak tahu nama lain selain "mengganggu" untuk simpul daftar yang terkandung dalam objek yang merupakan elemen daftar - apakah sebagai bagian dari penyatuan (dalam istilah C) atau tidak. Poin 3 hanya berlaku dalam bahasa yang memungkinkan Anda melakukannya - C, C ++, assembler bagus. Jawa buruk.
Steve Jessop
4

Daftar tertaut ganda adalah pilihan yang baik untuk menentukan urutan hashmap yang juga menentukan urutan pada elemen (LinkedHashMap di Java), terutama bila dipesan oleh akses terakhir:

  1. Lebih banyak overhead memori daripada vektor atau deque terkait (2 penunjuk bukan 1), tetapi kinerja penyisipan / penghapusan yang lebih baik.
  2. Tidak ada overhead alokasi, karena Anda tetap memerlukan node untuk entri hash.
  3. Lokalitas referensi bukanlah masalah tambahan dibandingkan dengan vektor atau deque pointer, karena Anda harus menarik setiap objek ke dalam memori dengan cara apa pun.

Tentu, Anda dapat berdebat tentang apakah LRU cache adalah ide yang bagus pada awalnya, dibandingkan dengan sesuatu yang lebih canggih dan dapat disetel, tetapi jika Anda ingin memilikinya, ini adalah implementasi yang cukup baik. Anda tidak ingin melakukan delete-from-middle-and-add-to-the-end pada vektor atau deque pada setiap akses baca, tetapi memindahkan node ke tail biasanya baik-baik saja.

Steve Jessop
sumber
4

Daftar tertaut adalah salah satu pilihan alami ketika Anda tidak dapat mengontrol di mana data Anda disimpan, tetapi Anda masih perlu berpindah dari satu objek ke objek berikutnya.

Misalnya saat mengimplementasikan pelacakan memori di C ++ (pengganti baru / hapus), Anda memerlukan beberapa struktur data kontrol yang melacak petunjuk mana yang telah dibebaskan, yang sepenuhnya perlu Anda implementasikan sendiri. Alternatifnya adalah mencari secara keseluruhan dan menambahkan daftar tertaut ke awal setiap potongan data.

Karena Anda selalu langsung tahu, di mana Anda berada dalam daftar saat delete dipanggil, Anda dapat dengan mudah melepaskan memori di O (1). Juga menambahkan potongan baru yang baru saja malloced ada di O (1). Berjalan dalam daftar sangat jarang diperlukan dalam kasus ini, jadi biaya O (n) tidak menjadi masalah di sini (berjalan di struktur adalah O (n) bagaimanapun juga).

LiKao
sumber
3

Mereka berguna saat Anda membutuhkan push, pop, dan rotate berkecepatan tinggi, dan tidak keberatan dengan pengindeksan O (n).

Ignacio Vazquez-Abrams
sumber
Pernahkah Anda repot mengatur waktu daftar tertaut C ++ dibandingkan dengan (katakanlah) deque?
@ Neil: Tidak bisa mengatakan bahwa saya punya.
Ignacio Vazquez-Abrams
@Neil: jika C ++ sengaja menyabotase kelas daftar tertautnya untuk membuatnya lebih lambat daripada penampung lainnya (yang tidak jauh dari kebenaran), apa hubungannya dengan pertanyaan bahasa-agnostik? Daftar tertaut yang mengganggu masih merupakan daftar tertaut.
Steve Jessop
@Steve C ++ adalah sebuah bahasa. Saya tidak bisa melihat bagaimana itu bisa memiliki kemauan. Jika Anda menyarankan bahwa anggota Komite C ++ entah bagaimana menyabotase daftar tertaut (yang secara logis harus lambat untuk banyak operasi), maka sebutkan orang yang bersalah!
3
Ini sebenarnya bukan sabotase - node daftar eksternal memiliki kelebihannya, tetapi kinerja bukan salah satunya. Namun, pasti semua orang sadar ketika melakukan trade-off dari hal yang sama yang Anda sadari, yaitu cukup sulit untuk menghasilkan manfaat yang baik std::list. Daftar yang mengganggu tidak sesuai dengan filosofi C ++ tentang persyaratan minimum pada elemen penampung.
Steve Jessop
3

Daftar tertaut tunggal adalah implementasi yang jelas dari tipe data "daftar" yang umum dalam bahasa pemrograman fungsional:

  1. Menambahkan ke head itu cepat, (append (list x) (L))dan (append (list y) (L))dapat membagikan hampir semua datanya. Tidak perlu copy-on-write dalam bahasa tanpa menulis. Pemrogram fungsional tahu bagaimana memanfaatkan ini.
  2. Sayangnya, penambahan ke bagian ekor lambat, tetapi begitu juga dengan penerapan lainnya.

Sebagai perbandingan, vektor atau deque biasanya akan lambat untuk ditambahkan di kedua ujungnya, membutuhkan (setidaknya dalam contoh saya dari dua tambahan berbeda) bahwa salinan diambil dari seluruh daftar (vektor), atau blok indeks dan blok data ditambahkan ke (deque). Sebenarnya, mungkin ada sesuatu yang bisa dikatakan di sana untuk deque pada daftar besar yang perlu ditambahkan di bagian ekor karena alasan tertentu, saya tidak cukup mengetahui tentang pemrograman fungsional untuk menilai.

Steve Jessop
sumber
3

Salah satu contoh penggunaan yang baik untuk daftar tertaut adalah di mana elemen daftar sangat besar yaitu. cukup besar sehingga hanya satu atau dua yang dapat masuk ke dalam cache CPU pada saat yang bersamaan. Pada titik ini, keuntungan yang dimiliki oleh kontainer blok yang berdekatan seperti vektor atau array untuk iterasi lebih atau kurang dinihilkan, dan keunggulan kinerja mungkin dimungkinkan jika banyak penyisipan dan penghapusan terjadi secara realtime.

metamorfosis
sumber
2

Dari pengalaman saya, mengimplementasikan sparse-matrices dan fibonacci heaps. Daftar tertaut memberi Anda kontrol lebih terhadap keseluruhan struktur untuk struktur data tersebut. Meskipun saya tidak yakin apakah matriks renggang paling baik diterapkan menggunakan daftar tertaut - mungkin ada cara yang lebih baik, tetapi sangat membantu mempelajari seluk beluk matriks renggang menggunakan daftar tertaut di CS S1 :)

zakishaheen
sumber
1

Ada dua operasi pelengkap yang sederhana O (1) pada daftar dan sangat sulit untuk diterapkan dalam O (1) dalam struktur data lain - menghapus dan menyisipkan elemen dari posisi sembarang, dengan asumsi Anda perlu mempertahankan urutan elemen.

Peta hash jelas dapat melakukan penyisipan dan penghapusan di O (1) tetapi kemudian Anda tidak dapat mengulang elemen secara berurutan.

Mengingat fakta di atas, peta hash dapat digabungkan dengan daftar tertaut untuk membuat cache LRU yang bagus: Peta yang menyimpan sejumlah pasangan nilai-kunci yang tetap dan meletakkan kunci yang paling terakhir diakses untuk memberi ruang bagi yang baru.

Entri dalam peta hash harus memiliki petunjuk ke node daftar tertaut. Saat mengakses peta hash, node daftar tertaut dibatalkan tautannya dari posisinya saat ini dan dipindahkan ke kepala daftar (O (1), yay untuk daftar tertaut!). Ketika ada kebutuhan untuk menghapus elemen yang paling terakhir digunakan, salah satu dari ekor daftar harus dibuang (sekali lagi O (1) dengan asumsi Anda menyimpan penunjuk ke simpul ekor) bersama dengan entri peta hash terkait (jadi backlink dari daftar ke peta hash diperlukan.)

Rafał Dowgird
sumber
1

Pertimbangkan bahwa daftar tertaut mungkin sangat berguna dalam penerapan gaya Desain Berbasis Domain dari sistem yang menyertakan bagian yang saling terkait dengan pengulangan.

Contoh yang muncul di benak Anda mungkin jika Anda akan memodelkan rantai gantung. Jika Anda ingin mengetahui tegangan pada tautan tertentu, antarmuka Anda dapat menyertakan pengambil bobot yang "tampak". Penerapannya akan mencakup tautan yang menanyakan tautan berikutnya untuk bobot yang terlihat, kemudian menambahkan bobotnya sendiri ke hasilnya. Dengan cara ini, keseluruhan panjang hingga ke bawah akan dievaluasi dengan satu panggilan dari klien jaringan.

Menjadi pendukung kode yang membaca seperti bahasa alami, saya suka bagaimana ini akan membiarkan programmer menanyakan tautan berantai berapa berat yang dibawanya. Itu juga menjaga perhatian menghitung anak-anak properti ini dalam batas implementasi tautan, menghilangkan kebutuhan untuk layanan penghitungan bobot rantai ".

780Farva
sumber
1

Salah satu kasus paling berguna yang saya temukan untuk daftar tertaut yang bekerja di bidang kinerja-kritis seperti pemrosesan mesh dan gambar, mesin fisika, dan raytracing adalah saat menggunakan daftar tertaut benar-benar meningkatkan lokalitas referensi dan mengurangi alokasi heap dan terkadang bahkan mengurangi penggunaan memori dibandingkan dengan alternatif langsung.

Sekarang itu bisa tampak seperti oxymoron lengkap bahwa daftar tertaut dapat melakukan semua itu karena mereka terkenal sering melakukan yang sebaliknya, tetapi mereka memiliki properti unik di mana setiap node daftar memiliki ukuran tetap dan persyaratan penyelarasan yang dapat kita manfaatkan untuk mengizinkan mereka untuk disimpan secara berdekatan dan dihapus dalam waktu konstan dengan cara yang tidak dapat dilakukan oleh hal-hal berukuran variabel.

Akibatnya, mari kita ambil kasus di mana kita ingin melakukan persamaan analogis dengan menyimpan urutan panjang variabel yang berisi satu juta sub-urutan panjang variabel bersarang. Contoh konkretnya adalah jaring terindeks yang menyimpan sejuta poligon (beberapa segitiga, beberapa paha depan, beberapa segi lima, beberapa segi enam, dll) dan kadang-kadang poligon dihapus dari mana saja di jaring dan terkadang poligon dibangun kembali untuk memasukkan simpul ke poligon yang ada atau hapus satu. Dalam hal ini, jika kita menyimpan satu juta kecil std::vectors, maka kita akan menghadapi alokasi heap untuk setiap vektor serta penggunaan memori yang berpotensi meledak. Satu juta orang kecil SmallVectorsmungkin tidak mengalami masalah ini sebanyak dalam kasus umum, tetapi buffer yang telah dialokasikan sebelumnya yang tidak dialokasikan secara terpisah mungkin masih menyebabkan penggunaan memori yang eksplosif.

Masalahnya di sini adalah satu juta std::vectorcontoh akan mencoba menyimpan sejuta benda dengan panjang variabel. Hal-hal dengan panjang variabel cenderung menginginkan alokasi heap karena tidak dapat disimpan secara efektif dan dihapus dalam waktu konstan (setidaknya dengan cara yang langsung tanpa pengalokasi yang sangat kompleks) jika mereka tidak menyimpan kontennya di tempat lain di heap.

Sebaliknya, jika kita melakukan ini:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... maka kami telah secara dramatis mengurangi jumlah alokasi heap dan cache yang hilang. Alih-alih memerlukan alokasi heap dan kemungkinan cache wajib hilang untuk setiap poligon yang kita akses, sekarang kita hanya memerlukan alokasi heap ketika salah satu dari dua vektor yang disimpan di seluruh mesh melebihi kapasitasnya (biaya diamortisasi). Dan sementara langkah untuk berpindah dari satu simpul ke simpul berikutnya mungkin masih menyebabkan bagian cache-nya meleset, itu masih sering kurang dari jika setiap poligon menyimpan larik dinamis yang terpisah karena simpul disimpan secara berdekatan dan ada kemungkinan simpul tetangga mungkin diakses sebelum penggusuran (terutama mengingat banyak poligon akan menambahkan simpulnya sekaligus yang membuat bagian terbesar dari simpul poligon bersebelahan sempurna).

Berikut contoh lainnya:

masukkan deskripsi gambar di sini

... di mana sel grid digunakan untuk mempercepat tumbukan partikel-partikel untuk, katakanlah, 16 juta partikel yang bergerak setiap bingkai. Dalam contoh kisi partikel itu, dengan menggunakan daftar tertaut kita dapat memindahkan partikel dari satu sel kisi ke kisi lainnya hanya dengan mengubah 3 indeks. Menghapus dari vektor dan mendorong kembali ke vektor lain bisa jadi jauh lebih mahal dan memperkenalkan lebih banyak alokasi heap. Daftar tertaut juga mengurangi memori sel hingga 32-bit. Sebuah vektor, bergantung pada implementasinya, dapat mengalokasikan larik dinamisnya ke titik di mana ia membutuhkan 32 byte untuk vektor kosong. Jika kita memiliki sekitar satu juta sel grid, itu sangat berbeda.

... dan di sinilah saya menemukan daftar tertaut yang paling berguna saat ini, dan saya secara khusus menemukan variasi "daftar tertaut yang diindeks" berguna karena indeks 32-bit membagi separuh persyaratan memori dari tautan pada mesin 64-bit dan mereka menyiratkan bahwa node disimpan secara berdekatan dalam sebuah array.

Seringkali saya juga menggabungkannya dengan daftar gratis yang diindeks untuk memungkinkan penghapusan dan penyisipan waktu konstan di mana saja:

masukkan deskripsi gambar di sini

Dalam hal ini, nextindeks menunjuk ke indeks bebas berikutnya jika simpul telah dihapus atau indeks yang digunakan selanjutnya jika simpul belum dihapus.

Dan ini adalah kasus penggunaan nomor satu yang saya temukan untuk daftar tertaut hari ini. Ketika kita ingin menyimpan, katakanlah, satu juta sub-urutan dengan panjang variabel yang rata-rata, katakanlah, masing-masing 4 elemen (tetapi terkadang dengan elemen yang dihapus dan ditambahkan ke salah satu sub-urutan ini), daftar tertaut memungkinkan kita untuk menyimpan 4 juta node daftar tertaut berdekatan alih-alih 1 juta kontainer yang masing-masing dialokasikan heap secara individual: satu vektor raksasa, yaitu, bukan satu juta vektor kecil.

DrunkCoder
sumber
0

Saya telah menggunakan daftar tertaut (bahkan daftar tertaut ganda) di masa lalu dalam aplikasi C / C ++. Ini sebelum .NET dan bahkan stl.

Saya mungkin tidak akan menggunakan daftar tertaut sekarang dalam bahasa .NET karena semua kode traversal yang Anda butuhkan disediakan untuk Anda melalui metode ekstensi Linq.

ChrisF
sumber