해시 세트 대퍼포먼스 일람
인 검색 HashSet<T>.List<T>class.만 하면 .List<T>를 누릅니다
, 해시 사이클이 수 .따라서 은 CPU의 가 될 수 .HashSet<T>.
제 질문은 손익분기점은 어디인가요?
를 들어,를 들면, 예를 들면, 예를 들면, 「아주 공평하게」라고해 봅시다.List<T>""를 합니다.Equals()항목을 식별하는 방법.
많은 분들이 속도가 걱정되는 크기에 도달하면HashSet<T> 두들겨 패다List<T>하지만 그것은 당신이 무엇을 하느냐에 달려있다.
를 들어, 예를 들어 ''가 .List<T>5년 전의 아이템을 하면 사이클마다 되는 것이 .List<T>.
제 기계로 테스트를 해봤는데, 아주 작아야 이점을 얻을 수 있어요.List<T>짧은 문자열 목록에서는 크기가 5보다 크면 장점이 사라졌고 크기가 20보다 크면 객체의 장점이 사라졌습니다.
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();
}
서로 다르게 동작하는 성능을 위해 두 구조를 비교하는 것은 근본적으로 의미가 없습니다.의도를 전달하는 구조를 사용하세요.아무리 네가 말한다고 해도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** |
+------------+--------+-------------+-----------+----------+----------+-----------+
두 경우 모두 addition은 O(1)이지만 해시 코드를 저장하기 전에 미리 계산하는 비용이 수반되기 때문에 HashSet에서는 상대적으로 느립니다.
HashSet의 뛰어난 확장성에는 메모리 비용이 듭니다.모든 엔트리는 해시 코드와 함께 새 개체로 저장됩니다.이 기사가 당신에게 아이디어를 줄지도 몰라요.
당신은 이것을 잘못 보고 있어요.예. 목록을 선형으로 검색하면 소수의 항목에 대해 해시 집합보다 우선합니다.그러나 일반적으로 컬렉션 수가 적은 경우에는 성능 차이가 문제가 되지 않습니다.일반적으로 많은 컬렉션을 고려해야 합니다. Big-O의 관점에서 이 점을 고려해야 합니다.그러나 HashSet 성능의 실제 병목 현상을 측정했다면 하이브리드 List/HashSet을 만들 수 있지만 SO에 대한 질문을 하지 않고 많은 경험적 성능 테스트를 수행함으로써 그렇게 할 수 있습니다.
HashSet <> 또는 List <> 중 어느 쪽을 사용할지는 컬렉션에 액세스하는 방법에 따라 결정됩니다.항목 순서를 보장해야 할 경우 목록을 사용하십시오.그렇지 않으면 HashSet을 사용합니다.Microsoft는 해싱 알고리즘과 오브젝트의 실장에 대해 염려하고 있습니다.
HashSet은 컬렉션(O(1)의 복잡도 또는 그 부근)을 열거할 필요 없이 항목에 액세스하며, HashSet과 달리 목록은 순서를 보장하므로 일부 항목(O(n)의 복잡도)을 열거해야 합니다.
이전 답변을 설명하기 위해 다양한 시나리오의 벤치마크를 몇 가지 살펴보겠습니다.
- 작은 문자열 몇 개(12~20자)(5~10자 길이)
- 다수의 작은 문자열(~10,000)
- 몇 개의 긴 문자열(200~1000자 길이)
- 많은 (500K까지) 길이의 문자열
- 몇 개의 정수
- 다수의 (10,000까지) 정수
각 시나리오에 대해 표시되는 값을 검색합니다.
- 목록의 선두("시작", 인덱스 0)
- 리스트의 선두 부근(「조기」, 인덱스 1)
- 목록의 중간("중간", 인덱스 수/2)
- 리스트의 말미("late", 인덱스 수-2) 근처
- 목록의 마지막("끝", 인덱스 카운트-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.8에서 테스트 완료GHz
---------- 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]
손익분기점은 해시 계산 비용에 의존합니다.해시 계산은 단순할 수도 있고 그렇지 않을 수도 있습니다. :-) 시스템은 항상 존재합니다.컬렉션전문.Hybrid Dictionary 클래스로 손익분기점에 대해 걱정할 필요가 없습니다.
HybridDictionary를 사용하면 브레이크 포인트를 자동으로 검출하고 늘 값을 받아들이기 때문에 기본적으로 HashSet과 동일합니다.
대답은 언제나 그렇듯이, "그것은 좌우된다"입니다.태그로 봤을 때 C#을 말씀하시는 것 같네요.
가장 좋은 방법은 다음 사항을 결정하는 것입니다.
- 데이터 세트
- 사용요건
몇 가지 테스트 케이스를 쓰세요.
또한 목록을 정렬하는 방법(정렬된 경우), 어떤 종류의 비교를 수행해야 하는지, 목록의 특정 개체에 대해 "비교" 작업이 걸리는 시간 또는 컬렉션을 사용하는 방법에 따라 달라집니다.
일반적으로 가장 적합한 선택은 작업 중인 데이터의 크기가 아니라 데이터에 액세스하는 방법에 따라 선택해야 합니다.각 데이터가 특정 문자열 또는 기타 데이터와 관련되어 있습니까?해시 기반 컬렉션이 가장 좋습니다.저장하는 데이터의 순서가 중요합니까, 아니면 모든 데이터에 동시에 액세스해야 합니까?그럼 일반 리스트가 더 나을 수도 있어요.
추가:
물론 위의 코멘트는 '성능'이 데이터 액세스를 의미한다고 가정합니다.고려해야 할 다른 사항: "퍼포먼스"라고 할 때 무엇을 찾고 계십니까?퍼포먼스는 개별 가치 검색입니까?대규모(10000, 100000 이상) 값 세트의 관리입니까?데이터 구조를 데이터로 채우는 성능입니까?데이터를 삭제하시겠습니까?개별 데이터 비트에 액세스하시겠습니까?값을 대체하시겠습니까?가치관을 반복하고 있습니까?메모리 사용량?데이터 복사 속도예를 들어 문자열 값으로 데이터에 액세스하지만 주요 성능 요구 사항이 최소 메모리 사용량인 경우 충돌하는 설계 문제가 있을 수 있습니다.
사정에 따라 다르겠지.정확한 답이 정말 중요하다면 프로파일링을 해서 알아보세요.세트에 포함된 요소가 일정 수보다 많지 않은 경우 목록을 선택하십시오.수에 제한이 없는 경우 HashSet을 사용합니다.
해싱에 따라 다르죠키가 정수인 경우 HashSet이 더 빠르기 전에 많은 항목이 필요하지 않을 수 있습니다.문자열로 입력하는 경우 입력 문자열에 따라 속도가 느려집니다.
확실히 당신은 꽤 쉽게 벤치마크를 만들 수 있습니까?
GetHashcode() 함수의 견고성은 고려하지 않은 요인 중 하나입니다.완벽한 해시 함수를 사용하면 HashSet의 검색 성능이 확실히 향상됩니다.그러나 해시 함수가 감소함에 따라 HashSet 검색 시간도 감소합니다.
여러 가지 요인에 따라...구현, CPU 아키텍처, JVM, 루프 의미론, 등가 방법의 복잡성 등을 나열합니다.목록이 효과적으로 벤치마킹할 수 있을 정도로 커질 때까지(1000개 이상의 요소) 해시 기반 바이너리 룩업은 선형 검색을 쉽게 앞지르고 차이는 거기서부터 확대됩니다.
이게 도움이 됐으면 좋겠네요!
언급URL : https://stackoverflow.com/questions/150750/hashset-vs-list-performance
'programing' 카테고리의 다른 글
| Python을 사용하여 MS Office 매크로를 프로그래밍하고 있습니까? (0) | 2023.04.15 |
|---|---|
| XAML: 속성 'Resources'가 두 번 이상 설정되었습니다. (0) | 2023.04.15 |
| 앱이 백그라운드에서 돌아왔을 때 viewApp이 호출되지 않는 이유는 무엇입니까? (0) | 2023.04.15 |
| 디렉토리내의 파일의 경우, 에코 파일명(경로 없음)만을 사용합니다. (0) | 2023.04.15 |
| C#을 사용한 Excel Automation에서 상행 프리즈 및 필터 적용 방법 (0) | 2023.04.15 |