구조가 SortedSet보다 빠르므로 끝에 추가 된 항목 수가 적음

Question

List<>을 통해 각 항목에 대해 몇 가지 작업을 수행 한 다음 해당 작업의 결과에 따라 잠재적으로 추가 각 하나는 다른 데이터 구조로, 나는 현재 SortedSet<>을 사용하고 있습니다. 이 후 최상위 정렬 된 n 개 항목을 목록으로 원합니다.

내가 이것을 SortedSet<>에해야만하는 또 다른 일은 모든 것이 명확하고 새롭게 시작됩니다. 이 일에서 조금 더 성과를 낼 수있는 방법이 있습니까?

저는 this similar question을 보았습니다. 포스터는 사용자 정의 빨강 - 검정 나무를 사용하여 런타임에서 약 1/6의 시간 단축을 달성 할 수있었습니다 (질문에 답한 후). 그러나 이미 SortedSet <> 빨강 - 검정 트리가 아닌가요? 이 경우 자신의 데이터 구조를 생성하여 성능 향상을 시도해 볼 가치가 있습니까?

Answer 1

프로그램에서 사용하지 않는 것에 대해 "비용을 지불하지 않음"으로써 조금 더 나은 성능을 얻을 수 있습니다. 모든 요소가 정렬 된 트리 구조를 사용하는 대신 요소를 정렬하지 않고 heap을 사용할 수 있지만 k * log(n) 시간에 k 개의 가장 큰 요소를 추출 할 수 있습니다.

힙은 삽입 및 삭제시 균형 잡힌 나무보다 빠른 경향이 있으며 인접한 메모리 영역도 차지하므로 "캐시 친 화성"이 향상 될 수 있습니다. 물론 속도 향상은 무료가 아닙니다. 힙은 맨 위에있는 항목 이외의 항목을 빠르게 정렬하거나 제거하지 못합니다.