hash_map 및지도가 더 빠릅니까? 10000 개 미만의 항목

해시 맵은 색인 생성을 위해 문자열/키의 해시를 생성합니다. 복잡성을 증명하면서 O (1)로 언급되었지만 hash_map은 문자열의 해시가 다른 문자열의 해시와 동일한 색인을 생성 할 수 있으므로 모든 삽입에 대한 충돌 감지를 수행합니다. 따라서 해시 맵은 이러한 충돌을 관리하기 위해 복잡합니다. 이러한 충돌을 이해하려면 입력 데이터를 기반으로합니다.

그러나 구조에서 많은 조회를 수행하려면 hash_map을 선택하십시오.

출처

2009-07-14 10:09:42

는 일반적으로 당신은 다양한 작업의 복잡성을보고, 그 좋은 가이드입니다 :

나는이 Dr.Dobbs 기사 가장 귀하의 질문에 대답 할 생각은, (1) 삽입 O를 상각 O (1) 조회, O (로그 N)에 대한 해시 맵 삭제 트리 기반 맵에 대한 삽입, 찾아보기, 삭제.

그러나 상수항이 극단적이기 때문에 복잡도가 잘못된 경우가 있습니다. 예를 들어, 10k 항목이 문자열에서 키를 입력했다고 가정합니다. 이 문자열은 각각 100k 문자 길이라고 가정 해보십시오. 서로 다른 문자열이 일반적으로 문자열의 시작 부분에서 다르다고 가정합니다 (예 : 본질적으로 무작위 인 경우 쌍은 확률이 255/256 인 첫 번째 바이트에서 달라집니다).

그런 다음 조회를 수행하려면 해시 맵이 100k 문자열을 해시해야합니다. 이것은 컬렉션의 크기에서 O (1)이지만 문자열의 길이가 O (M) 일 가능성이 굉장히 오래 걸릴 수 있습니다. 균형 잡힌 트리는 로그 N < = 14 비교를 수행해야하지만, 각 비교는 단지 몇 바이트 만 봐야합니다. 이것은 그리 오래 걸리지 않을 수도 있습니다.

64 바이트 캐시 라인 크기에서 해시 맵은 1500 개의 순차 라인을로드하고 100k 바이트 연산을 수행하지만 트리는 15 개의 임의 라인 (실제로는 문자열을 통한 간접 참조로 인해 30 개)을로드합니다) 및 14 * (일부 작은 숫자) 바이트 작업을 수행합니다. 전자가 후자보다 느릴 수도 있습니다. 또는 더 빨라질 수도 있습니다 : 아키텍처의 FSB 대역폭, 정지 시간 및 예상 판독 캐싱이 얼마나 좋을까요?

조회가 일치하는 것을 발견하면 물론이 두 구조는 단일 전체 길이 문자열 비교를 수행해야합니다. 또한 버킷에 충돌이 발생하면 해시 맵이 추가 실패 비교를 수행 할 수 있습니다.

따라서 실패한 비교가 무시할 정도로 빠르다고 가정하면 성공한 비교 및 해싱 작업은 느리지 만 트리는 해시의 1.5-2 배 정도 빠릅니다. 그러한 가정이 성립되지 않는다면, 그렇게되지 않을 것입니다.

극단적 인 예로, 데이터에서 O (log N) 연산이 특정 O (1) 연산보다 상당히 빠르다는 것을 쉽게 알 수 있습니다. 당신은 물론 테스트하고 싶지만, 테스트 데이터가 실제 세계를 대표하지 않으면 테스트 결과가 대표가 될 수 없습니다. 복잡도에 기반한 데이터 구조의 비교는 N이 무한대에 접근 할 때 한계의 행동을 나타냅니다. 그러나 N은 무한에 접근하지 않습니다. 그것은 10000입니다.

출처

2009-07-14 11:12:54

hash_map은 좋은 해시 기능을 가정하고 거의 일정 시간 O (1) 작업을 제공하는 것을 사용합니다. hash table.

지도는 내가지도와 숙박, 그것은 안전 말하고 싶지만

매우 허용 (13)의 10000 개 요소, O (LG 전자 (N)) 작업을 제공하는 BST를 사용합니다.

출처

2009-07-14 14:26:04

감사합니다! hash_map 대신 맵을 사용하기로 결정했습니다. – user25749

hash_map 및지도가 더 빠릅니까? 10000 개 미만의 항목

답변

관련 문제