用于搜索arrays中的3D坐标的高效算法
我有一个大的数组（> 10 ^ 5个条目）的3D坐标r =（x，y，z），其中x，y和z是浮点数。 这是搜索数组中给定坐标r’并给出数组索引的最有效方法。 注意，r’可能没有给出与r相同的精度; 比方说，如果数组存储坐标（1.5,0.5,0.0）并且r’给出为（1.49999,0.49999,0.0），则算法应该正确地选择坐标。 我正在用C开发代码。
为此目的，如何使用哈希表的O（1）搜索function？ 由于与准确性相关的问题，将坐标转换为字符串是不可能的。 是否有任何特定的数据结构有助于O（1）算法？
谢谢
OnRoadCoder
检查已在某些RDBMS上实现的R-tree ，如SQLite，以及（我认为）Postgres
为了在您描述时进行“模糊”搜索（因此您可以支持轻微的不准确性），您将不得不牺牲O（1）算法。
话虽这么说，但有一些非常好的算法。 空间分区 （例如使用八叉树或KD树 ）是一种常见的流行选项。
如果值的范围有限，请选择所需的精度。 现在，密钥（1,2,3）将指向曼哈顿距离3 * d（d = 0.5？ – 取决于细节）的所有点的链接列表（或更高级的数据结构）（1， 2,3）。 您最了解您的应用程序，因此您可以更好地选择d。 优化方法取决于数据的分布方式。
编辑：
这里的弱点是 – 如果你有很多点集中在一个立方体中，那么使用关于保证O（1）的哈希表可以做的很少…更像是O（n）:)
某种基于树的数据结构可以保证O（log n）。
你问的问题听起来像是最近邻搜索 。 一种方法可能是编码kd-tree （或任何基于空间分区的技术）并使用它来查找距离查询最近的点。 但是你也可以使用基于散列的方法，它基本上是Ipthnc的答案描述的，但是试图避免退化情况的不良性能。