我有一个包含大约 700 000 个条目的数据集，每个条目都是一组 3D 坐标，具有名称、时间戳、ID 等属性。
现在我只是在读取坐标并将它们渲染为 OpenGL 中的点。但是，我想将每个点与其对应的属性相关联，并且我希望能够在运行时根据它们的属性对它们进行排序和挑选。我将如何以有效的方式实现这一目标？
我知道我可以将数据放入结构中并使用 stl 排序进行排序，但这是一个好的设计选择还是有更有效/优雅的方式来处理问题？
问问题
522 次
3 回答
2
我倾向于查看这些设计选择的方式是首先使用标准库容器之一（顺便说一句，如果您需要“只是”进行查找，则不一定要排序，但您需要一个允许查找的容器） ，然后检查这是否是解决问题的“足够有效”的解决方案。
您通常可以提出一个更高效、可能更优雅的自定义解决方案，但您往往会遇到两个问题：
1）您最终不得不实现某种类型的容器，与已经存在的易于理解和测试的容器相比，这将花费您在实现和调试方面的时间。大多数时候，您最好尝试解决手头的问题，而不是通过添加更多代码来扩大问题。
2）如果其他人必须在某个时候维护您的代码，他们很可能从设计和实现的角度都熟悉标准库组件，但他们不会熟悉您的自定义容器，从而增加了学习曲线。
于 2013-04-10T18:34:15.013 回答
0
如果您正在处理点云，请查看PCL，它可以为您节省大量时间和精力，而无需自己深入研究空间索引的复杂性。它还包括可视化。
于 2013-04-11T09:36:37.740 回答
0
如果您将点类的每个属性都视为向量的一个组成部分，那么您的选择过程就是一个区域查询。您的字符串属性等于某物的示例意味着该区域实际上是数据空间中的一条线。但是，不会对该选择中的其他属性进行任何排序，您必须自己实现它，但对于八叉树来说应该相对简单，它在有序区域中划分数据。
正如另一个答案所倡导的，首先尝试现有的标准解决方案。如果你能找到这些数据结构之一的现成实现：
- R-树
- KD树
- BSP
- 八叉树，或者更可能是四叉树或八叉树原理的n 维版本（我将在这里使用术语八叉树来表示一般数据结构）
然后去吧。这些是我推荐用于空间数据管理的数据结构。
您还可以使用能够处理空间数据的嵌入式 RDBMS（它们通常实现 R-tree 用于空间索引），但如果您的数据集不是动态的，它可能不会很有趣。
如果您的数据集在 10000 个条目范围内，那么按照今天的标准，它并没有那么大，因此使用更简单的结构就足够了。在那个范围内，我会先选择一个简单的std::vector，然后使用std::sortandstd::find过滤较小集合中的数据，然后对其进行排序。
我可能会在第二次尝试中尝试对查询最多的属性进行有序集或映射，然后进行一些基准测试以选择性能更高的解决方案。
对于更有效的一维索引算法（本质上，这就是集合和映射），您可能想尝试B-trees：google 提供了 C++ 实现。
我的第三次尝试将转向 OpenCL 解决方案（尽管如果您正在执行繁重的 OpenGL 渲染，您可能更喜欢在 CPU 上进行工作，但这取决于您的帧速率需求）。
如果您的数据集看起来更大，那么请考虑我最初列出的更复杂的解决方案之一。
无论如何，如果没有关于您的数据集以及您打算如何使用它的更多详细信息，将很难提供一个好的解决方案，所以我们能给出的唯一真正的建议是：尽你所能并进行基准测试。
于 2013-04-10T18:57:11.140 回答