1

基本的に、私はunordered_mapを持っていて、それにペアのセットを追加しようとしています...それらの約500,000。ペアを追加すると、挿入速度がだんだん遅くなり、最終的にすべて一緒に停止することに気づきました。なぜこれが起こるのか、またはこれを修正する方法について何か考えはありますか？

マップの定義：

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

ハッシュ関数-私の場合、pair.first == pair.secondについて心配する必要がないことに注意してください。したがって、このハッシュ関数で十分だと思います。間違っている場合は修正してください。

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

unordered_mapに値を追加する方法...約200,000〜500,000ペアを追加しようとしています：

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

編集：私は実際に50,000,000ペア近くを追加しています...ちょうどテストを実行しました...

EDIT2：

フリーズする前の出力例。ここで、countはマップ内のエントリの数です。マップを再ハッシュしようとしていると思いますが、なぜそれが失敗してコンピューターがフリーズするのかわかりません。

チェックパーティクル：87500カウント：35430415負荷率：0.988477

チェックパーティクル：87600カウント：35470808負荷率：0.989652

チェックパーティクル：87700カウント：35511049負荷率：0.990818

チェックパーティクル：87800カウント：35555974負荷率：0.992073

チェックパーティクル：87900カウント：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

4

3 に答える 3

4

It's probably best to stick with the Boost hash_combine solution for a better hash function:

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-06T21:25:56.520 に答える
1

unordered_map::load_factor() を見てみてください。この呼び出しの結果は、理想的には < 1.0 である必要があります。1.0 を超える場合、ハッシュ関数はおそらく危険です。ペアを XOR する代わりに、hash_combine を使用する必要があります。

于 2011-11-07T13:00:41.693 に答える
0

reserve()すべてのペアに十分なバケットを事前に割り当てるためにを使用してみましたか？非常に多くのペアを追加すると、多くのサイズ変更（および再ハッシュ）がトリガーされる可能性があります。

次にチェックするのはハッシュ関数です。少し疑わしいように見えます。ハッシュの衝突がたくさん発生している場合は、各挿入のルックアップを遅くするオーバーフローバケットが大量に発生します。この場合は、を使用することをお勧めしますstd::map。各ペアのハッシュを格納するようにコードを変更してから、生成する一意のハッシュ値の数を確認できます。

于 2011-11-07T02:46:38.297 に答える