boo*_*dle 5 c++ algorithm performance
我有两个x,y坐标列表(列表A和列表B),其中0 <x <4000,0 <y <4000,它们将始终为整数.我需要知道两个列表中的坐标是什么.对于如何处理此问题,您有什么建议？
我一直在考虑将列表表示为两个网格,并且按位和可能？
列表A有大约1000个条目,每10,000个请求可能有一次更改.列表B的长度会有很大差异,每次运行都会有所不同.
编辑:我应该提到两次没有坐标列表; 例如,1,1不能在列表A中不止一次.
将(x,y)表示为单个24位数,如注释中所述.
按数字顺序维护A(你说它变化不大,所以这应该几乎没有任何成本).
对于每个B,在列表上进行二进制搜索.由于A大约有1000个项目,因此最多需要10个整数比较(在最坏的情况下)来检查成员资格.
如果您有更多的内存(约2MB)可以使用,您可以创建一个位向量来支持所有可能的24位数,然后对每个项执行单个位操作以测试成员资格.因此A将由单个2 ^ 24位数表示,如果值在那里则具有位设置(否则为0).要测试成员资格,您只需使用适当的位和操作即可.
将列表 A 的坐标放入某种集合（可能是哈希、bst 或堆）中，然后您可以快速查看列表 B 中的坐标是否存在。
根据您期望列表是否出现在列表中，将确定您使用的底层数据结构。
哈希可以很好地告诉您其中是否有某些内容，尽管取决于它的实现方式，但在尝试查找其中不存在的内容时可能会表现不佳。
bst 和堆同样擅长告诉您其中是否有东西，但理论上当其中有东西时，其性能不如散列。