[C#] SortedList와 SortedDictionary의 차이점은 무엇입니까?

C# / 글쓴이

a SortedList<TKey,TValue>와 a 사이에 실질적인 차이 가 SortedDictionary<TKey,TValue>있습니까? 하나만 사용하고 다른 하나는 사용하지 않는 상황이 있습니까?

답변

예-성능 특성이 크게 다릅니다. 아마도 그들에게 전화하는 것이 좋습니다 것 SortedList그리고 SortedTree그것은 더 밀접하게 구현을 반영한다.

각기 다른 상황에서 다른 작업의 성능에 대한 자세한 내용은 각 MSDN 문서 ( SortedList, SortedDictionary)를 참조하십시오. 다음은 SortedDictionary문서 에서 요약 한 것입니다 .

SortedDictionary<TKey, TValue>제네릭 클래스는 n은 사전에있는 요소의 수입니다 O (로그 n)이 검색과 이진 검색 트리입니다. 이것에서, 그것은 SortedList<TKey, TValue>일반 클래스 와 유사합니다
. 두 클래스는 비슷한 객체 모델을 가지며 둘 다 O (log n) 검색을 갖습니다. 두 클래스가 다른 곳은 메모리 사용과 삽입 및 제거 속도가 다릅니다.

  • SortedList<TKey, TValue>보다 적은 메모리를 사용합니다 SortedDictionary<TKey,
    TValue>    .

  • SortedDictionary<TKey, TValue>에 대해 O (n)과 반대로 정렬되지 않은 데이터에 대해 O (log n)에 대한 빠른 삽입 및 제거 작업이
    SortedList<TKey, TValue>있습니다.

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

( SortedList실제로는 오히려 나무를 사용하는 것보다, 정렬 된 배열을 유지합니다. 그것은 여전히 요소를 찾을 수 이진 검색을 사용합니다.)

답변

도움이된다면 표 형식보기가 있습니다 …

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

에서 구현 관점 :

+------------+---------------+----------+------------+------------+------------------+
| 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더 적합합니다. 언제 사용해야하는지에 대한 자세한 내용은이 질문을 참조하십시오

자세한 내용은 여기 , 여기 , 여기 , 여기 및 여기를 참조하십시오 .

답변

에 대해 약간의 혼동이있는 것처럼 나는 이것을 확인하기 위해 열린 반사판을 깨뜨렸다 SortedList. 실제로는 이진 검색 트리가 아니며 키-값 쌍으로 정렬 된 (키별로) 배열입니다 . TKey[] keys키-값 쌍과 함께 정렬되어 이진 검색에 사용되는 변수 도 있습니다 .

여기 내 주장을 뒷받침하는 소스 (.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 (Iictionary, 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++;
}

답변

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

답변

이것은 성과가 서로 비교되는 방식을 시각적으로 나타낸 것입니다.

답변

이미 주제에 대해 충분히 언급되어 있지만 간단하게 유지하려면 여기를 참조하십시오.

정렬 된 사전 은 다음과 같은 경우에 사용해야합니다.

  • 더 많은 삽입 및 삭제 작업이 필요합니다.
  • 순서가없는 데이터
  • 키 액세스는 충분하며 인덱스 액세스는 필요하지 않습니다.
  • 메모리는 병목 현상이 아닙니다.

반면에 정렬 된 목록 은

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

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

답변

인덱스 액세스 (여기에서 언급)는 실제 차이점입니다. 후임자 또는 전임자에 액세스해야하는 경우 SortedList가 필요합니다. SortedDictionary는 그렇게 할 수 없으므로 정렬을 사용하는 방법 (첫 번째 / foreach)에 상당히 제한적입니다.