Sự khác nhau giữa SortedList và SortedDictionary là gì?

Question

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?

Answer 1

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ọc SortedList<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ơn SortedDictionary<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) cho SortedList<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ơn SortedDictionary<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ố..)

Answer 2

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ủa SortedDictionary<(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ấ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à loại bỏ:

• SortedList<(Of <(TKey, TValue>)>) sử dụng ít bộ nhớ hơn SortedDictionary<(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) cho SortedList<(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ơn SortedDictionary<(Of <(TKey, TValue>)>).

Answer 3

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++; 
} 

Answer 4

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.

Bạn có thể đọc thêm here, here, here, here và here.

Answer 5

Đây là cách trình bày trực quan về cách biểu diễn so sánh với nhau.

Answer 6

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

Answer 7

Đủ đã đượ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 !!