SortedList와 SortedDictionary의 차이점은 무엇입니까?

Question

사이에 실제적인 실질적인 차이가 있습니까? SortedList<TKey,TValue> 그리고 SortedDictionary<TKey,TValue>?특별히 하나를 사용하고 다른 하나는 사용하지 않는 상황이 있습니까?

Answer 1

예 - 성능 특성은 크게 다릅니다. 그들을 부르는 것이 더 낫습니다 SortedList 그리고 SortedTree 그것은 구현을보다 밀접하게 반영합니다.

그들 각각에 대한 MSDN 문서를보십시오 (SortedList, SortedDictionary) 다른 situtations에서 다른 작업의 성능에 대한 자세한 내용. 다음은 좋은 요약입니다 ( SortedDictionary 문서) :

그만큼 SortedDictionary<TKey, TValue> 일반 클래스는 O (log n) 검색이있는 이진 검색 트리이며, 여기서 n은 사전의 요소 수입니다. 이것에서 그것은와 유사합니다 SortedList<TKey, TValue> 일반 수업. 두 클래스에는 비슷한 객체 모델이 있으며 둘 다 O (로그 N) 검색이 있습니다. 두 클래스가 다른 경우 메모리 사용 및 삽입 및 제거 속도가 있습니다.

• SortedList<TKey, TValue> 보다 기억이 적습니다 SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> O (n)과 달리 음조되지 않은 데이터에 대한 더 빠른 삽입 및 제거 작업이 있습니다. SortedList<TKey, TValue>.

• 목록이 정렬 된 데이터에서 한 번에 모두 채워진 경우 SortedList<TKey, TValue> 보다 빠릅니다 SortedDictionary<TKey, TValue>.

(SortedList 실제로 트리를 사용하지 않고 정렬 된 배열을 유지합니다. 여전히 이진 검색을 사용하여 요소를 찾습니다.)

Answer 2

도움이되는 경우 표로보기가 있습니다 ...

a 성능 관점:

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

an 구현 관점:

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

에게 대충 원시 성능이 필요한 경우 SortedDictionary 더 나은 선택이 될 수 있습니다. 더 적은 메모리 오버 헤드 및 색인 검색이 필요한 경우 SortedList 더 잘 맞습니다. 언제 사용 해야하는지에 대한 자세한 내용은이 질문을 참조하십시오.

더 읽을 수 있습니다 여기, 여기, 여기, 여기 그리고 여기.

Answer 3

나는 약간의 혼란이있는 것처럼 보이기 때문에 열린 반사판을 깨뜨렸다. SortedList. 실제로 이진 검색 트리가 아니며 키 값 쌍의 정렬 된 (키) 배열입니다.. 또 한있다 TKey[] keys 키 값 쌍과 동기화되고 이진 검색에 사용되는 변수.

다음은 내 주장을 백업하기위한 일부 소스 (Target .NET 4.5)입니다.

개인 회원

// 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 (유명한, 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

확인하십시오 SortedList 용 MSDN 페이지:

비고 섹션에서 :

그만큼 SortedList<(Of <(TKey, TValue>)>) 일반 클래스는 이진 검색 트리입니다 O(log n) 검색, 어디에 n 사전의 요소 수입니다. 이것에서 그것은와 유사합니다 SortedDictionary<(Of <(TKey, TValue>)>) 일반 수업. 두 클래스는 비슷한 객체 모델을 가지고 있으며 둘 다 O(log n) 검색. 두 클래스가 다른 경우 메모리 사용 및 삽입 및 제거 속도가 있습니다.

• SortedList<(Of <(TKey, TValue>)>) 보다 기억이 적습니다 SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>) 분류되지 않은 데이터에 대한 더 빠른 삽입 및 제거 작업이 있습니다. O(log n) 반대로 O(n) ~을 위한 SortedList<(Of <(TKey, TValue>)>).

• 목록이 정렬 된 데이터에서 한 번에 모두 채워진 경우 SortedList<(Of <(TKey, TValue>)>) 보다 빠릅니다 SortedDictionary<(Of <(TKey, TValue>)>).

Answer 5

이것은 성능이 서로 비교되는 방법을 시각적으로 표현합니다.

Answer 6

충분히 주제에 대해 말하지만 단순하게 유지하기 위해 여기에 내 테이크가 있습니다.

정렬 된 사전 언제에 사용해야합니다.

• 더 많은 인서트 및 삭제 작업이 필요합니다.
• 주문되지 않은 데이터.
• 주요 액세스가 충분하고 색인 액세스가 필요하지 않습니다.
• 메모리는 병목 현상이 아닙니다.

반대편에서 정렬 된 목록 언제에 사용해야합니다.

• 더 많은 조회 및 삽입 및 삭제 작업이 필요합니다.
• 데이터는 이미 정렬되어 있습니다 (전부는 아니지만 대부분).
• 인덱스 액세스가 필요합니다.
• 메모리는 오버 헤드입니다.

도움이 되었기를 바랍니다!!

Answer 7

여기에 언급된 인덱스 액세스는 실질적인 차이점입니다.후속 작업이나 이전 작업에 액세스해야 하는 경우 SortedList가 필요합니다.SortedDictionary는 이를 수행할 수 없으므로 정렬(first / foreach)을 사용하는 방법이 상당히 제한됩니다.