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

Question

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

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

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

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

Очевидно, что 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?

Можно ли как-нибудь ускорить этот метод?

10

c++performance stl unordered-set vector

Решение

Другие решения

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

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

1

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

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

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

0

Я столкнулся с подобной проблемой, когда линейный поиск выполняется быстрее, чем поиск с хэш-плюсом (поддержка первого ответа Марка).

Я пытаюсь использовать BFS для улучшения вокселизации ЦП меша. std::unordered_set используется для отметки посещенных вокселей. Тем не мение, unordered_set на 100% медленнее, чем линейная итерация пространства. При сравнении профиля я обнаружил, что линейный поиск быстрее, если отношение активных вокселей ко всем посещенным вокселям выше, чем 3%, В противном случае BFS с unordered_set лучше.

0

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

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

Ну, так как метод find в конечном итоге будет проходить через значительное количество элементов, это, вероятно, причина …

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

-2

Источник

Accepted Answer

У меня есть две возможности:

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

4