언제 사전 대신 sorteddictionary를 사용해야합니까?

Question

마지막 게시물의 일부에서 필자는 여전히 C# 세계에 새로운 것이므로 Dictionary, Hashtable, SortedList 및 SortedDictionary를 각각 비교하는 작은 벤치 마크를 작성했습니다. 다른. 테스트는 8000 번의 반복과 50에서 100000 개의 요소로 실행됩니다. 필자는 새로운 요소를 추가하고, 요소를 검색하고, 일부 요소를 모두 무작위로 반복하여 테스트했습니다. 그 결과는 나에게 많은 혼란을 안겨주는 SortedDictionary의 결과를 제외하고는 그들이 기대했던대로였습니다 ... 그것은 모든 결과에서 느린 것입니다. 그래서 정렬 된 사전의 개념에 대해 빠뜨린 것 같습니다. 나는 이미 Google에 물었다. 그러나 내가 알아 낸 모든 것은 다른 사람들이 같은 테스트 결과를 얻었습니다. 테스트 구현에 따라 약간 다릅니다. 다시 내 질문 : 왜 SortedDicrionary가 다른 모든 것보다 훨씬 느린가요?

Answer 1

SortedDictionary는 이진 검색 트리로 구현됩니다. 따라서 요소에 액세스하는 것은 O (lg (n))입니다. 사전은 해시 테이블이며 액세스를 위해 O (1)의 복잡성이 있습니다.

SortedDictionary는 데이터 정렬이 필요할 때 매우 유용합니다 (사전에는 정의 된 순서가 없음). 사전은 대부분의 경우에 적합합니다.

Answer 2

대답은 간단히 정렬 된 사전이 필요하면 SortedDictionary을 사용한다는 것입니다.

시험에서 가장 느린 것으로 끝났지 만 느린 것은 아닙니다. SortedDictionary이 정확히 필요한 경우 가장 좋은 솔루션입니다. Dictionary 또는 SortedList을 사용하여 동일하게 수행하는 것은 매우 느립니다.

Answer 3

또 다시 질문 : 왜 SortedDicrionary가 다른 모든 것보다 속도가 더 빠릅니까?

은 에티엔 느 이미 이전에 기술적 인 대답을했다,하지만 더 '일반'발언을 추가 :이 보인다 나는 SortedDictionary의 "정렬 된"비트 부분은 삽입에 약간의 오버 헤드를두고도 검색 항목 추측 것 에티엔의 대답에서.

그러나 실제 앱에서는 SortedDictionary가 앱의 "이미 정렬 된 사전"을 필요로 할 때 상당한 성능 또는 '인식 된 성능'을 제공 할 수 있습니다.

희망이 있습니다.