정렬 목록과 정렬된 사전의 차이점은 무엇입니까?
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++;
}
이 주제에 대해서는 이미 충분히 언급되었지만, 간단히 말하자면, 제 생각은 이렇습니다.
정렬된 사전은 다음과 같은 경우에 사용해야 합니다.
- 추가 삽입 및 삭제 작업이 필요합니다.
- 데이터가 정렬되지 않았습니다.
- 키 액세스로 충분하며 인덱스 액세스가 필요하지 않습니다.
- 메모리는 병목 현상이 아닙니다.
반면에, 정렬된 목록은 다음과 같은 경우에 사용되어야 합니다.
- 더 많은 조회와 더 적은 삽입 및 삭제 작업이 필요합니다.
- 데이터가 이미 정렬되어 있습니다(전부는 아닐지라도 대부분).
- 인덱스 액세스가 필요합니다.
- 메모리는 오버헤드입니다.
이것이 도움이 되길 바랍니다!!
비고 섹션에서:
그
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
'programing' 카테고리의 다른 글
이클립스의 모든 파일에서 문자열 바꾸기 (0) | 2023.05.01 |
---|---|
PostgreSQL에서 평균 소수점 2자리로 반올림하는 방법은 무엇입니까? (0) | 2023.05.01 |
HttpContent 사용 방법을 찾을 수 없습니다. (0) | 2023.05.01 |
일반 이전 CLR 개체 대 데이터 전송 개체 (0) | 2023.05.01 |
GIT 리포지토리를 한 서버에서 새 서버로 마이그레이션하는 방법 (0) | 2023.05.01 |