SortedList를 사용하는 경우

SortedList를 사용하는 경우 SortedDictionary 이상?

---

" SortedList 와 SortedDictionary 의 차이점은 무엇입니까 ?"라고 묻는 이 질문 의 중복으로 보일 수 있습니다. 불행히도 대답은 MSDN 문서를 인용하는 것 (둘 사이에 성능과 메모리 사용 차이가 있음을 명확하게 명시)을 인용하는 것 외에는 없지만 실제로 질문에 대답하지는 않습니다.

실제로 (따라서이 질문은 동일한 답변을 얻지 못합니다) MSDN에 따르면 :

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

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

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

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

따라서 정렬되지 않은 데이터에 대해 더 빠른 삽입 및 제거 작업이 필요 하지 않는 한SortedList<TKey, TValue> 이것이 더 나은 선택 임을 분명히 나타냅니다 .

SortedDictionary<TKey, TValue>? 를 사용하는 실제 (실제, 비즈니스 사례 등) 이유가 무엇인지 위의 정보를 고려할 때 질문은 여전히 ​​남아 있습니다 . 성능 정보에 따르면 실제로는 전혀 가질 필요가 없음을 의미 SortedDictionary<TKey, TValue>합니다.

---

내가 MSDN의 문서에 얼마나 정확하지 확신 SortedList하고 SortedDictionary. 둘 다 이진 검색 트리를 사용하여 구현 된 것 같습니다. 그러나 SortedList가 이진 검색 트리를 사용하는 경우 왜 추가 작업이 더 느릴 SortedDictionary까요?

어쨌든 다음은 성능 테스트 결과입니다.

각 테스트는 10,000 개의 int32 키를 포함 하는 SortedList/에서 작동 SortedDictionary합니다. 각 테스트는 1,000 회 반복됩니다 (빌드 릴리스, 디버깅하지 않고 시작).

첫 번째 테스트 그룹은 0에서 9,999 사이의 순서로 키를 추가합니다. 두 번째 테스트 그룹은 0에서 9,999 사이의 임의 셔플 키를 추가합니다 (모든 숫자가 정확히 한 번 추가됨).

***** Tests.PerformanceTests.SortedTest

SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms


SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms

***** Tests.PerformanceTests.UnsortedTest

SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms


SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms

다른 프로파일 링과 마찬가지로 중요한 것은 실제 수치가 아니라 상대적인 성능입니다.

보시다시피 정렬 된 데이터에서 정렬 된 목록은 SortedDictionary. 정렬되지 않은 데이터에서는 SortedList검색 속도가 약간 더 빠르지 만 추가 속도는 약 9 배 느립니다.

둘 다 내부적으로 이진 트리를 사용하는 경우 정렬되지 않은 데이터에 대한 추가 작업이 SortedList. 정렬 된 목록이 동시에 정렬 된 선형 데이터 구조에 항목을 추가 할 수도 있으므로 속도가 느려질 수 있습니다.

그러나, 당신은의 메모리 사용량이 기대 SortedList동일 또는 동등 이상 또는 적어도 큰 것으로 SortedDictionary. 그러나 이것은 MSDN 문서가 말하는 것과 모순됩니다.

---

나는 MSDN SortedList<TKey, TValue>이 구현을 위해 바이너리 트리를 사용 한다고 말하는 이유를 모르겠습니다. 왜냐하면 디 컴파일러로 코드를 보면 Reflector그것이 사실이 아니라는 것을 깨닫기 때문입니다.

SortedList<TKey, TValue> 단순히 시간이 지남에 따라 증가하는 어레이입니다.

요소를 삽입 할 때마다 먼저 배열에 충분한 용량이 있는지 확인합니다. 그렇지 않은 경우 더 큰 배열이 다시 생성되고 이전 요소가 여기에 복사됩니다 (예 List<T>:)

그런 다음 이진 검색을 사용하여 요소를 삽입 할 위치 를 검색합니다 (배열이 인덱싱 가능하고 이미 정렬되어 있기 때문에 가능합니다).

배열을 정렬 상태로 유지하기 위해 삽입 할 요소 위치 뒤에있는 모든 요소를 ​​한 위치만큼 이동 (또는 푸시)합니다 (사용 Array.Copy()).

예 :

// we want to insert "3" 

2  
4  <= 3
5
8
9
.      
.      
.  

// we have to move some elements first

2
.  <= 3
4 
5  |
8  v
9
.
.

SortedList정렬되지 않은 요소를 삽입 할 때의 성능이 왜 그렇게 나쁜지 설명합니다 . 삽입 할 때마다 일부 요소를 다시 복사해야합니다. 이것이 수행되지 않아야하는 유일한 경우는 요소가 배열의 끝에 삽입되어야하는 경우입니다.

SortedDictionary<TKey, TValue>이진 트리를 사용하여 요소를 삽입하고 검색합니다. 때로는 트리의 균형을 다시 조정해야하기 때문에 삽입시 약간의 비용이 발생합니다 (모든 삽입은 아님).

SortedList또는 SortedDictionary둘 다 이진 검색을 사용하기 때문에 요소를 검색하는 동안 성능이 매우 유사 합니다.

---

In my opinion, you should never use SortedList to just sort an array. Unless you have very few elements, it will always be faster to insert values into a list (or array) and then call Sort() method.

SortedList is mostly useful when you have a list of values already sorted (eg: from database), you want to keep it sorted and perform some operations that would take advantage it is sorted (eg: Contains() method of SortedList performs a binary search instead of linear search)

SortedDictionary offers same advantages than SortedList but performs better if values to insert are not already sorted.

---

EDIT : If you are using .NET Framework 4.5, an alternative to SortedDictionary<TKey, TValue> is SortedSet<T>. It works the same way as SortedDictionary, using a binary tree, but keys and values are the same here.

---

Are they meant for two different purposes?

There is not much semantic difference these two collection types in .NET make. They both offer keyed lookup as well as keep the entries in sort order of keys. In most cases you will be ok with either of them. Perhaps the only differentiator would be the indexed retrieval SortedList permits.

But performance?

However there is a performance difference which might be a stronger factor to choose between them. Here is a tabular view of their asymptotic complexity.

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

Summary

To roughly summarize, you want a SortedList<K, V> when:

1. you require indexed look-up.
2. it's desirable to have lesser memory overhead.
3. your input data is already sorted (say you get it already ordered from db).

You would instead want to prefer a SortedDictionary<K, V> when:

1. relative overall performance matters (with respect to scaling).
2. your input data is unordered.

Writing code

Both SortedList<K, V> and SortedDictionary<K, V> implement IDictionary<K, V>, so in your code you can return IDictionary<K, V> from the method or declare variable as IDictionary<K, V>. Basically hide the implementation detail, and code against interface.

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg. 

In future, its easier to switch from either in case you're not happy with performance characteristic of one collection.

---

For more info on the two collection types see the original question linked.

---

Visual representation of performance differences.

---

That's all there is to it. Retrieval of keys is comparable, but addition is much faster with Dictionaries.

I try to use SortedList as much as possible because it allows me to iterate over the keys and value collections. This is not possible with SortedDictionary as far as I know.

I'm not sure about this, but as far as I know Dictionaries store data in Tree structures, whereas List store data in linear arrays. That explains why insertion and removal is much faster with dictionaries, since less memory has to be shifted around. It also explains why you can iterate over SortedLists but not SortedDictionary.

---

An important consideration for us is the fact that we often have small dictionaries (<100 elements), and current processessors much faster at accessing sequential memory while performing few difficult to predict branches. (i.e. iterating over a linear array rather than traversing a tree) So when you have less than about 60 elements in your dictionary, SortedList<> is often the fastest and most memory efficient dictionary in many use cases.

참고URL : https://stackoverflow.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue