performance - superposicion - superposición de pantalla samsung s6

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

Question

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 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= 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?

Answer 1

¿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

Answer 2

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.

Answer 3

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

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

Answer 4

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:

le Explicación

Si dos rangos son "demasiado gordos" para caber en una ranura que es exactamente la suma 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!
}

Answer 5

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 expresar cuándo se superponen:

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

Answer 6

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:

Answer 7

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

Answer 8

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

Answer 9

Ya tiene la representación más eficiente: es lo mínimo que debe verificarse a menos que sepa con seguridad que x1 <x2, etc., y luego use las soluciones que otros le han proporcionado.

Probablemente deberías notar que algunos compiladores 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.

Answer 10

return x2 >= y1 && x1 <= y2;