给定两个包含范围[x1:x2]和[y1:y2]，其中x1≤x2和y1≤y2，测试这两个范围是否有重叠的最有效方法是什么?
一个简单的实现如下:
bool testOverlap(int x1, int x2, int y1, int y2) {
return (x1 >= y1 && x1 <= y2) ||
(x2 >= y1 && x2 <= y2) ||
(y1 >= x1 && y1 <= x2) ||
(y2 >= x1 && y2 <= x2);
}
但是我希望有更有效的方法来计算这个。
就最少的操作而言，哪种方法是最有效的?
当前回答
考虑到: (x1, x2) (y1, y2) 那么x1 <= y2 || x2 >= y1总是成立的。 作为
x1 ... x2
y1 .... y2
如果是x1 > y2，那么它们不重叠 或
x1 ... x2
y1 ... y2
如果x2 < y1，它们不重叠。
其他回答
我想问题是关于最快的代码，而不是最短的代码。最快的版本必须避免分支，所以我们可以这样写:
对于简单的例子:
static inline bool check_ov1(int x1, int x2, int y1, int y2){
// insetead of x1 < y2 && y1 < x2
return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};
或者，对于这种情况:
static inline bool check_ov2(int x1, int x2, int y1, int y2){
// insetead of x1 <= y2 && y1 <= x2
return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};
西蒙的回答很好，但对我来说，相反的情况更容易思考。
什么时候两个范围不重叠?当其中一个开始后另一个结束时，它们不会重叠:
dont_overlap = x2 < y1 || x1 > y2
当它们重叠时，很容易表示:
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
return x2 >= y1 && x1 <= y2;
为什么这样做有效: 范围不重叠的唯一情况是当一个范围的结束在另一个范围的开始之前。所以我们想要!(x2 < y1 || x1 > y2)它等价于上面。
这很容易扭曲正常人的大脑，所以我找到了一个更容易理解的视觉方法:
勒解释
如果两个范围“太胖”，无法放入正好是两者宽度之和的槽中，那么它们就会重叠。
对于范围[a1, a2]和[b1, b2]，这将是:
/**
* we are testing for:
* max point - min point < w1 + w2
**/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
// too fat -- they overlap!
}
我的情况不同。我要检查两个时间范围是否重叠。不应该有单位时间的重叠。这里是Go的实现。
func CheckRange(as, ae, bs, be int) bool {
return (as >= be) != (ae > bs)
}
测试用例
if CheckRange(2, 8, 2, 4) != true {
t.Error("Expected 2,8,2,4 to equal TRUE")
}
if CheckRange(2, 8, 2, 4) != true {
t.Error("Expected 2,8,2,4 to equal TRUE")
}
if CheckRange(2, 8, 6, 9) != true {
t.Error("Expected 2,8,6,9 to equal TRUE")
}
if CheckRange(2, 8, 8, 9) != false {
t.Error("Expected 2,8,8,9 to equal FALSE")
}
if CheckRange(2, 8, 4, 6) != true {
t.Error("Expected 2,8,4,6 to equal TRUE")
}
if CheckRange(2, 8, 1, 9) != true {
t.Error("Expected 2,8,1,9 to equal TRUE")
}
if CheckRange(4, 8, 1, 3) != false {
t.Error("Expected 4,8,1,3 to equal FALSE")
}
if CheckRange(4, 8, 1, 4) != false {
t.Error("Expected 4,8,1,4 to equal FALSE")
}
if CheckRange(2, 5, 6, 9) != false {
t.Error("Expected 2,5,6,9 to equal FALSE")
}
if CheckRange(2, 5, 5, 9) != false {
t.Error("Expected 2,5,5,9 to equal FALSE")
}
你可以在边界比较中看到异或模式
