Saya menemukan itu SortedList<TKey, TValue> SortedDictionary<TKey, TValue>danDictionary<TKey, TValue> menerapkan antarmuka yang sama.

1. Kapan kita harus memilih SortedListdan SortedDictionarykembaliDictionary ?
2. Apa perbedaan antara SortedListdan SortedDictionarydalam hal penerapan?

1. Saat melakukan iterasi terhadap elemen di salah satu dari keduanya, elemen akan diurutkan. Tidak demikian halnya dengan Dictionary<T,V>.

2. MSDN membahas perbedaan antara SortedList<T,V>dan SortedDictionary<T,V>:

Kelas generik SortedDictionary (TKey, TValue) adalah pohon pencarian biner dengan pengambilan O (log n), di mana n adalah jumlah elemen dalam kamus. Dalam hal ini, ini mirip dengan kelas generik SortedList (TKey, TValue). Kedua kelas memiliki model objek yang serupa, dan keduanya memiliki pengambilan O (log n). Di mana kedua kelas berbeda dalam penggunaan memori dan kecepatan penyisipan dan penghapusan:

SortedList (TKey, TValue) menggunakan lebih sedikit memori daripada SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) memiliki operasi penyisipan dan penghapusan yang lebih cepat untuk data yang tidak diurutkan: O (log n) dibandingkan dengan O (n) untuk SortedList (TKey, TValue).

Jika daftar diisi sekaligus dari data yang diurutkan, SortedList (TKey, TValue) lebih cepat daripada SortedDictionary (TKey, TValue).

Saya akan menyebutkan perbedaan antar kamus.

Gambar di atas menunjukkan itu Dictionary<K,V> dalam setiap kasus sama atau lebih cepat daripada Sortedanalog, tetapi jika urutan elemen diperlukan, misalnya untuk mencetaknya,Sorted dipilih satu.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Untuk meringkas hasil Tes Performa - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable , hasil dari yang terbaik hingga terburuk untuk skenario yang berbeda:

Penggunaan Memori:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Sisipan:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Operasi Pencarian:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

untuk setiap operasi loop

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

Saya dapat melihat jawaban yang diajukan berfokus pada kinerja. Artikel yang diberikan di bawah ini tidak memberikan informasi baru tentang kinerja, tetapi menjelaskan mekanisme yang mendasarinya. Juga perhatikan itu tidak fokus pada tiga CollectionJenis yang disebutkan dalam pertanyaan, tetapi membahas semua Jenis System.Collections.Genericnamespace.

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Ekstrak:

Kamus <>

Dictionary mungkin adalah class container asosiatif yang paling banyak digunakan. Kamus adalah kelas tercepat untuk pencarian / penyisipan / penghapusan asosiatif karena menggunakan tabel hash di bawah sampulnya . Karena kunci di-hash, jenis kunci harus menerapkan GetHashCode () dan Equals () dengan benar atau Anda harus menyediakan IEqualityComparer eksternal ke kamus tentang konstruksi. Waktu penyisipan / penghapusan / pencarian item dalam kamus diamortisasi waktu konstan - O (1) - yang berarti tidak peduli seberapa besar kamus, waktu yang diperlukan untuk menemukan sesuatu tetap relatif konstan. Ini sangat diinginkan untuk pencarian kecepatan tinggi. Satu-satunya downside adalah bahwa kamus, secara alami menggunakan tabel hash, tidak berurutan, jadiAnda tidak dapat dengan mudah menelusuri item dalam Kamus secara berurutan .

SortedDictionary <>

SortedDictionary mirip dengan Dictionary dalam penggunaan tetapi sangat berbeda dalam implementasinya. The SortedDictionary menggunakan pohon biner di bawah selimut untuk menjaga barang-barang dalam rangka oleh kunci . Sebagai konsekuensi dari pengurutan, tipe yang digunakan untuk kunci harus mengimplementasikan IComparable dengan benar sehingga kunci dapat diurutkan dengan benar. Kamus yang diurutkan memperdagangkan sedikit waktu pencarian untuk kemampuan mempertahankan item secara berurutan, sehingga waktu penyisipan / penghapusan / pencarian dalam kamus yang diurutkan adalah logaritmik - O (log n). Secara umum, dengan waktu logaritmik, Anda dapat menggandakan ukuran koleksi dan hanya perlu melakukan satu perbandingan ekstra untuk menemukan itemnya. Gunakan SortedDictionary jika Anda ingin pencarian cepat, tetapi juga ingin dapat menjaga koleksi agar sesuai dengan kuncinya.

SortedList <>

SortedList adalah kelas wadah asosiatif yang diurutkan lainnya dalam wadah generik. Sekali lagi SortedList, seperti SortedDictionary, menggunakan kunci untuk mengurutkan pasangan kunci-nilai . Tidak seperti SortedDictionary, item dalam SortedList disimpan sebagai larik item yang diurutkan. Ini berarti bahwa penyisipan dan penghapusan bersifat linier - O (n) - karena menghapus atau menambah item mungkin melibatkan pengalihan semua item ke atas atau ke bawah dalam daftar. Namun, waktu pencarian adalah O (log n) karena SortedList dapat menggunakan pencarian biner untuk menemukan item apa pun dalam daftar dengan kuncinya. Jadi, mengapa Anda ingin melakukan ini? Nah, jawabannya adalah jika Anda akan memuat SortedList di muka, penyisipan akan lebih lambat, tetapi karena pengindeksan array lebih cepat daripada mengikuti tautan objek, pencarian sedikit lebih cepat daripada SortedDictionary. Sekali lagi saya akan menggunakan ini dalam situasi di mana Anda ingin pencarian cepat dan ingin mempertahankan koleksi dalam urutan berdasarkan kunci, dan di mana penyisipan dan penghapusan jarang terjadi.

Ringkasan tentatif dari Prosedur yang mendasari

Umpan balik sangat kami terima karena saya yakin saya tidak melakukan semuanya dengan benar.

• Semua array berukuran n.
• Array yang tidak diurutkan = .Add / .Remove adalah O (1), tetapi .Item (i) adalah O (n).
• Array yang diurutkan = .Add / .Remove adalah O (n), tetapi .Item (i) adalah O (log n).

Kamus

Penyimpanan

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Menambahkan

1. Tambahkan HashArray(n) = Key.GetHash# O (1)
2. Tambahkan KeyArray(n) = PointerToKey# O (1)
3. Tambahkan ItemArray(n) = PointerToItem# O (1)

Menghapus

1. For i = 0 to n, temukan di imana HashArray(i) = Key.GetHash # O (log n) (array terurut)
2. Hapus HashArray(i)# O (n) (array diurutkan)
3. Hapus KeyArray(i)# O (1)
4. Hapus ItemArray(i)# O (1)

Dapatkan Item

1. For i = 0 to n, temukan di imana HashArray(i) = Key.GetHash# O (log n) (array terurut)
2. Kembali ItemArray(i)

Loop Through

1. For i = 0 to n, kembali ItemArray(i)

SortedDictionary

Penyimpanan

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

Menambahkan

1. Tambahkan KeyArray(n) = PointerToKey# O (1)
2. Menambahkan ItemArray(n) = PointerToItem# O (1)
3. For i = 0 to n, temukan di imanaKeyArray(i-1) < Key < KeyArray(i) (menggunakan ICompare) # O (n)
4. Menambahkan OrderArray(i) = n # O (n) (array diurutkan)

Menghapus

1. For i = 0 to n, Temukan i mana KeyArray(i).GetHash = Key.GetHash# O (n)
2. Menghapus KeyArray(SortArray(i))# O (n)
3. Menghapus ItemArray(SortArray(i))# O (n)
4. Menghapus OrderArray(i)# O (n) (array diurutkan)

Dapatkan Item

1. For i = 0 to n, Temukan i mana KeyArray(i).GetHash = Key.GetHash# O (n)
2. Kembali ItemArray(i)

Loop Through

1. For i = 0 to n, kembali ItemArray(OrderArray(i))

SortedList

Penyimpanan

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Menambahkan

1. For i = 0 to n, temukan di imanaKeyArray(i-1) < Key < KeyArray(i) (menggunakan ICompare) # O (log n)
2. Menambahkan KeyArray(i) = PointerToKey # O (n)
3. Menambahkan ItemArray(i) = PointerToItem # O (n)

Menghapus

1. For i = 0 to n, Temukan i mana KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Menghapus KeyArray(i)# O (n)
3. Hapus ItemArray(i)# O (n)

Dapatkan Item

1. For i = 0 to n, temukan di imanaKeyArray(i).GetHash = Key.GetHash# O (log n)
2. Kembali ItemArray(i)

Loop Through

1. For i = 0 to n, kembali ItemArray(i)

1. Saat Anda ingin koleksi diurutkan berdasarkan kunci saat Anda mengulanginya. Jika Anda tidak membutuhkan data Anda untuk disortir, Anda lebih baik hanya dengan Dictionary, itu akan memiliki kinerja yang lebih baik.

2. SortedList dan SortedDictionary melakukan hal yang sama, tetapi diterapkan secara berbeda, sehingga memiliki kekuatan dan kelemahan berbeda yang dijelaskan di sini .

Mencoba memberikan skor kinerja untuk setiap kasus yang disajikan oleh @Lev, saya menggunakan nilai-nilai berikut:

• O (1) = 3
• O (log n) = 2
• O (n) = 1
• O (1) atau O (n) = 2
• O (log n) atau O (n) = 1,5

Hasilnya (lebih tinggi = lebih baik):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Tentu saja, setiap kasus penggunaan akan memberi bobot lebih pada operasi tertentu.