Уникальный ключ для трехмерных координатных вставок для вставки в std :: unordered_set

Question

У меня есть поток трехмерных целочисленных координат, которые соответствуют вокселям и, таким образом, выровнены по сетке. Я хочу выяснить, существует ли текущий обработанный триплет для фильтрации дубликатов. Мне удалось построить простое решение моей проблемы с std::set. Пусть x y z будет 3 int, а registry будет std::set< std::array<int, 3> >. Я сделал функцию, которая возвращает bool вот так

std::array<int, 3> key = {x, y, z};
return registry.insert(key).second;

Но это далеко не оптимизировать с точки зрения времени вычислений. Читая документацию и темы SO, я понимаю, что unordered_set должно быть более подходящим. На самом деле здесь не нужно ничего сортировать. Кроме того, я предполагаю, что использование array<int,3> в качестве ключа неэффективно для сравнения во время insert.

Для unordered_set требуется хеш-функция. Изучая хеш-функции, которые я нашел boost::hash_combine, а также другие варианты.

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

Answer 1

Я отвечаю на свой вопрос. Мой первоначальный вопрос был некорректным, но благодаря @Damien я понял, как хеш был использован в std::unordered_*. Я использовал boost

#include <boost/functional/hash.hpp>

И я определил свой registry следующим образом

typedef std::array<I32,3> Array;
std::unordered_set<Array, boost::hash<Array> >

И я получил ~ 33% времени вычислений.

Answer 2

Уууууууу не нужно использовать вектор для подобных вещей.Он динамически распределяется.Вы уничтожаете потенциал кеша вашей программы.

Всего три int, поэтому просто создайте struct, в котором три int.Или передайте std::array<int, 3>.

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

Если это все еще слишком медленно, то вы можете рассмотреть возможность появленияс надлежащим алгоритмом для этого, видя, что и set, и unordered_set по-прежнему будут динамически распределять узлы.Это всего лишь один уровень косвенности, а не два, которые у вас есть сейчас, но ноль лучше, чем никакой.