지도 unordered_map도

Question

내 질문은 목적 디버깅보다 목적을 학습을위한 더 : 나는 현재 내 작은 게임 코드를 최적화하고있어

을, 나는 알고 싶어 : 내가 사용

을 내 프로그램 내에서 일부 값을 파견하기위한 맵, 그래서 unordered_map은 맵보다 사용이 빠릅니까?

(내 영어에 대한 BTW 죄송합니다, 그렇지 않은 제 모국어!)

Answer 1

차이점은 map은 내부적으로 red black tree을 사용하며 순서가 지정되지 않은지도는 hash table입니다. unordermap은 map에 비해 매우 빠릅니다. 요소를지도에 넣는 것은지도에 입력 된 값을 저장하기 위해 트리에서 올바른 위치를 찾아야하는 곳에서 단 하나 (O (1))의 "동작"을 필요로합니다. O (log n)). map 및 unordermap

Answer 2

std::unordered_map은 O입니다 검색하기 (1)하는 std::map가 레드 - 블랙 트리입니다 것을 의미한다 "hash_map"이다 , 검색은 O (log2 (n))입니다. 따라서 요소가 1000 개있는 경우 차이점은 std::map에있는 10 개의 키가 "올바른"키를 찾지 못했기 때문입니다. 1 백만 개의 요소가있는 경우 에있는 하나 인 "012"에 도달하기 전에 std::map에있는 20 개의 키를 봅니다.

그러나 "키"를 해싱해야합니다. 즉, 숫자를 만들기 위해 계산 양식을 수행해야합니다.

또한 요소를 얼마나 자주 자주 찾느냐와 비교하여 요소를 삽입/제거하는 빈도에 따라 다릅니다.

큰 데이터 세트의 경우 크기와 위치가 큰 영향을 줄 수 있으며 "처음 몇 개의 레이어"를 통한 검색은 캐시에 있기 때문에 빠르게 수행됩니다. [동일한 맵을 여러 번 검색하는 경우] (모든 10000 요소가 정확하게 10000 요소 인 해시 값을 생성 할 가능성이 거의 없기 때문에 정렬되지 않은 맵에서 더 많은 공간을 차지합니다. 따라서 일반적으로 해시 맵은 "전체"에서 멀리 떨어져 있습니다). "최근"해시 검색은 현재 캐시 검색과 일치하지 않으므로 캐시가별로 도움이되지 않습니다.

물론, std::unordered_map은 이름에서 알 수 있듯이 순서가 지정되어 있지 않습니다. 반복 할 경우 키는 해시 순서 (모듈로 버킷 수이므로 해시를 알고 있더라도 일반적으로 어렵습니다. 어떤 순서인지 아세요), "정렬 된"순서는 아닙니다. 어떤 경우에는 이것이 중요 할 수 있습니다.

성능면에서 눈에 띄는 성능상의 이점이 있는지 여부는 성능을 측정해야합니다.