¿Cuál es la forma más eficiente de probar dos rangos enteros para la superposición?

Dado dos rangos de valores enteros inclusivos [x1: x2] y [y1: y2], donde x1 ≤ x2 y y1 ≤ y2, ¿cuál es la forma más eficiente de comprobar si existe alguna superposición de los dos rangos?

Una implementación simple es la siguiente:

bool testOverlap(int x1, int x2, int y1, int y2) { return (x1 >= y1 && x1 = y1 && x2 = x1 && y1 = x1 && y2 <= x2); } 

Pero espero que haya formas más eficientes de calcular esto.

¿Qué método sería el más eficiente en términos de menos operaciones?

¿Qué significa que los rangos se superpongan? Significa que existe algún número C que está en ambos rangos, es decir,

 x1 <= C <= x2 

y

 y1 <= C <= y2 

Ahora, si se nos permite suponer que los rangos están bien formados (de modo que x1 <= x2 y y1 <= y2), entonces es suficiente para probar

 x1 <= y2 && y1 <= x2 

Dado dos rangos [x1, x2], [y1, y2]

 def is_overlapping(x1,x2,y1,y2): return max(x1,y1) <= min(x2,y2) 

Esto puede deformar fácilmente un cerebro humano normal, por lo que he encontrado un enfoque visual para ser más fácil de entender:

Superposición locura

le Explicación

Si dos rangos son “demasiado gordos” para caber en una ranura que es exactamente la sum del ancho de ambos, entonces se superponen.

Para los rangos [a1, a2] y [b1, b2] esto sería:

 /** * 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! } 

Gran respuesta de Simon , pero para mí fue más fácil pensar en el caso inverso.

¿Cuándo 2 rangos no se superponen? No se superponen cuando uno de ellos comienza después de que el otro termina:

 dont_overlap = x2 < y1 || x1 > y2 

Ahora es fácil express cuándo se superponen:

 overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2) 

Restar el mínimo de los extremos de los rangos desde el máximo del principio parece ser el truco. Si el resultado es menor o igual que cero, tenemos una superposición. Esto lo visualiza bien:

enter image description here

Supongo que la pregunta fue sobre el código más rápido, no el más corto. La versión más rápida tiene que evitar las twigs, por lo que podemos escribir algo como esto:

para el caso simple:

 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)); }; 

o, para este caso:

 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); }; 
 return x2 >= y1 && x1 <= y2; 

Si estaba tratando con dos rangos [x1:x2] y [y1:y2] , el orden natural / antinatural oscila al mismo tiempo donde:

  • orden natural: x1 <= x2 && y1 <= y2 o
  • orden antinatural: x1 >= x2 && y1 >= y2

entonces puede usar esto para verificar:

se superponen <=> (y2 - x1) * (x2 - y1) >= 0

donde solo están involucradas cuatro operaciones:

  • dos sustracciones
  • una multiplicación
  • una comparación

Ya tiene la representación más eficiente: es lo mínimo que debe verificarse a menos que sepa con seguridad que x1

Probablemente deberías notar que algunos comstackdores realmente optimizarán esto para ti, volviendo tan pronto como cualquiera de esas 4 expresiones devuelvan verdadero. Si uno devuelve verdadero, también lo hará el resultado final, por lo que las otras comprobaciones solo se pueden omitir.

Si alguien está buscando un trazador de líneas que calcule la superposición real:

 int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations 

Si quieres un par de operaciones menos, pero un par de variables más:

 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 

Aquí está mi versión:

 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; 

A menos que esté ejecutando un comprobador de rango de alto rendimiento en miles de millones de enteros ampliamente espaciados, nuestras versiones deben funcionar de manera similar. Mi punto es que esto es una micro-optimización.