Более эффективная структура как unordered_map<pair <int, int>, int>

У меня около 20 000 000 pair<int, int> который мне нужно связать с ints. Я сделал это с unordered_map<pair<int, int>, int>, Профилирование моего алгоритма показывает, что проверка, существует ли запись или нет

bool exists = myMap[make_pair(a, b)] != NULL

является узким местом производительности. Я думал, что получение этой информации из unordered_map будет очень быстро, так как это O (1). Но постоянное время может быть медленным, если постоянная большая...

Моя хеш-функция

template <>
struct tr1::hash<pair<int, int> > {
public:
        size_t operator()(pair<int, int> x) const throw() {
             size_t h = x.first * 1 + x.second * 100000;
             return h;
        }
};

Вы знаете лучшую структуру данных для моей проблемы?

Очевидно, что я не могу просто хранить информацию в матрице, поэтому объем памяти не поместится ни в один из существующих компьютеров. Все, что я знаю о распределении, это то, что myMap[make_pair(a, a)] не существует для любого a, И это все ints находятся в непрерывном диапазоне от 0 до около 20000000.

Думайте об этом как о разреженной матрице размером 20 000 000x20 000 000, содержащей около 20 000 000 записей, но не на главной диагонали.

Предложение

Был бы vector<pair<int, int>>* (массив с N записями) ожидается быстрее? Поиск для a будет тривиальным (просто индекс массива), а затем я бы перебрать вектор, сравнивая first значение пары в b,

БОЛЬШОЕ ОБНОВЛЕНИЕ

Я загрузил необработанные данные, чтобы вы могли видеть структуру.

Источник

5 ответов

Решение

Как предположить, я пошел с vector<pair<int, int>>* с N записей. Это примерно на 40% быстрее, чем unordered_map,

Источник

Вы пытались использовать myMap.find(make_pair(a,b)) != myMap.end()? operator[] создает элемент, если он не существует. Я бы ожидал find быть быстрее.

Источник

Прежде всего, myMap[make_pair(a, b)] != NULL не делает то, что вы думаете, что делает. Он вставляет пару, если она не существует, и сравнивает сопоставленное значение с 0 (что NULL расширяется до). Он вообще не проверяет существование. (Обратите внимание, что в современном C++ вы никогда не должны использовать NULL, Используйте 0 для чисел и nullptr для указателей).

Что касается основной темы, ваша хеш-функция не кажется слишком хорошей. Не забывайте, что арифметика на intс сделано в ints. Так как на большинстве компиляторов int является 32-разрядным, его максимальное значение составляет чуть более 2000 000 000. Таким образом, 20 000 000 * 10 000 намного больше, что приводит к переполнению (и неопределенному поведению).

Учитывая количество ваших данных, я предполагаю, что вы на 64-битной платформе, что означает size_t длиной 64 бита. Таким образом, вы можете получить лучшие результаты с помощью хэш-функции, например:

size_t operator()(pair<int, int> x) const throw() {
     size_t f = x.first, s = x.second;
     return f << (CHAR_BIT * sizeof(size_t) / 2) | s;
}

Это должно привести к значительно меньшему количеству столкновений (и определенному поведению) по сравнению с тем, что вы имеете сейчас.

Если это не поможет, вы также можете попробовать двухэтапный подход:

std::unordered_map<int, std::unordered_map<int, int>>

Поиск по x.first сначала, потом x.second, Я не знаю, поможет ли это; измерить и увидеть.

Источник

Главное, безусловно, избегать добавления элементов по умолчанию при каждом поиске:

bool exists = myMap[make_pair(a, b)] != NULL; // OUCH

bool exists = myMap.find(make_pair(a, b)) != myMap.end();  // BETTER

iterator i = myMap.find(make_pair(a, b);
if (i != myMap.end()) ... else ...;      // MAY BE BEST - SEE BELOW

И большой вызов хэш... вау-ху! Это может стоить того, но многое зависит от того, как распределены числа в парах и от реализации. std::hash (что часто бывает сквозным!)

    size_t operator()(pair<int, int> x) const throw() {
         size_t hf = std::hash(x.first);
         return (hf << 2) ^ (hf >> 2) ^ std::hash(x.second);
    }

Вы также можете найти его быстрее, если заменить пару на int64_ts, так что ключевые сравнения - это, безусловно, простые целочисленные сравнения, а не каскадные.

Кроме того, что ты делаешь после теста на существование? Если вам нужно получить доступ / изменить значение, связанное с тем же ключом, вам следует сохранить итератор find возвращается и избегайте другого поиска.

Источник

Я предлагаю вам протестировать с лучшей хэш-функцией. Вы можете найти примеры, если будете искать здесь на SO, но это одна из возможных реализаций.

struct pair_hash {
    template <typename T1, typename T2>
    size_t operator()(const std::pair<T1, T2> &pr) const {
        using std::hash;
        return hash<T1>()(pr.first) ^ hash<T2>()(pr.second);
    }
};
Источник
Другие вопросы по тегам