unordered_map 삽입이 정지 할 때까지 크롤링

Question

기본적으로 unordered_map이 있는데 그 중 50 만 개가 쌍으로 추가됩니다. 필자는 짝을 추가 할 때마다 삽입 속도가 느려지고 속도가 느려져서 결국 모두 함께 멈추는 것으로 나타났습니다. 왜 이런 일이 일어날 지 또는이 문제를 해결하는 방법에 대한 의견이 있습니까?

지도 정의 :

std::tr1::unordered_map<std::pair<int, int>, int, pairHash> x_map ; 

해시 기능 - 내 경우에 내가 == pair.first에 대해 pair.second을 걱정하지 않아도됩니다, 그래서 나는이 해시 함수가 정확, 충분해야한다 생각 내 경우 오전 잘못된 :

initialize_map(EndPoint**& arr, std::tr1::unordered_map<std::pair<int, int>, int, pairHash> &my_map, int size) 
{ 
    for(int i = 0 ; i < size ; i++) // add initial overlapping pairs 
    { 
     if(i % 100 == 0) 
      std::cout << "checking particle: " << i << " maxsize: " << my_map.max_size() << std::endl ; 
     int j = 1 ; 
     while(arr[i]->isMin && i+j < size && // while ys is a min, and not end of array 
       arr[i]->v_id != arr[i+j]->v_id)  // anything between min and max is a possible collision 
     { 
      if(!arr[i]->isEdge || !arr[i+j]->isEdge) 
      { 
       my_map[std::make_pair(std::min(arr[i]->v_id, arr[i+j]->v_id), 
         std::max(arr[i]->v_id, arr[i+j]->v_id))] = 1 ; 
      } 

      j++ ; 
     } 
    } 
} 

:

class pairHash 
     { 
     public: 
      size_t operator()(const std::pair<int, int> & v) const 
      { 
       return v.first^v.second ; 
      } 
     } ; 

방법에 대한 200,000-500,000 쌍을 추가하려고 ... unordered_map도에 값을 추가 할 수

편집 : 실제로 가까이 5천만쌍를 추가하고이 ... 단지 테스트를 실행 ...

EDIT2 : 카운트가지도 항목의 개수가 정지하기 전에

예 출력. 나는지도를 재탕하려고 생각하지만, 그렇게하는 것이 실패하고 컴퓨터를 동결 왜 확실하지 :

검사 입자 : 87500 수 : 35,430,415 하중 계수 : 0.988477

확인 입자 : 87600 수 : 35,470,808 부하율 : 0.989652

검사 입자 : 87,700 횟수 : 35,511,049 부하율 : 0.990818

검사 입자 : 87,800 횟수 : 35,555,974 부하율 : 0.992073

검사 입자 : 87,900 coun에 t : 35,595,646 부하율 : 0.993163

검사 입자 : 88000 횟수 : 35,642,165 부하율 : 0.994427

검사 입자 : 88100 횟수 : 35,679,608 부하율 : 0.995434

검사 입자 : 88,200 횟수 : 35,721,223 부하율 : 0.996563

검사 입자 : 88,300 횟수 : 35,760,313 부하율 : 0.997616

검사 입자 : 88400 횟수 : 35,799,621 부하율 : 0.9987

,451,515,

검사 입자 : 88,500 수 : 35,833,445 하중 계수 : 0.999649

Answer 1

그것은 더 나은 해시 함수에 대한 부스트 hash_combine 솔루션 스틱 아마 최선의 방법 :

template <class T> 
inline void hash_combine(std::size_t & seed, const T & v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

namespace std 
{ 
    template<typename S, typename T> struct hash< std::pair<S, T> > 
    { 
    inline std::size_t operator()(const std::pair<S, T> & v) const 
    { 
     std::size_t seed = 0; 
     hash_combine(seed, v.first); 
     hash_combine(seed, v.second); 
     return seed; 
    } 
    }; 
} 

Answer 2

가지고 당신이 reserve()를 사용하여 시도 미리 할당 너의 모든 쌍을위한 충분한 양동이? 너무 많은 쌍을 추가하면 많은 크기 조정 (및 재진입)을 유발할 수 있습니다.

다음으로 확인해야 할 것은 해시 함수입니다.조금 의심스러워 보입니다. 해시 충돌이 많이 발생하는 경우 오버플로 버킷이 많아서 각 삽입에 대한 조회 속도가 느려지므로 std::map을 사용하는 것이 좋습니다. 코드를 수정하여 각 쌍의 해시를 저장 한 다음 생성 한 고유 해시 된 값의 수를 확인할 수 있습니다.

Answer 3

unordered_map :: load_factor()를 살펴보십시오. 이 호출의 결과는 이상적으로 < 1.0이어야합니다. 1.0 이상이면 해시 함수가 아마도 dodgy입니다. 쌍을 XOR 처리하는 대신 hash_combine을 사용해야합니다.