Dalam keadaan apa daftar tertaut berguna?

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.

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 ;-).

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

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.

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.

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.

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.

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).

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

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.

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.

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 :)

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.)

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 ".

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:

... 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:

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.

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.