Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.143.239] |
|
Сообщ.
#1
,
|
|
|
Привет.
Формирую массив граней сетки. Каждая из граней имеет 4 узла (узел - long long число). При вставке следующей грани мне нужно максимально быстро определять была ли такая грань уже добавлена в набор. Подскажите, пожалуйста, способ быстрого определения вхождения грани в набор. Требование: без boost-а, и используя только <= 11 стандарт С++. Спасибо. Добавлено Смотрю пока в сторону реализации универсального хэша для кортежей. Вариант нашел на просторах интрнета. По скорости еще не оценивал такой подход т.к. код на работе. У меня есть другие варианты или этот наиболее оптимальный? #include <tuple> #include <cstring> #include <functional> #include <type_traits> size_t hash_combiner(size_t left, size_t right) //replacable { return left^right;} template<int index, class...types> struct hash_impl { size_t operator()(size_t a, const std::tuple<types...>& t) const { typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype; hash_impl<index-1, types...> next; size_t b = std::hash<nexttype>()(std::get<index>(t)); return next(hash_combiner(a, b), t); } }; template<class...types> struct hash_impl<0, types...> { size_t operator()(size_t a, const std::tuple<types...>& t) const { typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype; size_t b = std::hash<nexttype>()(std::get<0>(t)); return hash_combiner(a, b); } }; namespace std { template<class...types> struct hash<std::tuple<types...>> { size_t operator()(const std::tuple<types...>& t) { const size_t begin = std::tuple_size<std::tuple<types...>>::value-1; return hash_impl<begin, types...>()(1, t); //1 should be some largervalue } }; } #include <iostream> int main() { typedef std::tuple<int, char, float> T; T t(14, 'A', 3.14); std::cout << std::hash<T>()(t); return 0; } |
Сообщ.
#2
,
|
|
|
Из универсальных этот – да, наиболее оптимальный. Он лишь требует, чтобы для элементов хеша была определена операция ^, и просто итерируется по кортежу. (Сам алгоритм итерации на ошибки досконально не проверял.) Остальное выполнено вполне на уровне, сами итерации разгребаются в компайл-тайм.
В твоём случае, когда элементами являются просто целые, не думаю, что имеет смысл искать альтернативы. Операция ^ для них в ран-тайм должна быть вполне эффективна. Стоит лишь рассмотреть вопрос об эффективности подобного хеша в целом. Обычный ^ даёт весьма средненько малую вероятность коллизий, поэтому выиграв на вычислении хеша можно потерять на коллизиях. |
Сообщ.
#3
,
|
|
|
Я вот только не понял, зачем определять универсальную функцию для произвольного кортежа, если грань описывается набором из четырёх целых (пусть даже long long) чисел.
Второе, просто хэш-функция здесь чревата возникновением ошибок. Придётся реализовывать хэш-таблицу (при совпадении хэшей надо обязательно проверять сами грани). А значит хэш-функция должна допускать ещё и свёртку (уменьшение диапазона) с хорошими свойствами по коллизиям. |
Сообщ.
#4
,
|
|
|
Я для примера привел 4-х узловую грань. На самом деле грани могут содержать другое число узлов.
|
Сообщ.
#5
,
|
|
|
Сейчас я использую следующий подход.
Может у Вас есть соображения по ускорению данного подхода? При добавлении новой грани я проверяю ее наличие в массиве граней. Если грань еще не добавлялась, то я для каждого узла грани запоминаю ее идентификатор. faceId = links->GetFace(mesh, face->GetPointIds()); if (faceId == -1) { links->m_pLinks[face->GetPointIds()->GetId(0)].push_back(faceId); links->m_pLinks[face->GetPointIds()->GetId(1)].push_back(faceId); links->m_pLinks[face->GetPointIds()->GetId(2)].push_back(faceId); links->m_pLinks[face->GetPointIds()->GetId(3)].push_back(faceId); } else { } Ниже привожу код метода поиска грани GetFace. lppIdType GetFace( lppMesh *mesh, vtkIdList *ptIds ) { lppIdType pointId = -1, npts = -1, *pts = nullptr; bool find = true; // Бегаем по узлам грани for ( lppIdType i = 0; i < ptIds->GetNumberOfIds(); ++i ) { pointId = ptIds->GetId( i ); // Перебираем грани для узла for (size_t j = 0; j < m_pLinks[pointId].size(); ++j) { mesh->GetFace(m_pLinks[pointId][j], npts, pts); if (npts == ptIds->GetNumberOfIds()) { find = true; // Проверяем совпадение узлов у граней for (lppIdType n = 0; n < npts; ++n) { if (ptIds->IsId(pts[n]) == -1) { find = false; break; } } if (find) return m_pLinks[pointId][j]; } } } return -1; } И по измерениям скорости, сделанными на скорую руку, этот способ выигрывает у связки "универсальных хэш + unordered_map". |
Сообщ.
#6
,
|
|
|
Цитата gordey @ И по измерениям скорости, сделанными на скорую руку, этот способ выигрывает у связки "универсальных хэш + unordered_map". Ничего удивительного Хэш довольно медленная операция. Вполне возможно что он проигрывает прямому методу. Правда в вашем случае похоже где-то баг. Тут нужны точные параметра теста. Может у вас мэш на 1 миллион граней, а можете на миллиард. Просто одно дело ребер>1 миллиона и граний <100 шт. Совершенно другое дело ребер<=4 и граний > 1 миллиона. И с чего вдруг у вас у граней больше 4-х ребер? Я к чему вы слишком плохо описали задачу. Откуда берутся эти грани и зачем их куда-то добавлять? Может тут Spatial Hash использовать? https://habr.com/ru/post/182998/ Вон NVidia их использует https://github.com/NVIDIAGameWorks/PhysX-3....SpatialHash.cpp |
Сообщ.
#7
,
|
|
|
Я работаю с сетками разных типов, с двумерными и объемными, имеющими разные типы ячеек. У оних ячеек будет 3 грани, а у других 4 или больше. Грани могут иметь разное число узлов.
Я разработал сеточные структуры данных, в которые записываю информацию о сетках при чтении различных файлов, содержащих сеточную информацию. Сейчас я занят поиском оптимального пути (по потреблению ОП и по скорости) определения вхождения грани сетки в формирующийся массив граней. |