3D-сетка ячеек: вложенный std :: vector vs std :: unordered_map

Плюсы, мне нужны некоторые оценки производительности со следующим:

1-й вопрос:

Я хочу хранить объекты в трехмерной сеточной структуре, в целом она будет заполнена на ~ 33%, то есть 2 из 3 точек сетки будут пустыми.
Короткое изображение для иллюстрации:

введите описание изображения здесь

Возможно вариант А)

vector<vector<vector<deque<Obj>> grid;// (SizeX, SizeY, SizeZ);
grid[x][y][z].push_back(someObj);

Таким образом, у меня будет много пустых заявок, но доступ к одному из них будет быстрым, не так ли?

Другой вариант Б) будет

std::unordered_map<Pos3D, deque<Obj>, Pos3DHash, Pos3DEqual> Pos3DMap;

где я добавляю&удалить запросы, когда данные добавлены / удалены. Возможно, используется меньше памяти, но, возможно, менее быстро? Как вы думаете?

2-й вопрос (продолжение)

Что если бы у меня было несколько контейнеров в каждой позиции? Скажем, 3 сегмента для 3 разных объектов, скажем, типы объектов ObjA, ObjB, ObjC на точку сетки, тогда мои данные по существу станут 4D?

Еще одна иллюстрация:
введите описание изображения здесь

Используя опцию 1B, я мог бы просто расширить Pos3D, чтобы включить номер корзины, чтобы учесть еще более редкие данные.
Возможные запросы, которые я хочу оптимизировать для:

  1. Дайте мне все объекты из ObjA-ведер из всей структуры
  2. Дайте мне все объекты из ObjB-ведер для набора
    грид-позиции
  3. Какой ближайший непустой ObjC-контейнер
    положение x, y, z?

PS:

Я также думал о древовидной структуре данных, читая о подходах к ближайшему соседу. Поскольку мои данные настолько регулярны, я думал, что сохраню все деление клеток на деревья, разделив их на более мелкие части, и просто сделаю статическую 3D-сетку из конечных листьев. Вот как я пришел, чтобы спросить о наилучшем способе хранения этой сетки здесь.
Вопрос, связанный с этим, если у меня есть map<int, Obj> Есть ли быстрый способ запросить «все объекты с ключами от 780 до 790»? Или это самый быстрый способ построения вышеупомянутого дерева?

РЕДАКТИРОВАТЬ

Я закончил с 3D Boost :: Multi_array, который имеет порядок Fortran. Это немного похоже на такие игры, как майнкрафт. Что немного похоже на использование kd-дерева с фиксированным размером листьев и фиксированным количеством листьев? Работает довольно быстро, поэтому я доволен этим подходом.

1

Решение

Ответ на первый вопрос

Как отметил @Joachim, это зависит от того, предпочитаете ли вы быстрый доступ или небольшие данные. Примерно, это соответствует вашим вариантам А и В.

A) Если вам нужен быстрый доступ, используйте многомерный std::vector или массив, если хотите. std::vector облегчает обслуживание при минимальных накладных расходах, поэтому я бы предпочел это. С точки зрения пространства он потребляет O (N ^ 3) пространство, где N количество точек сетки вдоль одного измерения Чтобы получить максимальную производительность при переборе данных, не забудьте разрешить индексы в обратном порядке, как вы его определили: сначала внутри, а затем последним.

B) Если вы хотите, чтобы все было как можно меньше, используйте хэш-карту и используйте карту, оптимизированную для пространства. Это привело бы в космос НА), с N быть количество элементов. Вот эталонный тест сравнивая несколько хеш-карт. Я сделал хороший опыт с Google :: sparse_hash_map, который имеет наименьшие постоянные накладные расходы, которые я видел до сих пор. Кроме того, его легко добавить в систему сборки.

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

Ответ на второй вопрос

Я бы сказал, что ваши данные 4D, если у вас переменное число элементов, длинное 4-го измерения или фиксированное большое количество элементов. С опцией 1B) вы действительно добавите индекс сегмента, для 1A) вы добавите еще один вектор.

  1. Какой ближайший непустой контейнер ObjC находится в позиции x, y, z?

Эта операция обычно называется поиск ближайшего соседа. Вы хотите KDTree для этого. Существует libkdtree ++, если вы предпочитаете небольшие библиотеки. Иначе, Flann может быть вариант. Это часть Библиотека облаков точек которая решает много задач на многомерных данных и может также стоить посмотреть.

1

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


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector