给定两个包含范围[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 <= x2 && y1 <= y2或 反自然顺序:x1 >= x2 && y1 >= y2
然后你可能想用这个来检查:
它们重叠<=> (y2 - x1) * (x2 - y1) >= 0
其中只涉及四个操作:
2倍 一个乘法 一个比较
其他回答
什么新东西。只是可读性更强。
def overlap(event_1, event_2):
start_time_1 = event_1[0]
end_time_1 = event_1[1]
start_time_2 = event_2[0]
end_time_2 = event_2[1]
start_late = max(start_time_1, start_time_2)
end_early = min(end_time_1, end_time_2)
# The event that starts late should only be after the event ending early.
if start_late > end_early:
print("Absoloutly No overlap!")
else:
print("Events do overlap!")
如果有人正在寻找计算实际重叠的一行程序:
int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations
如果你想要少一些操作，但多一些变量:
bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations
给定两个范围[x1,x2]， [y1,y2]
def is_overlapping(x1,x2,y1,y2):
return max(x1,y1) <= min(x2,y2)
从开始的最大值减去范围末端的最小值似乎可以达到目的。如果结果小于等于零，就有重叠。这很直观:
我想问题是关于最快的代码，而不是最短的代码。最快的版本必须避免分支，所以我们可以这样写:
对于简单的例子:
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);
};
