programing

정렬 목록과 정렬된 사전의 차이점은 무엇입니까?

abcjava 2023. 5. 1. 19:48
반응형

정렬 목록과 정렬된 사전의 차이점은 무엇입니까?

a와 a 사이에 실질적인 차이가 있습니까? 특별히 하나를 사용하고 다른 하나를 사용하지 않는 상황이 있습니까?

예 - 성능 특성이 크게 다릅니다.아마도 그들에게 전화하는 것이 더 나을 것입니다.SortedList그리고.SortedTree그것은 구현을 더 가깝게 반영하기 때문입니다.

서로 다른 상황에서 서로 다른 작업에 대한 성능에 대한 자세한 내용은 SortedList각 MSDN 문서(, )를 참조하십시오.여기 좋은 요약이 있습니다.SortedDictionary문서):

SortedDictionary<TKey, TValue>제네릭 클래스는 O(log n) 검색을 사용하는 이진 검색 트리입니다. 여기서 n은 사전의 요소 수입니다.이것은 다음과 유사합니다.SortedList<TKey, TValue>제네릭 클래스두 클래스는 유사한 개체 모델을 가지며 둘 다 O(log n) 검색을 가집니다.두 클래스가 다른 것은 메모리 사용과 삽입 및 제거 속도입니다.

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

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

  • 정렬된 데이터에서 목록이 한 번에 채워지는 경우SortedList<TKey, TValue>보다 빠름SortedDictionary<TKey, TValue>.

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

다음 표는 도움이 될 경우...

성능 측면에서 볼 때:

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | O(n)**  | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

  * Insertion is O(log n) for data that are already in sort order, so that each 
    element is added to the end of the list. If a resize is required, that element
    takes O(n) time, but inserting n elements is still amortized O(n log n).
    list.
** Available through enumeration, e.g. Enumerable.ElementAt.

구현의 관점에서 보면 다음과 같습니다.

+------------+---------------+----------+------------+------------+------------------+
| 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(IDictionary, I 비교기)

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

정렬된 목록.추가(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);
}

정렬된 목록.제거 위치(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++;
}

이 주제에 대해서는 이미 충분히 언급되었지만, 간단히 말하자면, 제 생각은 이렇습니다.

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

  • 추가 삽입 및 삭제 작업이 필요합니다.
  • 데이터가 정렬되지 않았습니다.
  • 키 액세스로 충분하며 인덱스 액세스가 필요하지 않습니다.
  • 메모리는 병목 현상이 아닙니다.

반면에, 정렬된 목록은 다음과 같은 경우에 사용되어야 합니다.

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

이것이 도움이 되길 바랍니다!!

정렬된 목록에 대한 MSDN 페이지를 확인합니다.

비고 섹션에서:

SortedList<(Of <(TKey, TValue>)>)는 일클래다포이함진검트다니색입리는이 있는 이진 입니다.O(log n)서 검색, 치위n사전에 있는 요소 수입니다.이은다유사다니합음과것▁▁to다▁similar니와 비슷합니다.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>)>).

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

인덱스 액세스(여기서 언급됨)는 실질적인 차이입니다.후속 또는 이전 버전에 액세스해야 하는 경우 정렬된 목록이 필요합니다.SortedDictionary는 이 작업을 수행할 수 없으므로 정렬(첫 번째 / 각 정렬)을 사용하는 방법이 상당히 제한됩니다.

언급URL : https://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary

반응형