вставка unordered_map останавливается

Question

По сути, у меня есть 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++ ;
        }
    }
}

EDIT: Я на самом деле добавляю ближе к 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

Answer 1

Лучше использовать решение Boost 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

Попробуйте взглянуть на unordered_map :: load_factor ().Результат этого вызова в идеале должен быть <1.0.Если оно больше 1,0, то ваша хеш-функция, вероятно, хитрая.Вы должны использовать hash_combine вместо XOR для вашей пары. </p>

Answer 3

Вы пытались использовать reserve() для предварительного распределения достаточного количества сегментов для всех ваших пар? Добавление такого количества пар может вызвать многократные изменения размера (и перефразировки).

Следующее, что я бы проверил, это ваша хеш-функция. Это выглядит немного подозрительно, и если вы получаете много коллизий хешей, многие получают кучу переполненных блоков, которые замедляют поиск для каждой вставки - в этом случае вам лучше использовать std::map. Вы можете изменить свой код для хранения хэша каждой пары, а затем проверить количество генерируемых вами уникальных хеш-значений.