[c#] SortedList <>, SortedDictionary <> 및 Dictionary <>

Program / 글쓴이

나는 그것을 찾을 수 SortedList<TKey, TValue> SortedDictionary<TKey, TValue>와 Dictionary<TKey, TValue>같은 인터페이스를 구현합니다.

  1. 우리는을 선택해야하는 경우 SortedList와 SortedDictionary이상 Dictionary?
  2. 의 차이 무엇입니까 SortedList및 SortedDictionary응용 프로그램의 측면에서는?

답변

  1. 둘 중 하나의 요소를 반복하면 요소가 정렬됩니다. 그리로 Dictionary<T,V>.

  2. MSDN 은 SortedList<T,V>과 (와) 의 차이점을 해결합니다 SortedDictionary<T,V>.

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

SortedList (TKey, TValue)는 SortedDictionary (TKey, TValue)보다 적은 메모리를 사용합니다.

SortedDictionary (TKey, TValue)는 정렬되지 않은 데이터에 대한 삽입 및 제거 작업이 더 빠릅니다. SortedList (TKey, TValue)의 경우 O (n)이 아닌 O (log n)입니다.

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

답변

여기에 이미지 설명 입력

사전의 차이점을 언급하고 싶습니다.

위의 그림은 아날로그 Dictionary<K,V>보다 모든 경우에 동일하거나 빠르지 Sorted만 인쇄 등 요소의 순서가 필요한 경우 Sorted하나를 선택합니다.

Src : http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

답변

성능 테스트-SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable 의 결과를 요약하면 다양한 시나리오에 대한 최상의 결과에서 최악의 결과까지 다음과 같습니다.

메모리 사용량 :

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

삽입 :

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

검색 작업 :

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

foreach 루프 작업

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

답변

제안 된 답변이 성능에 중점을두고 있음을 알 수 있습니다. 아래에 제공된 문서는 성능과 관련하여 새로운 내용을 제공하지 않지만 기본 메커니즘에 대해 설명합니다. 또한 Collection질문에 언급 된 세 가지 유형 에 초점을 맞추지 않고 System.Collections.Generic네임 스페이스 의 모든 유형을 다룹니다 .

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

추출물 :

사전 <>

사전은 아마도 가장 많이 사용되는 연관 컨테이너 클래스 일 것입니다. Dictionary는 내부적 으로 해시 테이블을 사용 하기 때문에 연관 조회 / 삽입 / 삭제를위한 가장 빠른 클래스입니다 . 키가 해시되기 때문에 키 유형이 GetHashCode () 및 Equals ()를 올바르게 구현 하거나 생성시 사전에 외부 IEqualityComparer를 제공해야합니다. 사전에있는 항목의 삽입 / 삭제 / 조회 시간은 일정 시간 (O (1))으로 상각됩니다. 즉, 사전이 아무리 커도 무언가를 찾는 데 걸리는 시간은 상대적으로 일정하게 유지됩니다. 이것은 고속 조회에 매우 바람직합니다. 유일한 단점 은 해시 테이블 사용의 특성상 사전이 순서가 지정되지 않았기 때문에사전에있는 항목을 순서대로 쉽게 순회 할 수 없습니다 .

SortedDictionary <>

SortedDictionary는 사용법이 Dictionary와 비슷하지만 구현이 매우 다릅니다. SortedDictionary은 키 순서대로 항목을 유지하기 위해 내부적으로 이진 트리를 사용합니다 . 정렬의 결과로 키에 사용되는 형식 은 키가 올바르게 정렬 될 수 있도록 IComparable을 올바르게 구현해야합니다 . 정렬 된 사전은 항목을 순서대로 유지하는 능력을 위해 약간의 조회 시간을 교환하므로 정렬 된 사전의 삽입 / 삭제 / 조회 시간은 로그-O (log n)입니다. 일반적으로 로그 시간을 사용하면 컬렉션 크기를 두 배로 늘릴 수 있으며 항목을 찾기 위해 추가 비교를 한 번만 수행하면됩니다. 빠른 조회를 원하지만 컬렉션을 키별로 순서대로 유지하려면 SortedDictionary를 사용하십시오.

SortedList <>

SortedList는 제네릭 컨테이너의 다른 정렬 된 연관 컨테이너 클래스입니다. 다시 한번 SortedList는 SortedDictionary와 마찬가지로 키를 사용하여 키-값 쌍을 정렬합니다 . 그러나 SortedDictionary와 달리 SortedList의 항목은 정렬 된 항목 배열로 저장됩니다.. 즉, 항목을 삭제하거나 추가하면 목록에서 모든 항목을 위나 아래로 이동할 수 있기 때문에 삽입 및 삭제가 선형 (O (n))입니다. 그러나 조회 시간은 O (log n)입니다. SortedList는 이진 검색을 사용하여 키로 목록의 항목을 찾을 수 있기 때문입니다. 그렇다면 왜 이렇게하고 싶습니까? 음, 정답은 SortedList를 미리로드하려는 경우 삽입 속도가 느리지 만 배열 인덱싱이 다음 개체 링크보다 빠르기 때문에 조회가 SortedDictionary보다 약간 빠릅니다. 다시 한 번 빠른 조회를 원하고 키에 따라 컬렉션을 순서대로 유지하고 삽입 및 삭제가 거의없는 상황에서 이것을 사용합니다.

기본 절차의 임시 요약

내가 모든 것을 올바르게 얻지 못했다고 확신하므로 피드백은 매우 환영합니다.

  • 모든 배열은 크기 n입니다.
  • 정렬되지 않은 배열 = .Add / .Remove는 O (1)이지만 .Item (i)는 O (n)입니다.
  • 정렬 된 배열 = .Add / .Remove는 O (n)이지만 .Item (i)는 O (log n)입니다.

사전

기억

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

더하다

  1. HashArray(n) = Key.GetHash#O (1) 추가
  2. KeyArray(n) = PointerToKey#O (1) 추가
  3. ItemArray(n) = PointerToItem#O (1) 추가

없애다

  1. For i = 0 to n찾을 i곳 HashArray(i) = Key.GetHash # O (로그 N) (정렬 된 배열)
  2. 제거 HashArray(i)# O (n) (정렬 된 배열)
  3. 제거 KeyArray(i)# O (1)
  4. 제거 ItemArray(i)# O (1)

아이템 받기

  1. For i = 0 to n찾을 i곳 HashArray(i) = Key.GetHash# O (로그 N) (정렬 된 배열)
  2. 반환 ItemArray(i)

루프 스루

  1. For i = 0 to n, 반환 ItemArray(i)

SortedDictionary

기억

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

더하다

  1. KeyArray(n) = PointerToKey#O (1) 추가
  2. ItemArray(n) = PointerToItem#O (1) 추가
  3. For i = 0 to n찾을 i곳 KeyArray(i-1) < Key < KeyArray(i)(사용 ICompare) #의 O (N)를
  4. OrderArray(i) = n# O (n) 추가 (정렬 된 배열)

없애다

  1. For i = 0 to n, i위치 KeyArray(i).GetHash = Key.GetHash# O (n)
  2. 제거 KeyArray(SortArray(i))# O (n)
  3. 제거 ItemArray(SortArray(i))# O (n)
  4. 제거 OrderArray(i)# O (n) (정렬 된 배열)

아이템 받기

  1. For i = 0 to n, i위치 KeyArray(i).GetHash = Key.GetHash# O (n)
  2. 반환 ItemArray(i)

루프 스루

  1. For i = 0 to n, 반환 ItemArray(OrderArray(i))

SortedList

기억

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

더하다

  1. For i = 0 to n찾을 i곳 KeyArray(i-1) < Key < KeyArray(i)(사용 ICompare) # O의 (로그 N)를
  2. KeyArray(i) = PointerToKey# O (n) 추가
  3. ItemArray(i) = PointerToItem# O (n) 추가

없애다

  1. For i = 0 to n찾을 i경우 KeyArray(i).GetHash = Key.GetHash#의 O (로그 N)
  2. 제거 KeyArray(i)# O (n)
  3. 제거 ItemArray(i)# O (n)

아이템 받기

  1. For i = 0 to n찾을 i경우 KeyArray(i).GetHash = Key.GetHash#의 O (로그 N)
  2. 반환 ItemArray(i)

루프 스루

  1. For i = 0 to n, 반환 ItemArray(i)

답변

  1. 컬렉션을 반복 할 때 키별로 정렬하려는 경우. 데이터를 정렬 할 필요가없는 경우 사전 만 있으면 더 나은 성능을 얻을 수 있습니다.

  2. SortedList 및 SortedDictionary는 거의 동일한 작업을 수행하지만 구현 방식이 다르므로 여기에 설명 된 서로 다른 강점과 약점이 있습니다 .

답변

@Lev가 제시 한 각 사례에 성능 점수 를 할당하려고 시도 하면서 다음 값을 사용했습니다.

  • O (1) = 3
  • O (log n) = 2
  • O (n) = 1
  • O (1) 또는 O (n) = 2
  • O (log n) 또는 O (n) = 1.5

결과는 다음과 같습니다 (높을수록 좋음).

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

물론 모든 사용 사례는 특정 작업에 더 많은 가중치를 부여합니다.

답변