HashSet 대성능 목록
https://stackoverflow.com/questions/150750
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
그것은 분명히 검색하의 성능이 일반 HashSet<T> 클래스의 보다 높은 일반 List<T> 클래스입니다.비 hash 기반 핵심으로 선형 접근 방식에서 List<T> 클래스입니다.
그러나 계산하고 해시 키할 수 있습 자체 걸 CPU 사이클,그래서 작은 금액에 대한 항목의 선형 검색될 수 있는 진정한 대안을 HashSet<T>.
나의 질문:어디어?
을 단순화 시나리오(및 공정)다고 가정해 봅시다 List<T> 클래스를 사용하여 요소의 Equals() 는 방법을 확인하는 항목입니다.
해결책
많은 사람들이 일단 당신이 속도가 실제로 크기에 도달하면 실제로는 관심이 있다고 말합니다. HashSet<T> 항상 이길 것입니다 List<T>, 그러나 그것은 당신이하는 일에 달려 있습니다.
당신이 있다고 가정 해 봅시다 List<T> 그것은 평균 5 개의 항목 만 가지고있을 것입니다. 많은 사이클에 걸쳐 단일 항목이 추가되거나 각 사이클을 제거하면 List<T>.
나는 내 컴퓨터에서 이것에 대한 테스트를했는데, 이점을 얻으려면 매우 작아야합니다. List<T>. 짧은 문자열 목록의 경우 크기가 5 이후에 이점이 사라졌습니다.
1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms
2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms
3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms
4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms
5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms
6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms
7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms
8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms
9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms
1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms
4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms
7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms
10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms
13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms
16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms
19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms
22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms
25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms
28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms
31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms
34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms
37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms
40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms
43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms
46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms
49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms
다음은 그래프로 표시된 데이터입니다.
코드는 다음과 같습니다.
static void Main(string[] args)
{
int times = 10000000;
for (int listSize = 1; listSize < 10; listSize++)
{
List<string> list = new List<string>();
HashSet<string> hashset = new HashSet<string>();
for (int i = 0; i < listSize; i++)
{
list.Add("string" + i.ToString());
hashset.Add("string" + i.ToString());
}
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove("string0");
list.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove("string0");
hashset.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}
for (int listSize = 1; listSize < 50; listSize+=3)
{
List<object> list = new List<object>();
HashSet<object> hashset = new HashSet<object>();
for (int i = 0; i < listSize; i++)
{
list.Add(new object());
hashset.Add(new object());
}
object objToAddRem = list[0];
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove(objToAddRem);
list.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove(objToAddRem);
hashset.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}
Console.ReadLine();
}
다른 팁
당신은 이것을 잘못보고 있습니다. 예, 목록의 선형 검색은 소수의 항목에 대한 해시 세트를 이길 것입니다. 그러나 성능 차이는 일반적으로 작은 컬렉션에 중요하지 않습니다. 일반적으로 걱정해야 할 큰 컬렉션입니다. Big-O의 관점에서 생각하십시오. 그러나 해시 세트 성능에 대한 실제 병목 현상을 측정 한 경우 하이브리드 목록/해시 세트를 만들 수 있지만 많은 경험적 성능 테스트를 수행하여 질문을하지 않습니다.
그것은 무의미한 기본적으로 비교하는 두 개의 구조에 대한 성능 는 다르게 작동합니다.구조를 사용하여 전달하는 이도 있었습니다.심지어 말한다면 당신 List<T> 지 않을 중복하고 반복 순서는 중요하지 않습니 그것을 만드는 비교 HashSet<T>, 그는 여전히 가난한 선택 사용 List<T> 기 때문에 상대적으로 적은 내결함성을 적용할 수도 있습니다.
는 말했다,나는 검사 몇 가지 다른 측면 의 성능,
+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition | Removal | Memory |
| | access | | | | | |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T> | O(1) | O(n) | O(n) | O(1)* | O(n) | Lesser |
| HashSet<T> | O(n) | O(1) | n/a | O(1) | O(1) | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+
* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.
** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.
Hashset <> 또는 List <>를 사용할지 여부 컬렉션에 액세스하는 방법. 항목 순서를 보장 해야하는 경우 목록을 사용하십시오. 그렇지 않은 경우 해시 세트를 사용하십시오. Microsoft가 해싱 알고리즘 및 객체의 구현에 대해 걱정하게하십시오.
해시 세트는 컬렉션을 열거하지 않고 항목에 액세스합니다 (복잡성 o (1) 또는 그 근처), 목록은 해시 세트와 달리 순서를 보장하기 때문에 일부 항목은 열거되어야합니다 (O (n)의 복잡성).
방금 이전의 답변을 설명하기 위해 다른 시나리오의 벤치 마크를 가지고있을 것이라고 생각했습니다.
- 몇 가지 (12-20) 작은 문자열 (5 ~ 10 자 사이의 길이)
- 많은 (~ 10k) 작은 문자열
- 몇 가지 긴 줄 (200 ~ 1000 자 사이의 길이)
- 많은 (~ 5k) 긴 줄
- 몇 정수
- 많은 (~ 10k) 정수
그리고 각 시나리오에 대해 나타나는 값을 찾고 있습니다.
- 목록의 시작 부분에서 ( "시작", 색인 0)
- 목록의 시작 부분 근처 ( "조기", 색인 1)
- 목록의 중간에 ( "중간", 인덱스 카운트/2)
- 목록의 끝 근처 ( "늦은", 색인 카운트 -2)
- 목록의 끝에서 ( "end", index count-1)
각 시나리오 전에 임의의 크기의 임의 문자열 목록을 생성 한 다음 각 목록을 해시 세트로 공급했습니다. 각 시나리오는 본질적으로 10,000 번 실행되었습니다.
(테스트 의사 코드)
stopwatch.start
for X times
exists = list.Contains(lookup);
stopwatch.stop
stopwatch.start
for X times
exists = hashset.Contains(lookup);
stopwatch.stop
샘플 출력
Windows 7, 12GB RAM, 64 비트, Xeon 2.8GHz에서 테스트
---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...
Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]
---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...
Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]
---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...
Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]
---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...
Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]
---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...
Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]
---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...
Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]
양익원은 해시 계산 비용에 따라 다릅니다. 해시 계산은 사소한 일이든 아니든 ... :-) 부진한 지점에 대해 걱정할 필요가 없도록 항상 System.Collections.specialized.hybridDictionary 클래스가 있습니다.
항상 그렇듯이 대답은 "때에 따라 다르지". 나는 당신이 C#에 대해 말하는 태그에서 가정합니다.
가장 좋은 방법은 결정하는 것입니다
- 일련의 데이터
- 사용 요구 사항
몇 가지 테스트 사례를 작성하십시오.
또한 목록을 정렬하는 방법 (전혀 정렬 된 경우), 어떤 종류의 비교가 필요한지, 목록의 특정 객체에 대한 "비교"작업이 얼마나 오래 걸리거나, 심지어 사용하려는 방법에 따라 다릅니다. 수집.
일반적으로 선택하기 가장 좋은 것은 데이터의 크기를 기반으로하는 것이 아니라 해당 데이터에 액세스하려는 방식을 기반으로합니다. 특정 문자열 또는 기타 데이터와 관련된 각 데이터가 있습니까? 해시 기반 컬렉션이 가장 좋을 것입니다. 저장중인 데이터의 순서가 중요합니까, 아니면 모든 데이터에 동시에 액세스해야합니까? 그러면 일반 목록이 더 나을 수 있습니다.
추가의:
물론 내 의견은 '성능'이 데이터 액세스를 의미한다고 가정합니다. 고려해야 할 사항 : "성능"이라고 말할 때 무엇을 찾고 있습니까? 성능 개별 가치가 찾아 다니고 있습니까? 대형 (10000, 100000 이상) 값 세트의 관리입니까? 데이터 구조를 데이터로 채우는 성능입니까? 데이터 제거? 개별 비트의 데이터에 액세스 하시겠습니까? 값 대체? 값을 반복합니까? 메모리 사용? 데이터 복사 속도? 예를 들어, 문자열 값으로 데이터에 액세스하지만 기본 성능 요구 사항이 메모리 사용이 최소 인 경우 디자인 문제가 상충 될 수 있습니다.
브레이킹 포인트를 자동으로 감지하고 널 값을 수용하여 해시 세트와 동일하게하는 하이브리드 소설을 사용할 수 있습니다.
때에 따라 다르지. 정확한 대답이 실제로 중요하다면 프로파일 링을하고 알아보십시오. 세트에 특정 수의 요소 이상이 없다고 확신한다면 목록을 가지고 가십시오. 숫자가 생겨나면 해시 세트를 사용하십시오.
당신이 해시하는 것에 따라 다릅니다. 키가 정수 인 경우 해시 세트가 더 빠르기 전에 많은 항목이 필요하지 않을 수 있습니다. 문자열에서 키를 키우면 느려지고 입력 문자열에 따라 다릅니다.
확실히 당신은 벤치 마크를 꽤 쉽게 채울 수 있습니까?
고려하지 않은 한 가지 요소는 gethashcode () 함수의 견고성입니다. 완벽한 해시 기능을 사용하면 해시 세트는 분명히 더 나은 검색 성능을 제공합니다. 그러나 해시 함수가 감소함에 따라 해시 세트 검색 시간도 마찬가지입니다.
많은 요인에 따라 다릅니다 ... 목록 구현, CPU 아키텍처, JVM, 루프 의미, Equals Method의 복잡성 등 ... 목록이 효과적으로 벤치마킹 (1000+ 요소), 해시 기반 바이너리를 효과적으로 벤치마킹 할 수있을 정도로 커질 정도로 커질 수 있습니다. 조회는 선형 검색을 이길 수 있으며 차이는 거기에서만 비늘이 나옵니다.
도움이 되었기를 바랍니다!
