Có sự khác biệt thực tế nào giữa một số SortedList<TKey,TValue>
và SortedDictionary<TKey,TValue>
không? Có bất kỳ hoàn cảnh nào mà bạn sẽ sử dụng một cách cụ thể và không phải là trường hợp khác không?Sự khác nhau giữa SortedList và SortedDictionary là gì?
Trả lời
Có - đặc điểm hiệu suất của chúng khác nhau đáng kể. Nó có lẽ sẽ tốt hơn nếu gọi chúng là SortedList
và SortedTree
vì điều đó phản ánh việc triển khai chặt chẽ hơn.
Xem tài liệu MSDN cho mỗi người trong số họ (SortedList
, SortedDictionary
) để biết chi tiết về hiệu suất cho các hoạt động khác nhau trong các vị trí khác nhau. Dưới đây là một bản tóm tắt thoải mái (từ SortedDictionary
tài liệu):
Các
SortedDictionary<TKey, TValue>
generic lớp là một cây tìm kiếm nhị phân với O (log n) hồi, trong đó n là số của các yếu tố trong từ điển. Trong trường hợp này, nó giống với lớp họcSortedList<TKey, TValue>
generic . Hai lớp có các mô hình đối tượng tương tự và cả hai đều có truy xuất O (log n) . Trong trường hợp hai lớp khác nhau được sử dụng bộ nhớ và tốc độ của chèn và loại bỏ:
SortedList<TKey, TValue>
sử dụng ít bộ nhớ hơnSortedDictionary<TKey, TValue>
.
SortedDictionary<TKey, TValue>
có chèn nhanh hơn và loại bỏ hoạt động cho dữ liệu không được phân loại, O (log n) như trái ngược với O (n) choSortedList<TKey, TValue>
.Nếu danh sách được điền tất cả cùng một lúc từ dữ liệu được sắp xếp,
SortedList<TKey, TValue>
nhanh hơnSortedDictionary<TKey, TValue>
.
(SortedList
thực sự duy trì một mảng được sắp xếp, thay vì sử dụng một cây Nó vẫn sử dụng tìm kiếm nhị phân để tìm các yếu tố..)
Cảm ơn v nhiều cho tất cả các con trỏ. Tôi đoán tôi chỉ là quá lười biếng để RTFM ... dễ dàng hơn nhiều để yêu cầu những người tốt đẹp trên SO ...;) Tôi đã bình chọn cho bạn cả hai cho câu trả lời; Jon được trả lời tín dụng cho lần đầu tiên trên kích hoạt. :) –
Tôi nghĩ định nghĩa SortedList nên được sửa vì tôi không tin đó là cây tìm kiếm nhị phân ...? – nchaud
Tôi đã sử dụng phản xạ và thấy rằng nó không sử dụng cây tìm kiếm nhị phân. –
Kiểm tra các MSDN page for SortedList:
Từ phần chú thích:
Lớp chung là một cây tìm kiếm nhị phân với
O(log n)
truy xuất, trong đón
là số phần tử trong từ điển. Trong trường hợp này, nó giống với lớp chung củaSortedDictionary<(Of <(TKey, TValue>)>)
. Hai lớp này có các mô hình đối tượng tương tự nhau và cả hai đều có truy xuấtO(log n)
. Trường hợp hai lớp khác nhau là sử dụng bộ nhớ và tốc độ chèn và loại bỏ:
SortedList<(Of <(TKey, TValue>)>)
sử dụng ít bộ nhớ hơnSortedDictionary<(Of <(TKey, TValue>)>)
.
SortedDictionary<(Of <(TKey, TValue>)>)
có thao tác chèn và xóa nhanh hơn cho dữ liệu chưa phân loại,O(log n)
thay vìO(n)
choSortedList<(Of <(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<(Of <(TKey, TValue>)>)
nhanh hơnSortedDictionary<(Of <(TKey, TValue>)>)
.
Văn bản được trích dẫn sai (và được cập nhật trên MSDN): SortedList không phải là "cây tìm kiếm nhị phân", nó là "mảng các cặp khóa/giá trị". –
tôi nứt Reflector mở để có một cái nhìn lúc này như có vẻ là một chút nhầm lẫn về SortedList
. Trên thực tế không phải là cây tìm kiếm nhị phân, nó là một mảng được sắp xếp (bằng khóa) của các cặp khóa-giá trị. Cũng có biến số TKey[] keys
được sắp xếp đồng bộ với cặp khóa-giá trị và được sử dụng để tìm kiếm nhị phân.
Đây là một số nguồn (nhắm mục tiêu .NET 4.5) để sao lưu các xác nhận quyền sở hữu của tôi.
thành viên cá nhân
// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;
SortedList.ctor (IDictionary, IComparer)
public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
if (dictionary == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
}
dictionary.Keys.CopyTo(this.keys, 0);
dictionary.Values.CopyTo(this.values, 0);
Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
this._size = dictionary.Count;
}
SortedList.Add (TKey, TValue): void
public void Add(TKey key, TValue value)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
if (num >= 0)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
this.Insert(~num, key, value);
}
SortedList.RemoveAt (int): void
public void RemoveAt(int index)
{
if ((index < 0) || (index >= this._size))
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
}
this._size--;
if (index < this._size)
{
Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
Array.Copy(this.values, index + 1, this.values, index, this._size - index);
}
this.keys[this._size] = default(TKey);
this.values[this._size] = default(TValue);
this.version++;
}
Dưới đây là một cái nhìn bảng nếu nó giúp ...
Từ một hiệu suất quan điểm:
+------------------+---------+----------+--------+----------+----------+---------+
| Collection | Indexed | Keyed | Value | Addition | Removal | Memory |
| | lookup | lookup | lookup | | | |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList | O(1) | O(log n) | O(n) | O(n)* | O(n) | Lesser |
| SortedDictionary | n/a | O(log n) | O(n) | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+
* Insertion is O(1) for data that are already in sort order, so that each
element is added to the end of the list (assuming no resize is required).
Từ một triển khai phối cảnh:
+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup | Ordering | Contiguous | Data | Exposes Key & |
| structure | strategy | | storage | access | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays | Binary search | Sorted | Yes | Key, Index | Yes |
| BST | Binary search | Sorted | No | Key | Yes |
+------------+---------------+----------+------------+------------+------------------+
Để khoảng diễn giải, nếu bạn yêu cầu hiệu suất thô SortedDictionary
có thể là lựa chọn tốt hơn. Nếu bạn yêu cầu chi phí bộ nhớ thấp hơn và truy xuất được lập chỉ mục SortedList
phù hợp hơn. See this question for more on when to use which.
Lưu ý rằng nếu bạn muốn hiệu suất tốt ** và ** sử dụng bộ nhớ tương đối thấp ** và ** truy xuất được lập chỉ mục, hãy xem xét ['BDictionary
@Qwertie có sẵn điểm chuẩn hiệu suất không? – nawfal
Có, hãy xem phần dưới cùng của [bài viết này] (http://core.loyc.net/collections/alists-part3.html). Nó chỉ ra 'BDictionary' thường chậm hơn' SortedDictionary' ngoại trừ kích thước rất lớn, nhưng nó nhanh hơn 'SortedList' nếu có hơn 700 mục hoặc hơn. Việc sử dụng bộ nhớ chỉ cao hơn một chút so với 'SortedList' (thấp hơn nhiều so với' SortedDictionary'), do việc sử dụng các mảng trong lá của cây. – Qwertie
Đây là cách trình bày trực quan về cách biểu diễn so sánh với nhau.
Truy cập chỉ mục (được đề cập ở đây) là sự khác biệt thực tế. Nếu bạn cần truy cập người kế nhiệm hoặc người tiền nhiệm, bạn cần SortedList. SortedDictionary không thể làm điều đó vì vậy bạn đang khá hạn chế với cách bạn có thể sử dụng phân loại (đầu tiên/foreach).
Đủ đã được nói về chủ đề, tuy nhiên để đơn giản, đây là của tôi.
Sắp xếp từ điển nên được sử dụng bất kỳ khi
- More chèn và xóa các hoạt động được yêu cầu.
- Dữ liệu chưa được đặt hàng.
- Quyền truy cập chính là đủ và không cần truy cập chỉ mục.
- Bộ nhớ không phải là nút cổ chai.
Ở phía bên kia, Sắp xếp Danh sách nên được sử dụng bất kỳ khi
- More tra cứu và chèn ít hơn và xóa các hoạt động được yêu cầu.
- Dữ liệu đã được sắp xếp (nếu không phải là tất cả, hầu hết).
- Quyền truy cập chỉ mục là bắt buộc.
- Bộ nhớ là chi phí.
Hy vọng điều này sẽ giúp ích !!
- 1. SortedList <>, SortedDictionary <> và Dictionary <>
- 2. SortedList so với SortedDictionary vs. Sort()
- 3. Sự khác nhau giữa WPF và WinForms là gì?
- 4. Sự khác nhau giữa JavaScript và Java là gì?
- 5. Sự khác nhau giữa ODBC và OleDB là gì?
- 6. Sự khác nhau giữa SGML và XML là gì?
- 7. Sự khác nhau giữa DefaultSelenium và RemoteWebDriver là gì?
- 8. Sự khác nhau giữa RMI và Corba là gì?
- 9. Sự khác nhau giữa scgi và wsgi là gì?
- 10. Sự khác nhau giữa wsHttpBinding và ws2007HttpBinding là gì?
- 11. Sự khác nhau giữa Pingback và Trackback là gì?
- 12. Trong Python, sự khác nhau giữa ".append()" và "+ = []" là gì?
- 13. Sự khác nhau giữa AxInterop và Interop là gì?
- 14. Sự khác nhau giữa CellClick và CellMouseClick là gì?
- 15. Sự khác nhau giữa .bashrc, .bash_profile và .environment là gì?
- 16. Sự khác nhau giữa JSP và Facelets là gì?
- 17. Sự khác nhau giữa hg quên và hg là gì?
- 18. Sự khác nhau giữa GDI và GDI + là gì?
- 19. Sự khác nhau giữa đá quý và plugin là gì?
- 20. Sự khác nhau giữa metaClass.methods và metaClass.metaMethods là gì?
- 21. Sự khác nhau giữa kEND và $ end là gì?
- 22. Sự khác nhau giữa java và jsp là gì?
- 23. Sự khác nhau giữa Application.Run() và Form.ShowDialog() là gì?
- 24. Sự khác nhau giữa -0 và 0 là gì?
- 25. Sự khác nhau giữa HTTP 1.0 và 1.1 là gì?
- 26. Sự khác nhau giữa java.lang.Math và java.lang.StrictMath là gì?
- 27. Sự khác nhau giữa " " và "" là gì?
- 28. Sự khác nhau giữa Spring BeanFactoryAware và ApplicationContextAware là gì?
- 29. sự khác nhau giữa SCRIPT_FILENAME và SCRIPT_NAME là gì?
- 30. Sự khác nhau giữa JSP và JSTL là gì?
Liên quan: [Khi sử dụng SortedList hoặc SortedDictionary] (http://stackoverflow.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue) – Liam
I bối rối. Tại sao SortedList có hai tham số kiểu 'SortedList' thay vì một 'SortedList '? Tại sao nó không thực hiện 'IList '? –
@ColonelPanic bởi vì chức năng SortedList là một bản đồ, không phải là một bộ sưu tập tuyến tính. Đừng để tên đánh lừa bạn. Cũng giống như một cuốn từ điển, bạn chuyển vào một khóa, bạn sẽ nhận được một giá trị. Trong khi từ điển không có thứ tự, SortedList được sắp xếp theo thứ tự sắp xếp tự nhiên của nó. – nawfal