Std::vector быстрее, чем std:: unordered_set?

В моем пользовательском физическом движке самым большим узким местом является метод, который получает все тела из пространственного разбиения (2D-сетку) и возвращает коллекцию, содержащую только уникальные указатели на тело.

template<typename T, typename V> bool contains(const T& mContainer, const V& mValue)
{
    return std::find(std::begin(mContainer), 
                     std::end(mContainer), mValue) != std::end(mContainer);
}

const vector<Body*>& GridInfo::getBodiesToCheck()
{
    bodiesToCheck.clear();
    for(auto& query : queries)
        for(auto& body : *query)
            if(!contains(bodiesToCheck, body)) bodiesToCheck.push_back(body);
    return bodiesToCheck;
}

Использование профилировщика показывает, что узкое место находится в методе "содержит".

Очевидно, что a std::unordered_set будет "идеальным" решением. Однако это намного медленнее, чем текущее решение. Я также пробовал google::dense_hash_set, который быстрее, чем std::unordered_set, но все же медленнее, чем текущее решение.

const unordered_set<Body*>& GridInfo::getBodiesToCheck()
{
    bodiesToCheck.clear();
    for(auto& query : queries)
        for(auto& body : *query)
            /*if(!contains(bodiesToCheck, body))*/ bodiesToCheck.insert(body);
    return bodiesToCheck;
}

Почему "правильные" контейнеры медленнее, чем std::vector?

Есть ли способ ускорить этот метод?

Ответы

Ответ 1

Есть две возможности, о которых я могу думать:

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

Ответ 2

Если количество дублирующих тел не так велико по сравнению с остальными, одним из вариантов может быть просто подтолкнуть все ваши тела к вектору и затем удалить дубликаты. Но для этого потребуется std::sort, за которым следует erase(std::unique, end).

Но, может быть, стоит попробовать, учитывая, что ваш вектор, похоже, в любом случае переигрывает std::unordered_set, который не имеет такой же локальности и тривиального доступа, как a std::vector.

Ответ 3

Я не уверен, что правильно понимаю проблему, но похоже, что поиск будет медленнее на std::vector/std::find, но итерация может быть быстрее, чем с std::unordered_set. Если это так, и вы не ограничены ограничениями памяти, вы можете смешивать оба подхода:

Поддерживайте элементы std::unordered_set и std::vector с элементами. Посмотрите внутри std::unordered_set, чтобы определить, есть ли элемент уже там, если нет, добавьте его в оба контейнера. В конце итерации по std::vector.

Обратите внимание, что вы можете предоставить подсказки для обоих контейнеров относительно "ожидаемого" количества элементов, которые они будут содержать, и это уменьшит количество выделенных/переименований памяти.

Ответ 4

Вот что вы найдете в документации std:

"контейнеры unordered_set быстрее, чем установленные контейнеры для доступа к отдельным элементам по их ключу, хотя они, как правило, менее эффективны для итерации диапазона через подмножество их элементов."

Хорошо, так как метод find в конечном итоге пройдет через значительное количество элементов, что, вероятно, является причиной...

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