해시 맵이 빠르지 만 삽입 속도가 느림

Question

해시도 google :: dense_hash_map의 Google 구현을 사용하고 있습니다.

광산은 클러스터링 응용 프로그램입니다. 그래서 클러스터 쌍 사이에 거리를 저장해야합니다. 각 클러스터에는 long int 인 클러스터 ID가 있습니다. 따라서 키는 (long int id1, long int id2)이어야합니다.

그래서이 작업을 위해 hashMap 내에 hashMap이 필요하다고 결정했습니다.

google::dense_hash_map<long int, google::dense_hash_map<long int, double> > distanceHash; 

이 해시 맵에 거리를 삽입하고

template<class Point> 
void CoverTree<Point>:: insertDistance(long int id1, long int id2, long double distance) 
{ 

    //Always id1 < id2; 
    if(id1 < id2) 
    { 
    long temp = id1; 
    id1 = id2; 
    id2 = temp; 
    } 


    if(distanceHash.find(id1) == distanceHash.end()) 
    { 
    google::dense_hash_map<long int, double> insideHash; 
    insideHash.set_empty_key(-9999 ); 
    insideHash[id2] = distance; 
    distanceHash[id1] = insideHash; 
    } 
    else 
    { 
    (distanceHash[id1])[id2] = (distanceHash[id1])[id2]; 
    } 
} 

template<class Point> 
double CoverTree<Point>::getStoredDistance(long int id1, long int id2) 
{ 
    if(id1 < id2) 
    { 
    long temp = id1; 
    id1 = id2; 
    id2 = temp; 
    } 

    google::dense_hash_map<long int, double>::iterator it; 

    if(distanceHash.find(id1) != distanceHash.end()) 
    { 

    if(distanceHash[id1].find(id2) != distanceHash[id1].end()) 
     return distanceHash[id1][id2]; 
    } 

    return -1; 
} 

나는 거리의 수백만을 검색하는 코드는 다음과 같습니다

이 내 거리 저장 해시 맵의 구조입니다. LasTime 내가 조사한 바에 따르면 대략 600000000 개의 거리가 있었고 그 중 400000000 개가 고유했습니다. 이것은 거리의 1/3이 반복되고 그 시간이 절약 될 수 있음을 의미합니다.

그러나이 해시 맵 구조를 사용하여 거리를 저장하면 프로그램이 느리게 실행됩니다. 이것은 정확히 무엇입니까? 거리 함수를 사용하여 거리를 저장하면 전체 프로그램이 약 50 초 더 느리게 실행됩니다. (보관시 200 초, 사용하지 않을 경우 150 초). 그러나 거리를 저장 한 다음 해시 맵을 사용하여 계산하기 전에 거리가 존재하는지 여부를 확인하면 프로그램이 길어집니다 (프로그램의 1/25 초가 소요됨).

이 동작을 이해하지 못합니다. 일단 거리가 저장되면 거리를 검색하는 것이 더 빠를 것입니다. 여기에 무엇이 잘못되었는지 알려주고 더 빨리 만들 수 있는지 알려주세요.

P.S : RAM은 문제가되지 않습니다. 나는 약 160 기가의 RAM을 가진 서버에서 이것을 실행하고있다. 해시 맵 사용시 피크 메모리 사용량은 총 메모리의 1.8 %에 불과합니다 (상단을 사용하여 보았 음). 따라서 페이징과 스 래싱은 문제가되지 않습니다.

Answer 1

But If I store the distances and then use the hashmap to check whether the distances exist before computing them, the program becomes way way slower(1/25th of the program takes 300 seconds).

난 당신이 데이터를 승인 할 모든 요소를 ​​찾아 내고있다 생각한다.

좋아는 해시 맵 룩업 시간 복잡도는 O (N)이지만, 최악의 경우에 대해 총 복잡도 O (n 개 * 않음)를 만드는 getStoredDistance 함수 n 번, 두 번

distanceHash.find(id1) 

를 사용

400M의 *의 400M = 너무 복잡 160000000000000000