c++ - 容器的 3D 网格:嵌套 std::vector 与 std::unordered_map

Question

专业人士，我需要以下方面的一些性能意见:

第一个问题:

我想在 3D-Grid-Structure 中存储对象，总的来说它会填充 ~33%，即 3 个网格点中有 2 个是空的。用于说明的短图:

也许选项A)

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

这样我会有很多空双端队列，但访问其中一个会很快，不是吗？

另一个选项 B) 是

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

添加/删除数据时，我在哪里添加和删除双端队列。可能使用的内存较少，但速度可能较慢？你怎么看？

第二个问题(跟进)

如果我在每个位置有多个容器怎么办？假设 3 个不同实体的 3 个桶，每个网格点的对象类型 ObjA、ObjB、ObjC，那么我的数据基本上变成了 4D？

另一个例子:

使用选项 1B，我可以扩展 Pos3D 以包含存储桶编号，以说明更稀疏的数据。我想优化的可能查询:

1. 给我整个结构中 ObjA 桶中的所有对象
2. 给我一组 ObjB 桶中的所有对象网格位置
3. 哪个是最近的非空 ObjC 桶位置 x,y,z?

附言:

我之前也考虑过基于树的数据结构，阅读最近邻方法。因为我的数据非常规则，所以我想我会保存所有将细胞划分成更小的部分的树构建，并只制作最终叶子的静态 3D 网格。这就是我来这里询问存储此网格的最佳方式的原因。与此相关的问题，如果我有 map<int, Obj>有没有一种快速的方法来询问“键在 780 到 790 之间的所有对象”？或者是构建上述树的最快方法？

编辑

我最终选择了具有 fortran 排序的 3D boost::multi_array。这有点像我的世界使用的 block 游戏。这有点像使用固定叶子大小和固定数量叶子的 kd 树？现在运行速度非常快，所以我对这种方法很满意。

Answer 1

第一个问题的答案

正如@Joachim 所指出的，这取决于您更喜欢快速访问还是小数据。大致上，这对应于您的选项 A 和 B。

A) 如果您想要快速访问，请使用多维 std::vector 或数组(如果您愿意)。 std::vector 以最小的开销带来更轻松的维护，所以我更喜欢这样。就空间而言，它消耗 O(N^3) 空间，其中 N 是沿一维的网格点数。为了在遍历数据时获得最佳性能，请记住按照您定义的相反顺序解析索引:最里面的第一个，最外层的最后一个。

B) 如果您反而希望保持尽可能小，请使用散列映射，并使用针对空间进行优化的映射。这将导致空间 O(N)，其中 N 是元素的数量。这是一个benchmark比较几个 HashMap 。我对 google::sparse_hash_map 有了很好的体验，这是迄今为止我所见过的最小的常量开销。另外，很容易将它添加到您的构建系统中。

如果您需要兼顾速度和小数据，或者事先不知道每个维度的大小，也可以使用 HashMap 。

第二个问题的答案

如果您在第 4 维上有可变数量的元素，或者有固定的大量元素，我会说您的数据是 4D。使用选项 1B) 你确实会添加桶索引，对于 1A) 你会添加另一个 vector 。

3. Which is the nearest non-empty ObjC-bucket to position x,y,z?

此操作通常称为最近邻搜索。你想要一个 KDTree。如果您更喜欢小型库，可以使用 libkdtree++。否则，FLANN可能是一个选择。它是 Point Cloud Library 的一部分它完成了很多关于多维数据的任务，也值得一看。