我的依据是我最近发现的关于 Dictionary
的性能特征,所以我使用 Dictionary<type, bool>
bool
在哪里被忽略但据说我可以使用 HashSet
相反。
例如:
Dictionary<bounds, bool> overlap;
class bounds
{
public float top_left_x, top_left_y, width, height;
public bool equal(bounds other)
{
return upper_left_x + width > other.upper_left_x &&
upper_left_x < other.upper_left_x + other.width &&
upper_left_y + height > other.upper_left_y &&
upper_left_y < other.upper_left_y + other.height;
}
public ... GetHashCode()
{
...;
}
}
在这里,我没有使用 equal 检查是否相等,而是检查重叠,这在其他地方肯定会很烦人,但我这样做是有原因的。
我假设如果可以在 O(1) 时间内从键中查找值,那么从键本身也可以。
所以我大概可以将数千个边界重叠并执行此操作:
overlap.ContainsKey(new bounds(...));
在 O(1) 时间内找出给定边界是否与集合中的任何其他边界重叠。
我还想知道如果我更改边界的 (x, y) 位置会发生什么,大概就像删除然后再将其添加到集合中一样性能明智,非常昂贵?
我应该在 GetHashCode 函数中输入什么?
目标
如果这可行,那么我将使用这种机制找出给定边界重叠的其他边界。
此系统中移动的边界很少,并且在填充集合后不会添加新边界。新添加的边界需要能够与旧边界重叠。
结论
有关详细信息,请参阅下面的反馈。
总而言之,不可能实现 O(1) 性能,因为与默认的 equals 不同,重叠检查不是可传递的。
然而,区间树是一个很好的解决方案。
最佳答案
在这里使用相等关系完全是错误的关系,因为相等必须是等价关系。也就是说,它必须是自反的 -- A == A 对于任何 A。它必须是对称的 -- A == B 意味着 B == A。并且它必须是可传递的——如果 A == B 和 B == C 那么 A == C。
你提议违反传递属性; “重叠”不是传递关系,因此“重叠”不是等价关系,因此不能将相等定义为重叠。
与其尝试做这种危险的事情,不如解决真正的问题。您的目标显然是采用一组间隔,然后快速确定给定间隔是否与这些间隔中的任何一个重叠。您想要的数据结构称为区间树; 它经过专门优化以准确解决该问题,因此请使用它。 在任何情况下,您都不应尝试将哈希集用作区间树。使用正确的工具来完成这项工作:
关于c# - 使用C#HashSet解决等不等的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8765772/