가장 빠른 검색을 제공하는 .NET 컬렉션

가장 빠른 검색을 제공하는 .NET 컬렉션

---

20k 조회 목록에 대해 60k 항목을 확인해야합니다. (같은 컬렉션 개체 있는가 List, HashTableexceptionly 빠르게 제공) Contains()방법은? 아니면 내가 직접 써야합니까? 즉, 기본 Contains()방법은 각 항목을 스캔하거나 더 나은 검색 알고리즘을 사용하는 것입니다.

foreach (Record item in LargeCollection)
{
    if (LookupCollection.Contains(item.Key))
    {
       // Do something
    }
}

참고 . 조회 목록이 이미 정렬되었습니다.

---

가장 일반적인 경우, System.Collections.Generic.HashSet평가하는 데 일정한 시간이 걸리므로 기본 "포함"작업량 데이터 구조로 고려 하십시오 Contains.

"가장 빠른 검색 가능한 컬렉션이란 무엇입니까?"에 대한 실제 답변은 특정 데이터 크기, 순서, 해시 비용 및 검색 빈도에 따라 다릅니다.

---

주문할 필요가 없으면 HashSet<Record>(.Net 3.5를 처음 사용하십시오)

그렇다면 a를 사용하여 List<Record>전화하십시오 BinarySearch.

---

당신은 고려 했습니까 List.BinarySearch(item)?

당신은 당신의 큰 컬렉션이 이미 분류되어 완벽한 기회처럼 보인다고 말했습니까? 해시는 가장 빠를 것이지만, 이로 인해 자체 문제가 발생하고 스토리지에 더 많은 오버 헤드가 필요합니다.

---

단일 및 다중 스레드 기술을 사용하여 각각에 대해 여러 가지 유형의 콜렉션 및 메소드를 빠르게 테스트 한이 블로그 를 읽어야 합니다 .

결과에 따르면, List 및 SortedList의 BinarySearch는 "가치"로 무언가를 찾을 때 지속적으로 목을 달리는 최고 성과 기업이었습니다.

"키"를 허용하는 콜렉션을 사용할 때 Dictionary, ConcurrentDictionary, Hashset 및 HashTables가 전체적으로 가장 우수했습니다.

---

x와 y 목록을 정렬 된 순서대로 유지하십시오.

x = y이면 x <y이면 x를 진행하고 y <x이면 x가 y가 될 때까지 y를 진행하십시오.

이 교차점의 실행 시간은 최소 (크기 (x), 크기 (y))에 비례합니다.

.Contains () 루프를 실행 하지 마십시오 . 이것은 x * y에 비례하므로 훨씬 나쁩니다.

---

항목을 정렬 할 수 있다면 훨씬 빠른 방법으로 키 조회를 해시 테이블 또는 b- 트리로 수행 할 수 있습니다. 항목을 정렬 할 수없는 경우 어쨌든 b- 트리에 실제로 넣을 수는 없습니다.

어쨌든, 정렬 가능한 두 목록을 정렬하면 조회 목록을 순서대로 걷는 것입니다.

Walk lookup list
   While items in check list <= lookup list item
     if check list item = lookup list item do something
   Move to next lookup list item

---

.Net 3.5를 사용하는 경우 다음을 사용하여 더 깨끗한 코드를 만들 수 있습니다.

foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
  //dostuff
}

여기에 .Net 3.5가 없으므로 테스트되지 않았습니다. 확장 방법에 의존합니다. LookupCollection.Intersect(LargeCollection)아마 그것은 같지 않을 것입니다 LargeCollection.Intersect(LookupCollection)... 후자는 아마 훨씬 느립니다.

이것은 LookupCollection이 HashSet

---

마지막으로 성능이 저하 될 염려가 없다면 HashSet 또는 이진 검색을 사용하는 것이 좋습니다. 귀하의 데이터 세트는 99 %의 문제가 될 정도로 크지 않습니다.

그러나이 작업을 수천 번만 수행하고 성능이 중요하고 (HashSet / 이진 검색을 사용하여 수용 할 수없는 것으로 판명 된 경우) 정렬 된 목록을 걸었던 자체 알고리즘을 작성하여 비교할 수 있습니다. 각 목록은 최대 한 번 걸으며 병리학 적 사례에서는 나쁘지 않을 것입니다 (이 경로로 이동하면 문자열 또는 다른 비 적분 값을 가정하면 비교는 실제 비용이 될 것입니다. 최적화는 다음 단계가 될 것입니다).

참고 URL : https://stackoverflow.com/questions/1009107/what-net-collection-provides-the-fastest-search