나는 정리하고 게임 중에 다른 시간에 검색해야하는 약 3000 개의 파일이 있습니다.사전 <>의 항목에 제한이 있습니까?
나는 내 자신의 변수 구조를 만들었습니다. 응용 프로그램 시작시 "사전" 을 작성하고 게임을 시작하기 전에 모든 파일을로드하는 방법에 대해 생각했습니다.
성능에 대한 궁금한 점이 있습니다.이 항목이 많은 사전은 내 응용 프로그램의 속도가 느려 집니까? 큰 사전은 "TryGetValue"와 "ContainsKey"를 느리게 실행합니까?
조언을 주셔서 감사합니다!
TryGetValue와 ContainsKey는 키가 분산 된 해시가있는 한 그 크기에서 매우 빠릅니다.
사전에는 색인 할 수있는 "버킷"수가 있습니다. 키에 의해 값을 추가하거나 찾으면 GetHashCode()에 의해 반환 된 값을 취해 버킷의 수보다 작게 다시 해시합니다 (일반적으로 모듈로와 같은 간단한 것이지만 구현은 정의되지 않음). 관련 버킷을 살펴보십시오.
버킷에는 현재 0 개 이상의 항목이 있습니다. 사전은 .Equals()를 사용하여 각 항목을 키와 비교합니다.
오른쪽 버킷을 찾는 첫 번째 비트는 일정 시간 O (1)이 될 것입니다. 버킷의 키와 키를 비교하는 두 번째 비트는 단 시간 O (n) 일 것입니다. 여기서 n은 전체 모음이 아닌 해당 버킷의 항목 수와 관련이 있습니다.
일반적으로 각 버킷에는 항목이 거의 없어야합니다 (버킷 수는이 경우 계속 유지하려고합니다). 따라서 작업은 본질적으로 일정 시간입니다.
그러나 해시 코드가 제대로 구현되지 않은 경우 동일한 버킷에 많은 키가 있습니다. 매번 0을 반환하는 고의적으로 나쁜 GetHashCode를 가진 객체를 실험하여 볼 수 있듯이 시간 복잡도는 O (n)에 가깝고 가까워 질 것입니다. List가 O (n)이기 때문에 Dictionary보다 더 많은 오버 헤드가 있기 때문에 더 나쁜 경우 List보다 나쁩니다.
걱정할 필요가있는 것이 있습니까? 아니, 상대적으로 순진한 해싱 방법조차도 비교적 좋은 결과를 제공해야합니다. 문자열 키를 사용한다면 아마도 이미 충분히 좋은 것일 것입니다. 간단한 기본 제공 유형을 사용하는 경우 훨씬 더 그렇습니다.
사전 액세스가 느린 경우이 문제에주의하고 GetHashCode() 메소드를 수정하거나 GetHashCode() 및 Equals()에 대한 외부 규칙을 정의 할 수있는 IEqualityComparer)를 사용하여 사전, 해시 세트 등).
대부분의 경우에도 3000은 아무 것도 아니지만 괜찮습니다.
Dictionary<>에 대해 3000 개의 항목이 표시됩니다. 그것은 속도 저하의 원인이되지 않습니다.
시작시 3000 개의 다른 파일을 메모리로 읽는 반면, 은이 느립니다. 필요할 때만 파일을 메모리로 읽는 것이 훨씬 나을 것이지만 나중에 액세스 할 때 메모리에 저장하는 것이 좋습니다.
그는 게임에 대해 언급하고 있기 때문에 정상적인 규칙이 적용되지 않을 수 있습니다. 부하가 어느 지점에 있고 크기가 큰지에 따라 Ashe가 Deadite를 치려고 할 때보 다 시작 스플래시 화면 뒤에로드하는 것이 더 낫습니다. – AllenG
@AllenG, 좋은 지적입니다. –
아마도 프로세스를 수행하는 시작 중에 백그라운드 스레드를 생성 할 수 있습니다. –
.NET의 사전은 해시 테이블 조회 체계를 사용하므로 항목을 추가해도 조회 성능에 미치는 영향은 거의 없습니다. 문제는 메모리 사용량뿐입니다. 3000 개의 사전으로 구성된 사전은 키와 값 유형에 사용 된 저장 영역의 대략 3000 배를 소비합니다. 거대한 이진 얼룩이없는 단순한 구조체라면 3000은 아주 작습니다.
아니요. 메모리를 소비하지만 사전이 해시 테이블이며 키에 의한 요소에 대한 액세스가 일정하고 요소 수에 의존하지 않으므로 TryGetValue 및 ContainKey이 매우 빠릅니다.
+1 - 좋은 답변 – JonH
사전 키 유형에 대한 해시 코드 알고리즘을 제공하면 해시 코드가 Int32 공간에서 비교적 고르게 퍼지고 해시 코드 조회는 사전 크기의 영향을받지 않습니다.
자세한 내용은 http://en.wikipedia.org/wiki/Hashtable#Performance_analysis을 참조하십시오.
+1은 해시가 손상되지 않은 경우에만 작동한다는 것을 지적합니다. –
병목 현상은 사전의 성능이 아니라 3000 개의 파일을 읽는 것입니다. 컴퓨터 (과 성능을 특정)와 대부분의 것들과 마찬가지로
는, 그것은 모든 사전의 실현하는 것이에 따라
"그것은 (TM)를 따라 다릅니다."
이진 트리로 수행 할 수 있습니다.이 경우 검색은 O (log2 N) 여야합니다. 즉, 사전의 크기가 커질수록 조회 시간이 길어집니다.
이론상 O (1) 인 해시 테이블로 수행 할 수 있습니다. 즉, 사전의 크기에 관계없이 조회에 항상 같은 시간이 걸릴 수 있지만 그 것이 이론입니다. 버킷 수와 해시 코드의 품질에 따라 달라집니다. 많은 아이템이 같은 양동이에서 끝나기 때문에 선형 검색이 필요합니다. 사전이 커짐에 따라 상당히 느려집니다.
그러나 사전은 눈에 띄는 차이가 발생하기 전에 3000 배 이상 커야합니다.
사전 <>은 해시 테이블을 사용하는 것으로 명시되어 있습니다. –
한계가 있지만 그 근처에 3000이 없습니다. Dictionary<>은 Object.GetHashCode()을 사용하여 키를 오리지널 처리하고 int을 반환합니다.따라서 충돌이 발생하기 전에 최대 2^32 (4,294,967,296) 키를 저장할 수 있습니다. 그러나 .Net의 해시 코드는 일반적으로 계산되므로이 마법 번호에 가까워 질수록 많은 충돌이 발생할 수 있습니다.
더 많은 키를 추가해도 TryGetValue 및 ContainsKey의 속도는 저하되지 않습니다.이 값은 O(1)입니다.
마지막 두 문장이 충돌합니다. 두 개의 키가 충돌하는 경우 고유 한 해시 코드가있는 키보다 키를 가져 오는 데 시간이 오래 걸릴 수 있습니다. –
.NET의 해시 코드는 일반적으로 계산되는 방식과 관련이 없으며 기본 계산과 관련이 있습니다. 첫째, 2^32 개 이상의 가능한 값 (대부분의 유형에 해당)이 있으면 미리 값을 알고 완벽 해시를 만들 수 없다면 고유성을 보장 할 수 없습니다.또한 사전은 16GB 상당의 포인터 공간을 차지하므로 2^32 슬롯 (참조 유형이 저장되지 않은 경우 더 많을 수 있음)을 차지할 수는 있지만 충돌이 줄어들어 사전에 시작하지 않습니다. 그럼에도 불구하고 잘 분산 된 비트로 충돌은 일반적으로 드뭅니다. 약간의 충돌은별로 상처주지 않을 것입니다. –
시도해보고 측정하십시오! – Brian