На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: Qraizer
  
> Ускорить процесс формирования массива граней сетки (с++)
    Привет.
    Формирую массив граней сетки. Каждая из граней имеет 4 узла (узел - long long число).
    При вставке следующей грани мне нужно максимально быстро определять была ли такая грань уже добавлена в набор.
    Подскажите, пожалуйста, способ быстрого определения вхождения грани в набор.
    Требование: без boost-а, и используя только <= 11 стандарт С++.
    Спасибо.

    Добавлено
    Смотрю пока в сторону реализации универсального хэша для кортежей. Вариант нашел на просторах интрнета.
    По скорости еще не оценивал такой подход т.к. код на работе.
    У меня есть другие варианты или этот наиболее оптимальный?

    ExpandedWrap disabled
      #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;
      }
    Сообщение отредактировано: gordey -
      Из универсальных этот – да, наиболее оптимальный. Он лишь требует, чтобы для элементов хеша была определена операция ^, и просто итерируется по кортежу. (Сам алгоритм итерации на ошибки досконально не проверял.) Остальное выполнено вполне на уровне, сами итерации разгребаются в компайл-тайм.
      В твоём случае, когда элементами являются просто целые, не думаю, что имеет смысл искать альтернативы. Операция ^ для них в ран-тайм должна быть вполне эффективна. Стоит лишь рассмотреть вопрос об эффективности подобного хеша в целом. Обычный ^ даёт весьма средненько малую вероятность коллизий, поэтому выиграв на вычислении хеша можно потерять на коллизиях.
        Я вот только не понял, зачем определять универсальную функцию для произвольного кортежа, если грань описывается набором из четырёх целых (пусть даже long long) чисел.

        Второе, просто хэш-функция здесь чревата возникновением ошибок. Придётся реализовывать хэш-таблицу (при совпадении хэшей надо обязательно проверять сами грани). А значит хэш-функция должна допускать ещё и свёртку (уменьшение диапазона) с хорошими свойствами по коллизиям.
          Я для примера привел 4-х узловую грань. На самом деле грани могут содержать другое число узлов.
            Сейчас я использую следующий подход.
            Может у Вас есть соображения по ускорению данного подхода?

            При добавлении новой грани я проверяю ее наличие в массиве граней. Если грань еще не добавлялась, то я для каждого узла грани запоминаю ее идентификатор.

            ExpandedWrap disabled
              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.

            ExpandedWrap disabled
              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".
            Сообщение отредактировано: gordey -
              Цитата 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
                Я работаю с сетками разных типов, с двумерными и объемными, имеющими разные типы ячеек. У оних ячеек будет 3 грани, а у других 4 или больше. Грани могут иметь разное число узлов.
                Я разработал сеточные структуры данных, в которые записываю информацию о сетках при чтении различных файлов, содержащих сеточную информацию.

                Сейчас я занят поиском оптимального пути (по потреблению ОП и по скорости) определения вхождения грани сетки в формирующийся массив граней.
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0316 ]   [ 16 queries used ]   [ Generated: 28.03.24, 20:04 GMT ]