SortedList <>, SortedDictionary <> và Dictionary <>

Question

Tôi thấy rằng SortedList<TKey, TValue>SortedDictionary<TKey, TValue> và Dictionary<TKey, TValue> triển khai cùng một giao diện.

1. Khi nào chúng tôi nên chọn SortedList và SortedDictionary qua Dictionary?
2. Sự khác biệt giữa SortedList và SortedDictionary về mặt đơn đăng ký là gì?

Answer 1

1. Khi lặp qua các phần tử của một trong hai thành phần, các thành phần sẽ được sắp xếp. Không phải như vậy với Dictionary<T,V>.

2. MSDN địa chỉ chênh lệch giữa SortedList<T,V> và SortedDictionary<T,V>:

Các SortedDictionary (TKey, TValue) lớp generic là một binary search tree với O (log n) hồi, trong đó n là số nguyên tố trong từ điển. Về mặt này, nó tương tự như lớp chung SortedList (TKey, TValue). Hai lớp có các mô hình đối tượng tương tự nhau và đều có truy xuất O (log n). Trường hợp hai lớp khác nhau là sử dụng bộ nhớ và tốc độ chèn và xóa:

SortedList (TKey, TValue) sử dụng ít bộ nhớ hơn SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) đã chèn nhanh và xóa hoạt động cho dữ liệu chưa được phân loại: O (log n) trái ngược với O (n) cho SortedList (TKey, TValue).

Nếu danh sách được điền cùng một lúc từ dữ liệu được sắp xếp, SortedList (TKey, TValue) nhanh hơn SortedDictionary (TKey, TValue).

Answer 2

1. Khi bạn muốn tập hợp được sắp xếp theo khóa khi bạn lặp lại khóa đó. Nếu bạn không cần dữ liệu của bạn được sắp xếp, bạn tốt hơn chỉ với một từ điển, nó sẽ có hiệu suất tốt hơn.

2. SortedList và SortedDictionary khá nhiều làm điều tương tự, nhưng được thực hiện khác nhau, do đó có điểm mạnh và điểm yếu khác nhau explained here.

Answer 3

tôi muốn đề cập đến sự khác biệt giữa các từ điển.

Ảnh trên cho thấy rằng Dictionary<K,V> bằng hoặc nhanh hơn trong mọi trường hợp so với Sorted tương tự, nhưng nếu yêu cầu yếu tố, ví dụ: để in chúng, Sorted được chọn.

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

Answer 4

Để tóm tắt các kết quả của một Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, kết quả từ tốt nhất để tồi tệ nhất cho các kịch bản khác nhau:

Memory Usage:

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

Insertions:

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

Operations Tìm kiếm:

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

hoạt động vòng lặp foreach

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