stl hash_map 단순 해시 함수보다 느림?

Question

나는 소수의 다른 소수 (테이블 크기)를 곱하는 간단한 해쉬 함수를 비교하고있다. stl은 100 배 느리다. 이것은 내가 쓴 테스트 방법 :

이

stdext:: hash_map<string, int> hashDict; 
for (int l = 0; l < size; ++l){ 
    hashDict[arr[l]] = l; 
} 
long int before3 = GetTickCount(); 
int c = 0; 
while (c < size){ 
    hashDict[arr[c]]; 
    c++; 
} 
long int after3 = GetTickCount(); 
cout << "for stl class, the time is " << (after3 - before3)/1000.0 << '\n'; 
cout << "the average is " << ((after3 - before3)/1000.0) /long (size) << '\n'; 

사전의 크기는 약 200K 요소와 내가 쓴 해시 함수의 테이블 크기는 3m 항목, 그래서 어쩌면의 테이블 크기와 상관이있다 stl 클래스는 매우 작습니다. 누구든지 stl 함수의 tablesize와 collision rates.etc를 알고 있습니까?

Answer 1

VS2008의 STL 구현은 문자열을 다음과 같은 해시 함수를 사용하지 않습니다 :

size_t _Val = 2166136261U; 
while(_Begin != _End) 
    _Val = 16777619U * _Val^(size_t)*_Begin++; 

이 확실하지 100 배 더 효율성이 당신보다, 내가 빌더 버전이 매우 다릅니다 의심한다. 차이점은 측정 (GetTickCount()은 그다지 정확하지 않음) 또는 해시 값 계산 이외의 작업입니다.

C++ Builder에 대해 잘 모르지만 일부 STL 구현에는 디버그 버전에 추가 체크 및 어설 션이 많이 포함되어 있습니다. 최적화 된 릴리스 빌드를 프로파일 링 해 보셨습니까?

최소한이지만 완전한 예제를 게시하면 진행 상황을 파악하는 데 도움이되지만 더 많은 코드가 없으면 실제로 말할 내용이 많지 않습니다.

Answer 2

답변으로 게시하려면 다음과 같이하십시오. 잘못된 값이 표시되는 것 같습니다. 실제로 해시 된 값을 사용하지 않고 참조 만하기 때문에 컴파일러는 hash_map이 아닌 해시 테이블에 대한 액세스를 최적화 할 수 있습니다.

매우 드문 경우를 제외하고는 여전히 동일한 알고리즘을 사용하면서 큰 통합 요소로 전문적인 구현을 이길 수는 없습니다. 적어도 100의 요인으로 그것을하는 것보다 추첨에서 큰 상을받을 가능성이 있습니다.

값을 사용하도록 테스트 코드를 변경하십시오. 이를 합하여 합계를 출력하십시오. 속도가 빠르며 프로그램이 각 값을 찾도록 강요합니다.

Answer 3

디버그 빌드와 릴리스 빌드간에 큰 차이가있을 수 있음을 확인할 수 있습니다. 예제에서는 hash_map 및 list를 사용하는 프로그램이 있습니다. 디버그 버전이 8 분 이상 실행되었습니다. 릴리스 버전이 1 초 이내에 실행되었습니다. 적어도 480x 시간의 차이가 있습니다.