搜索点数组的更好算法？

Question

我有一个结构数组，其中每个结构都是一个二维位置（一对 32 位值）。此数组用于跟踪地图上的兴趣点。

struct Point {
    int x;
    int y;
};

// ...

struct Point pointsOfInterest[1024];

问题是，这些兴趣点在不断变化，这意味着数组中的条目经常被添加或删除。最重要的是，每个报告的兴趣点可能已经存在于数组中，所以我不能在不检查它们是否已经存在的情况下盲目添加新的。

目前数组未排序（新条目添加到末尾，交换和弹出以删除），我遍历整个列表以找到要删除或重复检查的条目。我想知道我有什么选择可以加快这个过程。

在其他语言中，这是我分解字典或哈希集的地方。 C 中都不存在，所以我必须权衡添加类似内容的复杂性。
我考虑过对列表进行排序（即首先按 X，然后按 Y）。但是鉴于更新的频率，我觉得我会比迭代时更频繁地抖动 table。但是我对排序算法的了解很少。
某种二叉树在这里会更好吗？或者我会再次花费所有时间来重新平衡树吗？
从理论上讲，考虑到这些算法的（感知到的）复杂性，是否存在一个阈值，低于该阈值线性搜索仍然是一个可行的选择？

我假设这是一个已知的已解决问题，所以我希望在我花大量时间重新发明轮子和测试可能的解决方案之前指出正确的方向。

Answer 1

除了琐碎的情况，通常很难预测性能提升在哪里。这就是为什么您应该在更改前后对代码进行基准测试。同时分析您的代码以找出它花费最多时间的地方。

In other languages, this is where I break out a dictionary or hash set. Neither exist in C, so I have to weigh the complexity of adding something like that.

TBH，实现起来并不复杂。如果您需要性能，那是不费吹灰之力的。但不保证会更快

I've considered sorting the list (i.e. first by X, then Y). But given the frequency of updates, I feel like I'll be thrashing the table far more than when iterating. But my knowledge of sorting algorithms is minimal.

这很可能不是最优的。但你可以试试看。而且您不需要进行完整排序。只需进行二进制搜索并移动后面的所有内容。

Would a binary tree of some sort be any better here? Or would I again be spending all of my time re-balancing the tree?

只有一种方法可以找出答案。尝试并进行基准测试。

Theoretically, given the (perceived) complexity of these algorithms, is there a threshold below which a linear search remains a viable option?

我肯定有，但这些总是要与现实保持平衡。就像对性能有很大影响的缓存未命中一样。可能会改善缓存友好性的一件事可能正在改变

struct Point {
    int x;
    int y;
};

struct Point pointsOfInterest[1024];

至

int pointsOfInterest[2][1024];

并为 x 或 y 使用第一个索引。可能有效，具体取决于您对数据的处理方式。我想这对你的情况不起作用，但它可以加速一个只在一个维度上循环的函数。

搜索点数组的更好算法？

Better algorithm for searching through an array of points?

arrays

c

search

c11