Что самый эффективный путь состоит в том, чтобы протестировать два целочисленных диапазона на перекрытие?
Учитывая два содержащих целочисленных диапазона [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);
}
Но я ожидаю, что существуют более эффективные способы вычислить это.
Какой метод был бы самым эффективным с точки зрения наименьшего количества операций.
5 ответов
Что означает перекрытие диапазонов? Это означает, что существует некоторое число C, которое находится в обоих диапазонах, то есть
x1 <= C <= x2
и
y1 <= C <= y2
. Теперь, если нам разрешено предположить, что диапазоны сформированы правильно (так что x1 <= x2 и y1 <= y2), тогда достаточно проверить
x1 <= y2 && y1 <= x2
Вот моя версия:
int xmin = min(x1,x2)
, xmax = max(x1,x2)
, ymin = min(y1,y2)
, ymax = max(y1,y2);
for (int i = xmin; i < xmax; ++i)
if (ymin <= i && i <= ymax)
return true;
return false;
Если вы не используете высокопроизводительную программу проверки диапазона на миллиардах широко расставленных целых чисел, наши версии должны работать одинаково. Я хочу сказать, что это микрооптимизация.
У вас уже есть наиболее эффективное представление - это минимум, который нужно проверить, если только вы не знаете наверняка, что x1 < x2 и т.д., тогда используйте решения, предложенные другими.
Вы, вероятно, должны заметить, что некоторые компиляторы на самом деле оптимизируют это для вас - возвращаясь, как только любое из этих 4 выражений возвращает true. Если одно из них возвращает истину, то и конечный результат будет истинным - так что остальные проверки можно просто пропустить.
Я полагаю, вопрос касался самого быстрого, а не самого короткого кода. Самая быстрая версия должна избегать ветвлений, поэтому мы можем написать что-то вроде этого:
для простого случая:
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);
};