C++: какой алгоритм выбрать для быстрой вставки уникальных пар u64?
Мне надо хранить уникальные пары с uint64_t внутри, должна быть очень быстрая вставка в контейнер и первый элемент в паре всегда меньше второго. Какой алгоритм тут эффективнее?
Сейчас использую std::unordered_set с такой хэш-функцией:
std::uint64_t hasher(const std::pair<std::uint64_t, std::uint64_t> src) { return (src.first << 32) + src.second; } |
std::uint64_t hasher(const std::pair<std::uint64_t, std::uint64_t> src) { return (src.first << 32) + src.second; }
Сомневаюсь что не будет коллизий хэшей, но unordered_set наверное умеет с этим бороться. Можно ли сделать что-то получше?
Дополнительно:
Вам только вставка нужна? Что вы еще делаете с контейнером-то? Так-то, vector::push_back самое быстрое будет.
Если бы лимитов не было то ОДЗ для пары uint64_t составляло бы целое число в 128 бит.
А если включить лимит то эти 128 бит надо поделить на два в диапазоне. Тоесть 127 бит.
Как взять верхний треугольник из квадратной матрицы всех сочетаний.
Вобщем берите любую хеш-функцию которая работает с uint64_t. Ну для пары интов можно сделать
их XOR.
А вот внизу уже один чел подобное прелагает. Но он делает хитрее. По разному их обрабатывает.
Видимо боится корреляций. О которых вы не сказали. Ну и бох с ними. Может их и нету.
Скорее всего, действительно, unordered_set - лучший вариант. Но, возможно, вам можно взять вектор и потом его один раз отсортировать, например. Зависит от того, как много у вас чисел приходит, как много там повтороений, и что вы с ними потом делаете.
структуры данных. По аналогии с BSP-Tree, Oct-Tree. Но эти что я перечислил - статичны.
А вам нужно поискать такоечто очень быстро может модифицироваться во времени.
Как они называются я не знаю. Но думаю что искать в этом направлении.
Тогда никакие хеш-таблички вам будут не нужны. Тем более что речь идет о координатах.
А это - непрерывность. Скорость. Ускорение. Гравитация и прочие штуки которые надо решать
как непрерывные величины.
Вообще, непонятно. По идее вы в дерево кладете объекты при создании. Они же у вас не все новые 250 раз в секунду? Поэтому вставка туда, хоть и тяжелее unordered_set, не должна тормозить все программу.
И пересекаться у вас все 20к объектов каждый с каждым не должны - разбивайте пространство тщательнее. А еще, вы в дереве никак не можете получать повторяющиеся пары! Ну, кроме того, что вы каждую пару получите ровно 2 раза, но это надо просто отбросить те, у которых первое число больше второго. Вы это, кажется, уже делаете.
А еще, Если у вас уже отдельный вектор есть, то вы вместо указателей используйте индексы в нем. Можно вместо 64бит получить 32 или даже 16. Если все же останетесь с вашими парами, то одно int32 число, кодирующее пару индексов будет быстрее вставлять куда угодно чем пару int64.
Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.
Пока нет других ответов. Будьте первым, кто поможет автору.
Ответить на вопрос
Для быстрой вставки уникальных пар u64 в C++ можно использовать хэш-таблицу (unordered_map) или множество (set).
Хэш-таблица позволяет быстро найти элемент по ключу и вставить новый элемент. Для этого необходимо использовать функцию хэширования, которая преобразует ключ в индекс массива. Однако, при коллизиях (когда два ключа хэшируются в одно и то же значение) может возникнуть необходимость в дополнительных операциях.
Множество (set) также обеспечивает уникальность элементов и позволяет быстро искать и вставлять элементы. Однако, в отличие от хэш-таблицы, множество хранит элементы в отсортированном порядке, что может повлиять на скорость операций вставки.
В обоих случаях необходимо правильно выбрать хэш-функцию или оператор сравнения, чтобы обеспечить эффективную работу структуры данных.
Например, вот как можно использовать хэш-таблицу для вставки уникальных пар u64:
#include #include int main() { std::unordered_map<std::pair, bool> uniquePairs; // Вставка уникальных пар uniquePairs[{1, 2}] = true; uniquePairs[{3, 4}] = true; uniquePairs[{1, 2}] = true; // не будет вставлено, так как пара уже существует return 0; }
Или использовать множество:
#include #include int main() { std::set<std::pair> uniquePairs; // Вставка уникальных пар uniquePairs.insert({1, 2}); uniquePairs.insert({3, 4}); uniquePairs.insert({1, 2}); // не будет вставлено, так как пара уже существует return 0; }
Выбор между хэш-таблицей и множеством зависит от конкретной задачи и требований к производительности. В обоих случаях необходимо обеспечить уникальность ключей и правильную реализацию хэш-функции или оператора сравнения.