c++ - 获取大数据范围的数据容器

Question

我有一个 3D 对象，它有超过 100000 个点，这些点有一个 id 和 x,y,z 位置值。我需要找到特定 x 范围的点 ID，其中 y 和 z 值是静态的。

例如 -

 ---- --- --- --- 
| Id | x | y | z |
|----|---|---|---|
|    |   |   |   |

如果我需要找到 (x,y,z) 之间的点 id

• p1 - 0.1 ,0.23, 0.78
• p2 - 123.0 ,0.23, 0.78

我应该使用什么样的数据容器来有效地实现这一点？

如有任何帮助，我们将不胜感激。

Answer 1

由于 2 个坐标始终是静态的，您可以为每个坐标使用一个简单的排序数组，或者一个平衡的 BST (或skip list/B+ tree/...)如果你还需要支持高效的添加/删除。 (考虑到这一点，跳过列表可能更容易实现，只需找到范围内的第一个点，然后迭代直到超出范围)。

这将花费 O(logN) 来查询(如果您需要实际点它的 O(logN+k)，其中 k是点)和 O(NlogN) 初始化。

因此，算法将是:

1. 识别非静态点
2. 高效搜索范围内的“最低”点
3. 高效搜索范围内的“最大”点
4. 返回它们之间的所有点数。

2+3的复杂度是O(logN)，4的复杂度是O(k)，其中k是返回点数(如果您需要实际点数，而不是它们的特定聚合，则无法避免)。