Kamus vs Daftar

30

Jadi saya bertemu dengan Dictionary<int, int>hari ini di tempat kerja. Ini tampak aneh bagi saya karena saya mungkin akan menggunakan List<int>saja. Apakah ada perbedaan dan apakah akan ada use case di mana satu struktur lebih disukai daripada yang lain?

ZeroDivide
sumber
1
Apakah perlu ada hubungan antara dua (atau lebih) int yang diberikan? Maka peta (kamus dalam bahasa ini) masuk akal.
Rig
3
Kamus nama membuatnya jelas bagi saya. Ketika Anda perlu mencari sesuatu dengan cepat, Anda menggunakan kamus.
ChaosPandion
2
@ChaosPandion: a List<T>dalam kerangka .NET adalah array akses acak, di mana operasi pencarian biasanya lebih cepat daripada untuk Dictionary<int,T>.
Doc Brown
2
@DocBrown - Hanya dalam kasus agak aneh menggunakan indeks numerik sebagai kuncinya. Pandangan bijaksana lainnya adalah akan lebih cepat saat menggunakan Dictionary<TKey, TValue>.
ChaosPandion
2
@chaos pertanyaan ini adalah tentang kasus aneh itu.
MarkJ

Jawaban:

32

Anda akan menggunakan a Dictionary<int, int>jika indeks Anda memiliki arti khusus selain hanya penempatan posisi.

Contoh langsung yang muncul dalam pikiran adalah menyimpan kolom id dan kolom int dalam database. Misalnya, jika Anda memiliki [person-id]kolom dan [personal-pin]kolom, maka Anda dapat membawanya ke a Dictionary<int, int>. Dengan cara ini pinDict[person-id]memberi Anda PIN, tetapi indeks itu bermakna dan bukan hanya posisi dalam a List<int>.

Tapi sungguh, setiap kali Anda memiliki dua daftar bilangan bulat terkait, ini bisa menjadi struktur data yang sesuai.

Kris Harper
sumber
Jika id orang saya dari kisaran 0, ..., 999, dan saya harus memuat nilai pin pribadi ke dalam memori untuk semua 1000 orang, saya biasanya memilih a List<int>, dan bukan kamus. Lihat jawaban saya di bawah ini.
Doc Brown
3
ya tapi kamus bisa jarang
jk.
@ jk: itulah yang saya coba jelaskan dalam jawaban saya.
Doc Brown
7
Pin pribadi? Kedengarannya agak berlebihan.
Jack
Hm, ketika indeks memiliki "makna khusus", dalam skenario dunia nyata, kemungkinan indeks tidak membentuk rentang yang berdekatan [0, ..., n] (meskipun ini tidak wajib), jadi jawaban ini adalah tidak jelas salah, tetapi tidak tepat. Namun demikian IMHO keputusan tidak boleh didasarkan pada "hal makna khusus" ini, tetapi hanya pada "jangan kunci membangun kira-kira suatu interval [0, ..., n]". Berdasarkan jumlah upvotes, saya kira sebagian besar pembaca melewatkan titik itu.
Doc Brown
28

Pikirkan Listsebagai array dan Dictionarysebagai tabel hash . Anda hanya akan menggunakan Dictionaryjika Anda perlu memetakan (atau mengaitkan) kunci nilai yang bermakna, sedangkan Listhanya peta (atau rekan) yang memposisikan (atau indeks) nilai.

Misalnya, Anda ingin menyimpan hubungan antara usia dan tinggi badan seseorang. Anda dapat menggunakan a Dictionary<int, int>untuk memetakan usia seseorang (an int) hingga tinggi mereka (an int):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

Bukan contoh yang sangat berguna, tetapi intinya adalah Anda tidak akan dapat melakukan ini dengan elegan Listkarena itu perlu menyimpan nilai-nilai ini secara posisi.

Bernard
sumber
7
+1 untuk menyebutkan bahwa suatu Listtransaksi dengan pesanan , di mana suatu Dictionarytransaksi dengan asosiasi . Jika Anda perlu mendapatkan data Anda dalam urutan tertentu setiap kali, atau urutan mereka dalam kaitannya dengan satu sama lain adalah penting, a Listadalah cara untuk pergi. Dictionariescenderung tidak teratur, dan berurusan dengan pemetaan kunci -> hubungan nilai.
KChaloux
2
Terakhir, ketika Anda tahu apa yang Anda cari, tabel hash sekitar O (1) waktu, sedangkan array adalah O (logN) dalam kasus terbaik (diurutkan dan tanpa duplikat) dan O (N) di kasus terburuk.
JensG
1
+1. Sepertinya tidak ada orang lain yang membahas masalah bahwa daftar disusun secara semantik dan dikte adalah pencarian semantik, yang menurut saya sangat mendasar .
Benjamin Hodgson
15

Secara semantik, a Dictionary<int, T>dan List<T>sangat mirip, keduanya adalah wadah akses acak dari kerangka NET. Untuk menggunakan daftar sebagai pengganti kamus, Anda memerlukan nilai khusus dalam jenis Anda T(seperti null) untuk mewakili slot kosong dalam daftar Anda. Jika Tbukan tipe nullable int, Anda bisa menggunakan int?saja, atau jika Anda hanya berharap untuk menyimpan nilai positif, Anda juga bisa menggunakan nilai khusus seperti -1 untuk mewakili slot kosong.

Yang mana yang akan Anda pilih harus bergantung pada kisaran nilai kunci. Jika kunci Anda dalam Dictionary<int, T>berada dalam interval integer, tanpa banyak celah di antara mereka (misalnya, 80 nilai dari [0, ... 100]), maka a List<T>akan lebih sesuai, karena pengaksesan oleh indeks lebih cepat, dan ada lebih sedikit memori dan waktu overhead dibandingkan dengan kamus dalam kasus ini.

Jika nilai kunci Anda adalah 100 intnilai dari rentang seperti [0, ..., 1000000], maka List<T>memori yang diperlukan untuk menyimpan nilai 1000000 T, di mana kamus Anda hanya akan membutuhkan memori dalam urutan besarnya sekitar 100 nilai T, 100 nilai int (ditambah beberapa overhead, dalam kenyataannya mengharapkan sekitar 2 kali memori untuk menyimpan 100 kunci dan nilai-nilai). Jadi dalam kasus terakhir kamus akan lebih sesuai.

Doc Brown
sumber
6
inilah perbedaan penting imho, Kamus <int, int> bisa jarang
jk.
Dalam hal ini, tidak bisakah kita menggunakan Daftar <KeyValuePair <int, int >>? Yang mana yang lebih baik untuk traversal linier?
Deepak Mishra
@DeepakMishra: perbedaan utama di sini adalah, dengan List<KeyValuePair<int,T>>, tidak ada operasi pencarian O (1) yang tersedia. Kedua, elemen-elemen di List<KeyValuePair<int,T>>dapat memiliki urutan tertentu, terlepas dari nilai-nilai kunci mereka. Jika Anda membutuhkan yang terakhir tetapi bukan yang pertama, List<KeyValuePair<int,T>>atau List<Tuple<int,T>>mungkin pilihan yang lebih baik. Jika Anda membutuhkan keduanya, ada juga OrderedDictionary.
Doc Brown
@DocBrown Yang mana yang akan lebih baik untuk linear traversal (yaitu foreach) dan operasi insert, tidak perlu pencarian langsung?
Deepak Mishra
@DeepakMishra: tidak ada yang namanya "umumnya lebih baik" dalam pengembangan perangkat lunak. Lebih baik di sini bisa berarti lebih cepat, lebih baik membaca, lebih sedikit kode untuk mengetik, lebih mudah diperluas untuk persyaratan mendatang. Tetapi secara umum, berhentilah memikirkan hal ini, terapkan yang menyelesaikan masalah Anda dengan benar dan paling sederhana di mata Anda , periksa apakah itu cukup cepat untuk tujuan Anda , dan investasikan lebih banyak pemikiran di dalamnya ketika Anda mengamati kekurangannya.
Doc Brown
6

Bagaimana orang bisa menganggap mereka setara?

Kamus jarang dan memungkinkan penyisipan acak tetapi membuat traversal in-order menjadi masalah, Daftar tidak jarang dan penyisipan tidak berurutan mahal, ia secara inheren menyediakan traversal in-order.

Akan ada beberapa situasi di mana satu tidak secara dramatis lebih unggul daripada yang lain.

Loren Pechtel
sumber
2

Selain itu: Bahasa pemrograman lain merujuk pada tipe struktur data ini sebagai Peta, bukan Kamus.

Jika data Anda secara bermakna dapat didefinisikan sebagai pasangan kunci / nilai, maka Kamus akan memberikan akses yang jauh lebih cepat jika Anda perlu menemukan nilai menggunakan kuncinya.

Misalnya, anggap Anda memiliki daftar Pelanggan. Setiap Pelanggan mencakup perincian seperti nama dan alamat, dan nomor pelanggan yang unik. Misalkan Anda juga memiliki daftar Pesanan yang sedang diproses. Setiap Pesanan akan berisi perincian tentang apa yang sedang dibuat, dan perlu menyertakan nomor pelanggan dari orang yang memesannya.

Ketika pesanan siap dikirim, Anda perlu menemukan alamat tujuan pengirimannya. Jika pelanggan disimpan sebagai Daftar biasa, maka Anda perlu mencari seluruh daftar untuk menemukan pelanggan dengan nomor pelanggan yang tepat. Sebagai gantinya, Anda bisa menyimpan pelanggan dalam Kamus, dengan nomor pelanggan sebagai kuncinya. Kamus sekarang akan memungkinkan Anda menarik pelanggan yang benar dalam satu langkah tanpa pencarian.

Simon B
sumber
1

Kamus menggunakan hashing untuk mencari data. Kamus pertama menghitung nilai hash untuk kunci dan nilai hash ini mengarah ke ember data target. Setelah itu, setiap elemen dalam ember perlu diperiksa untuk kesetaraan. Tetapi sebenarnya daftar akan lebih cepat dari kamus pada pencarian item pertama karena tidak ada pencarian di langkah pertama. Tetapi pada langkah kedua, daftar harus melihat item pertama, dan kemudian item kedua. Jadi setiap langkah pencarian membutuhkan lebih banyak waktu. Semakin besar daftar, semakin lama waktu yang dibutuhkan.

Lebih lanjut tentang .... Kamus Vs dengan contoh.

Walshregal
sumber
-1

Jika kode tersebut menyimpan dua set nilai yang berkorelasi, kelas Kamus menyediakan cara diindeks untuk mencari nilai dengan kunci. Jika hanya ada satu set nilai, tetapi set itu perlu diakses secara acak (mungkin untuk memeriksa keberadaan kunci dalam satu set), dan nilainya unik, sebuah HashSet mungkin kelas set terbaik untuk digunakan.

JoshL
sumber
-3

Ini adalah jawaban yang bagus yang tampaknya menutupi pangkalan.

Pertimbangan lain yang akan saya tawarkan adalah Kamus (dalam C #) lebih kompleks dari perspektif pengkodean. Memiliki kedua daftar dan kamus dalam basis kode yang sama membuat kode Anda lebih sulit untuk dipertahankan karena kedua metode memiliki perbedaan halus dalam cara melakukan operasi dasar seperti mencari dan menyusun data objek. Perspektif saya adalah bahwa kecuali Anda memerlukan kamus untuk alasan tertentu, gunakan daftar.

StephenR
sumber
8
Saya tidak setuju. Kamus / peta adalah struktur data mendasar yang harus akrab dengan setiap insinyur perangkat lunak. Either way: Anda akan membutuhkan alasan yang dapat dibenarkan untuk menggunakan struktur data apa pun; termasuk Daftar.
Steven Evers