20k 조회 목록에 대해 60k 항목을 확인해야합니다. (같은 컬렉션 개체 있는가 List
, HashTable
exceptionly 빠르게 제공) 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