1

专业人士，我需要以下一些性能意见：

第一个问题：

我想将对象存储在 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. 离位置 x,y,z 最近的非空 ObjC 桶是哪个？

PS：

我之前也考虑过基于树的数据结构，阅读最近邻方法。由于我的数据非常有规律，我原以为我会保存所有将单元格划分为更小块的树形结构，然后只制作最终叶子的静态 3D 网格。这就是我来询问在此处存储此网格的最佳方式的方式。与此相关的问题，如果我有map<int, Obj>一个快速的方法来询问“所有具有 780 和 790 之间键的对象”？或者是构建上述树的最快方式？

编辑

我最终选择了具有 fortran 排序的 3D boost::multi_array。这有点像我的世界使用的块游戏。这有点像使用具有固定叶子大小和固定叶子数量的 kd-tree？现在工作得很快，所以我对这种方法很满意。

4

1 回答 1

1

回答第一个问题

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

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

B）如果您希望尽可能小，请使用哈希映射，并使用针对空间优化的映射。这将导致空间O(N)，其中N是元素的数量。这是比较几个哈希映射的基准。我在google::sparse_hash_map方面取得了很好的经验，这是迄今为止我见过的最小的常量开销。另外，很容易将它添加到您的构建系统中。

如果您需要速度和小数据的混合，或者事先不知道每个维度的大小，也可以使用哈希图。

回答第二个问题

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

  1. 离位置 x,y,z 最近的非空 ObjC 桶是哪个？

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

于 2014-09-19T12:38:30.533 回答