SortedList vs. SortedDictionary vs. Sort()

Question

이것은 this one과 같은 질문의 연속입니다.

성능을 조정하는 지침이 있습니까? 빅 -O의 이익을 의미하는 것이 아니라 선형 시간을 절약하는 것입니다.

예를 들어, 사전 정렬은 SortedList 또는 SortedDictionary 중 하나에 저장합니까?

나는 정렬 할 3 가지 속성을 가진 person-class가있다. 그 중 하나는 몇 년 동안의 나이이다. 나는 나이에 물체를 버킷해야합니까?

먼저 하나의 속성을 정렬해야합니까? 그런 다음 결과 목록/사전을 사용하여 두 속성을 정렬해야합니까?

마음에 드는 다른 최적화가 있습니까?

Answer 1

글쎄, 그것은 SortedList에서 쉽게이기는거야. 항목을 삽입하려면 삽입 지점을 찾으려면 이진 검색 (O (log (n))이 필요하고 항목을 삽입하려면 List.Insert (O (n))가 필요합니다.^2). 입력 항목이 이미 정렬 된 경우 Insert는 O (1)로 축소되지만 검색에는 영향을 미치지 않습니다. 이제 채우기가 O (nlog (n))입니다. 오,

SortedDictionary가 다르고 red-black 트리가 사용됩니다. 삽입 지점을 찾는 데는 O (log (n))가 필요합니다. 트리의 재조정은 다음과 같은 경우 일 수 있습니다. 이후에 필요합니다 또한 O (log (n)) 걸립니다. 사전 채우기 O (nlog (n)) 걸립니다. 정렬 된 입력을 사용하여 삽입 지점을 찾으려면 노력을 변경하지 않거나 균형을 조정, 여전히 O (nlog n)). 이제는 오 중요하지만, 정렬 된 입력을 삽입하면 트리가 consta에 있어야합니다. NT 균형 조정 자체. 입력이 무작위 인 경우 잘 작동하며 정렬 된 입력을 원하지 않습니다.

SortedList를 정렬 된 입력으로 채우고 SortedDictionary를 정렬되지 않은 입력으로 채우는 것은 모두 O (nlog (n))입니다. 정렬 된 입력을 제공하는 비용을 무시하면 SortedList의 아는 SortedDictionary의 아보다 작습니다. 이것은 List가 메모리를 할당하는 방식 때문에 구현 세부 사항입니다. 그것은 오직 O (log (n)) 시간을해야하고, red-black tree는 O (n) 번을 할당해야합니다. 아주 작은 오.

주목할만한 점은 어느 누구도 List를 채우고 Sort()를 호출하는 것보다 유리하다는 점입니다. 그것도 O (nlog (n))입니다. 사실 입력이 실수로 정렬 된 경우 Sort() 호출을 무시할 수 있습니다.이 경우 O (n)로 축소됩니다. 이제 비용 분석은 입력을 정렬하기 위해 필요한 노력으로 이동해야합니다. Sort(), O (nlog (n))의 근본적인 복잡성을 우회하기는 어렵습니다. 쉽게 볼 수 없을 수도 있습니다. 예를 들어 SQL 쿼리로 입력을 정렬 할 수 있습니다. 완료하는 데 시간이 오래 걸립니다.

SortedList 또는 SortedDictonary를 사용하는 이유는 삽입 후에 정렬을 유지하기 위해서입니다. 채우는 것에 대해서만 염려하지만 돌연변이가 없다면 그 컬렉션을 사용해서는 안됩니다.