C# HashSet <T> 검색 성능 (ObservableCollection <T>과 비교)?

Question

C# 일반 HashSet < T> 검색 성능은 O (1)이어야하고 ObservableCollection < T>의 검색 성능은 O (n)이어야합니다.

많은 양의 고유 한 요소가 있습니다. 각 요소에는 고유하지 않은 DateTime 속성이 있습니다.

각 요소는 단순히 DateTime.GetHashCode()를 반환하여 HashCode를 계산합니다.

이제 내 데이터의 하위 집합을 가져오고 싶습니다. 나는 300.000 요소의 컬렉션이 LINQ 쿼리를 실행하면 년 3 월 2012 2012 년 6 월

var result = from p in this.Elements 
       where p.Date >= new DateTime(2012, 03, 01) && 
         p.Date <= new DateTime(2012, 30, 06 
       select p; 

사이의 날짜가있는 모든 요소가 지정된 범위 내에있는 80 개 요소를 반환 ~ 25 밀리 소요 - HashSet < T> 또는 ObservableCollection < T>를 사용하면 문제가되지 않습니다.

모든 요소를 ​​수동으로 반복하여 확인하면 약 25ms의 시간이 걸립니다.

그러나 주어진 범위 내에있는 모든 날짜의 HashCode를 알고 있습니다. 내 HashSet < T>에서 지정된 HashCodes를 사용하여 모든 요소를 ​​가져올 수 있습니까? 나는 그것이 훨씬 더 빠를 것이라고 생각한다 ...

LINQ 쿼리의 속도를 높일 수 있습니까? 내 HashSet의 특수 기능을 사용하지 않는다고 가정합니다. < T>?

Answer 1

해시 세트는 지정된 해시가 세트에 있는지를 결정할 때 매우 효율적이라고 지적되었습니다. 쿼리는 해시 집합이 IEnumerable을 구현하여 전체 집합을 반복하고 날짜 비교를 수행한다는 사실을 사용합니다. 해시를 전혀 사용하지 않습니다. 이것이 수동 방법이 쿼리와 동일한 시간이 걸리는 이유입니다.

해시 세트의 해시를 기반으로 요소를 가져올 수 없으며 집합의 요소 존재 여부 만 테스트 할 수 있습니다. 사전은 당신이 갖고 싶어하는 것을 원한다면 (가지고 있지 않은 것처럼 보입니다)

당신이 당신의 데이터로해야 할 일과 그 것을 위해 최적화 된 구조를 사용하십시오. 이것은 여러 가지 내부 구조를 유지하는 자체 클래스 일 수 있습니다. 각 구조는 한 가지에서 효율적입니다 (범위를 검색하기위한 것과 여러 필드로 존재를 확인하기위한 것과 같이). 또는 필요에 맞는 기존 구조가있을 수 있습니다. 그러나 당신이 당신의 데이터로 무엇을하고 싶은지 알지 못해서 조언하기가 어렵습니다.

고려해야 할 다른 사항은 조기에 최적화하고 있는지 여부입니다. 수동으로 검색하는 데 25ms가 충분히 빠르면 IEnumerable을 구현하는 모든 구조가 충분할 것입니다. 어떤 경우에는 필요한 다른 기준에 따라 하나를 선택할 수 있습니다.

Answer 2

올바른 데이터 구조를 사용하고 있지 않습니다. 정렬 된 목록 (Date 속성으로 정렬 됨)과 같은 것을 사용해야하며 범위의 시작과 끝을 이진 검색 할 수 있습니다.