unordered_map插入爬行停止

基本上，我有一個unordered_map並試圖向它添加一組對......約500,000個對。我注意到，當我添加對時，插入速度變得越來越慢，直到它最終停止在一起。任何想法爲什麼這可能是或如何解決這個問題？unordered_map插入爬行停止

地圖定義：

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

Hash函數 - 注意，對於我來說，我不擔心pair.first == pair.second，所以我相信這個散列函數應該是足夠的，正確的我，如果我錯了：

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

方法添加值到unordered_map，試着增加約200000-500000對：

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++ ; 
     } 
    } 
}

編輯：我其實更接近加入〜5000萬對組...剛跑測試...

EDIT2：

示例輸出凍結之前，其中數在映射條目的數量。我相信這是試圖重提地圖，但不知道爲什麼它沒有這樣做，電腦死機：

檢查顆粒：87500計數：35430415負荷係數：0.988477

檢查顆粒：87600計數： 35470808負載因子：0.989652

檢查顆粒：87700計數：35511049負載因子：0.990818

檢查顆粒：87800計數：35555974負載因子：0.992073

檢查顆粒：87900個COUN T：35595646負載因子：0.993163

檢查顆粒：88000計數：35642165負載因子：0.994427

檢查顆粒：88100計數：35679608負載因子：0.995434

檢查顆粒：88200計數：35721223負載因數：0.996563

檢查顆粒：88300計數：35760313負載因子：0.997616

檢查顆粒：88400計數：35799621負載係數：0.9987

檢查顆粒：88500計數：35833445負荷係數：0.999649

來源

2011-11-06 ElfsЯUs

這也可能是最好堅持使用一個更好的散列函數的升壓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; 
    } 
    }; 
}

來源

2011-11-06 21:25:56

添加專業化是否合法？標準庫不爲'pair'提供'hash'嗎？ –

@ k-ballo - 沒有標準庫不包括哈希對...悲哀:) –

Kerrek SB - 假設我無法使用助推庫，你會怎麼做呢？ –

您是否嘗試過使用reserve()預分配足夠的桶爲所有你的配對？添加這麼多對可能會觸發許多調整大小（和重新哈希）。

接下來我要檢查的是你的散列函數。它看起來有點懷疑，如果你得到很多散列衝突，你很多會得到一堆溢出桶，這會減慢每個插入的查找 - 在這種情況下，你最好用std::map。您可以修改您的代碼以存儲每對的散列值，然後檢查您生成的唯一散列值的數量。

來源

2011-11-07 02:46:38 beldaz

tr1 :: unordered_map似乎沒有reserve（）函數...你的意思是rehash（）嗎？看起來這兩個功能可能類似... –

試着看看unordered_map :: load_factor（）。此調用的結果理想情況下應爲< 1.0。如果它超過1.0，那麼你的散列函數可能是不好的。你應該使用hash_combine而不是XOR你的對。

來源

2011-11-07 13:00:41 Alan

unordered_map插入爬行停止

回答

相關問題