HashSet<T> t = new HashSet<T>();
// add 10 million items
Dictionary<K, V> t = new Dictionary<K, V>();
// add 10 million items.누구의 .Contains방법이 더 빨리 돌아 올까요?
명확히하기 위해 제 요구 사항은 데이터 구조에 존재하는지 확인해야하는 천만 개의 개체 (실제로 문자열)가 있다는 것입니다. 나는 절대 반복하지 않을 것입니다.
답변
HashSet vs List vs Dictionary 성능 테스트, 여기 에서 가져 왔습니다 .
1000000 개의 개체 추가 (중복을 확인하지 않고)
10000 컬렉션의 절반 개체에 대한 검사 포함
10000 컬렉션의 절반 개체 제거
답변
Dictionary<TKey, TValue>두 번째 경우 를 의미한다고 생각 합니까?HashTable제네릭이 아닌 클래스입니다.
실제 요구 사항에 따라 작업에 적합한 컬렉션을 선택해야합니다. 실제로 마십시오 원하는 값으로 각 키를 매핑? 그렇다면 Dictionary<,>. 다음과 같은 경우 에만 일련의 사용으로 신경HashSet<> .
나는 기대 HashSet<T>.Contains와 Dictionary<TKey, TValue>.ContainsKey그들이 근본적으로 동일한 알고리즘을 사용 – 기본적으로 동일한을 수행하기 위해 (당신이 현명하게 당신의 사전을 사용하는 가정하고 비교 작업있는). 항목 Dictionary<,>이 커지면 캐시를을 사용하는 Dictionary<,>것보다 캐시를 날려 버릴 가능성이 더 커지지 HashSet<>만 단순히 잘못된 데이터 유형을 선택하는 고통과 비교할 때 중요하지 않을 것으로 예상합니다. 달성하려고.
답변
Dictionary <TKey, TValue>에 대한 MSDN 설명서에서
” Dictionary 클래스가 해시 테이블로 구현되기 때문에 키를 사용하여 값을 검색하는 것은 O (1)에 가까워 매우 빠릅니다 . “
메모 :
“검색 속도는 TKey에 지정된 유형의 해싱 알고리즘 품질에 따라 다릅니다.”
귀하의 질문 / 게시물이 오래되었다는 것을 알고 있지만 비슷한 질문에 대한 답변을 찾는 동안이 문제를 발견했습니다.
도움이 되었기를 바랍니다. 자세한 내용을 보려면 비고 섹션으로 스크롤 하십시오.
https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx
답변
이들은 다른 데이터 구조입니다. 또한 일반 버전의 HashTable.
HashSet키-값 쌍을 포함 하는 HashTable(또는 Dictionary) 유형 T의 값을 포함합니다 . 따라서 저장해야 할 데이터에 대한 수집을 선택해야합니다.
답변
이 질문에 대해 허용 된 답변은 질문에 대한 올바른 답변이 아닙니다! 정답을 제공하지만 그 답은 그들이 제공 한 증거로 보여지지 않습니다.
그 대답이 보여주는 것은 Dictionary또는 에 대한 키 조회 HashSet가 List. 사실이지만 흥미롭지도 놀랍지도 않으며 동일한 속도 를 가지고 있다는 증거도 아닙니다 .
조회 시간을 비교하기 위해 아래 코드를 실행했으며 내 결론은 실제로 동일한 속도라는 것입니다. (또는 적어도 차이가 있다면 그 차이는 그 속도의 표준 편차 내에있는 것입니다)
구체적으로,이 테스트에서 100,000,000 조회는 두 가지 모두에 대해 10 초에서 11.5 초 사이에 걸렸습니다.
테스트 코드 :
private const int TestReps = 100_000_000;
[Test]
public void CompareHashSetContainsVersusDictionaryContainsKey()
{
for (int j = 0; j < 10; j++)
{
var rand = new Random();
var dict = new Dictionary<int, int>();
var hash = new HashSet<int>();
for (int i = 0; i < TestReps; i++)
{
var key = rand.Next();
var value = rand.Next();
hash.Add(key);
dict.TryAdd(key, value);
}
var testPoints = Enumerable.Repeat(1, TestReps).Select(_ => rand.Next()).ToArray();
var timer = new Stopwatch();
var total = 0;
timer.Restart();
for (int i = 0; i < TestReps; i++)
{
var newKey = testPoints[i];
if (hash.Contains(newKey))
{
total++;
}
}
Console.WriteLine(timer.Elapsed);
var target = total;
Assert.That(total == target);
timer.Restart();
for (int i = 0; i < TestReps; i++)
{
var newKey = testPoints[i];
if (dict.ContainsKey(newKey))
{
total++;
}
}
Console.WriteLine(timer.Elapsed);
Assert.That(total == target * 2);
Console.WriteLine("Set");
}
}답변
