c - 将相同的函数应用于C中数组中的每个元素

Question

假设我需要找到从一个 (x,y) 坐标到百万坐标数组中每个坐标的欧几里德距离，然后选择距离最小的坐标。

目前我循环通过百万元素数组，计算跟踪最小值的距离。有没有办法我可以以不同的方式更快地做到这一点。

谢谢

Answer 1

您可以通过使用更复杂的数据结构（例如kd 树）来显着改进您的算法。尽管如此，如果您期望做的是简单地搜索一次最近的邻居，那么您不可能比迭代所有点更好。

您可以做的是优化计算距离的函数，并且（如评论中所述）您可以省略平方根，因为比较两个非负整数的平方与比较值相同。

Answer 2

我从这个问题中了解到的是你想找到最接近的一对点。有一个算法最接近点对问题来解决这个问题。

一组点的最近对：

• 将集合划分为两个大小相等的部分l，并递归计算每个部分的最小距离。
• 让d是两个最小距离中的最小值。
• 消除距离大于 d 的点l
• 根据 y 坐标对剩余点进行排序
• 以 y 顺序扫描剩余的点并计算每个点到其五个邻居的距离。
• 如果这些距离中的任何一个小于d然后更新d。

整个算法 Closest Pair 需要O(logn*nlogn)=时间。 O(nlog2n)

我们可以通过减少在步骤 4 中实现 y 坐标排序所需的时间来稍微改进该算法。这是通过要求在步骤 1 中计算的递归解决方案返回按 y 坐标排序的点来完成的。这将产生两个排序的点列表，只需在步骤 4 中合并（线性时间操作）即可产生完整的排序列表。因此，修改后的算法涉及进行以下更改：

• 第 1 步：将集合划分为...，并递归计算每个部分的距离，返回每个集合中的点按 y 坐标排序。
• 第四步：及时将两个排序后的列表合并为一个排序后的列表O(n)。

因此，合并过程现在由线性时间步长控制，从而产生一种O(nlogn)算法，用于找到平面中一组点的最近对。

Answer 3

您可以通过首先检查沿 x 和沿 y 的距离是否小于您存储的最后一个距离（平方）来节省大量时间。如果它是真的，那么你继续计算距离（平方）。当然，您节省的时间取决于积分的分配方式。