c++ - 返回同时存在于列表 A 和列表 B 中的 x,y 坐标的最快方法是什么？

Question

我有两个 x,y 坐标列表(列表 A 和列表 B)，其中 0 < x < 4000、0 < y < 4000，它们始终是整数。我需要知道两个列表中的坐标是什么。对于如何解决这个问题，您有什么建议？

我一直在考虑将列表表示为两个位网格，并可能按位进行？

列表 A 大约有 1000 个条目，并且可能每 10,000 个请求更改一次。列表 B 的长度会有很大差异，并且每次运行时都会有所不同。

编辑:我应该提到没有坐标会出现在列表中两次；例如，1,1 不能多次出现在列表 A 中。

Answer 1

如注释中所述，将 (x,y) 表示为单个 24 位数字。

按数字顺序维护 A(你说它变化不大，所以这应该几乎没有任何成本)。

对每个 B 在列表中进行二分查找。由于 A 大约有 1000 个项目，因此您最多需要 10 次整数比较(在最坏的情况下)来检查成员资格。

如果您有更多的内存(大约 2MB)可以玩，您可以创建一个位 vector 来支持所有可能的 24 位数字，然后对每个项目执行一个位操作来测试成员资格。因此，如果值存在(否则为 0)，A 将由带有位集的单个 2^24 位数字表示。要测试成员资格，您只需使用适当的位和操作即可。