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

251

Dados dos rangos enteros inclusivos [x1: x2] y [y1: y2], donde x1 ≤ x2 e y1 ≤ y2, ¿cuál es la forma más eficiente de probar si hay una 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 la menor cantidad de operaciones.

WilliamKF
fuente
Podría estar interesantemente relacionado para algunos - stackoverflow.com/q/17138760/104380
vsync

Respuestas:

454

¿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 e y1 <= y2), entonces es suficiente probar

x1 <= y2 && y1 <= x2
Simon Nickerson
fuente
1
Creo que debería ser x1 <= y2 && y1 >= x2, ¿no?
David Beck
8
@DavidBeck: no, si y1> x2, los rangos definitivamente no se superponen (por ejemplo, considere [1: 2] y [3: 4]: y1 = 3 y x2 = 2, entonces y1> x2, pero no hay superposición) .
Simon Nickerson
8
esta sería una mejor respuesta si explicaras el razonamiento un poco más
shoosh
2
@Vineet Deoraj: ¿Por qué crees que no funciona? x1 = 1, y1 = 1, x2 = 1, y2 = 1, entonces x1 <= y2 && y1 <= x2 es cierto, por lo tanto, hay una superposición.
dcp
2
La explicación está aquí: stackoverflow.com/questions/325933/…
Alex
138

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

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)
KFL
fuente
44
@ uyuyuy99: solo que no es tan eficiente, porque cuando esta verificación se realiza muchas veces por segundo, la función de llamada es algo que le gustaría evitar, y haga las
mismas
77
@vsync Los navegadores modernos integrarán y optimizarán funciones como Math.max, no debería haber un impacto notable en el rendimiento.
Ashton Six, el
1
@AshtonWar: interesante. ¿Tienes un artículo que explique qué se inserta y qué no?
vsync
@vsync No, pero estoy seguro de que puede encontrar la información usted mismo
Ashton Six, el
66
Además, tenga en cuenta que min(x2,y2) - max(x1,y1)proporciona la cantidad de superposición en caso de que lo necesite.
user1556435
59

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

superposición de locura

le Explicación

Si dos rangos son "demasiado gruesos" para caber en una ranura que es exactamente la suma del ancho de ambos, entonces se superponen.

Para 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!
}
FloatingRock
fuente
3
Hay más casos de los que se muestran en sus imágenes. Por ejemplo, ¿qué pasa si w2 comienza antes de w1 y termina después de w1?
WilliamKF
77
@WilliamKF la lógica se mantiene verdadera
FloatingRock
2
De acuerdo, pero creo que podría ayudar a proporcionar una tercera imagen.
WilliamKF
3
@WilliamKF, entonces necesitas muchas más imágenes, hay 16 combinaciones diferentes en las que se pueden colocar 2 rangos ...
Peter
3
Tenga cuidado si usa este método, porque la suma a2 - a1 + b2 - b1puede desbordarse. Para solucionarlo, reorganice la fórmula a max(a2, b2) - a2 - b2 < min(a1, b1) - a1 - b1, que se simplifica max(a1, b1) < min(a2, b2), ahorrando algo de aritmética y evitando posibles desbordamientos (esta es la respuesta de AX-Labs a continuación). En el caso especial donde sabes b2-b1=a2-a1, otra reorganización útil de la fórmula de FloatingRock es max(a2, b2) - min(a1, b1) - (b2 - b1) < a2-a1, que se convierte en abs(b1-a1) < a2 - a1.
Paolo Bonzini
44

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

¿Cuándo no se superponen 2 rangos? 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)
Damluar
fuente
1
Para mí, la expresión más fácil de entender es: x2 <y1 || y2 <x1 // donde uso 'menor que' en lugar de "mayor que".
Park JongBum
25

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

ingrese la descripción de la imagen aquí

Laboratorios AX
fuente
2
Esto cubre todos los casos
usuario 3290180
10

Supongo que la pregunta era 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:

por simple caso:

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);
};
ruslik
fuente
77
Ten fe en tu compilador. La expresión x1 <= y2 && y1 <= x2 tampoco tiene ramificaciones , suponiendo un compilador razonablemente competente y una arquitectura de CPU (incluso en 2010). De hecho, en x86, el código generado es básicamente idéntico para la expresión simple frente al código en esta respuesta.
Søren Løvborg
4
return x2 >= y1 && x1 <= y2;
BlueRaja - Danny Pflughoeft
fuente
Esto no es correcto. Porque x1 <= y1 && x2 >= y2 || x1 >= y1 && x2 <= y2también debería volver cierto.
Rahat Zaman
4

Si estaba lidiando, dados dos rangos [x1:x2]y rangos de orden [y1:y2]natural / antinatural al mismo tiempo donde:

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

entonces es posible que desee usar esto para verificar:

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

donde solo participan cuatro operaciones:

  • dos restas
  • una multiplicación
  • una comparación
Yankuan Zhang
fuente
1

Si alguien está buscando una línea 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 desea 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
Victor.dMdB
fuente
1

Piense de manera inversa : ¿cómo hacer que los 2 rangos no se superpongan ? Dado [x1, x2], entonces [y1, y2]debe estar afuera [x1, x2] , es decir, y1 < y2 < x1 or x2 < y1 < y2que es equivalente ay2 < x1 or x2 < y1 .

Por lo tanto, la condición para hacer que los 2 rangos se superpongan: not(y2 < x1 or x2 < y1)es equivalente a y2 >= x1 and x2 >= y1(lo mismo con la respuesta aceptada por Simon).

Duque
fuente
Parece lo mismo que respondió @damluar (2 de marzo de 16 a las 17:36)
Nakilon
0

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

Probablemente debería tener en cuenta que algunos compiladores realmente optimizarán esto para usted, al regresar tan pronto como cualquiera de esas 4 expresiones devuelva verdadero. Si uno devuelve verdadero, también lo hará el resultado final, por lo que las otras verificaciones solo se pueden omitir.

Mark H
fuente
2
Todos los compiladores lo harán. Todos (según mi conocimiento) los lenguajes utilizados actualmente con sintaxis de estilo C (C, C ++, C #, Java, etc.) emplean operadores booleanos en cortocircuito y es parte de los diversos estándares que rigen esos lenguajes. Si el resultado del valor de la izquierda es suficiente para determinar el resultado de la operación, el valor de la derecha no se evalúa.
Jonathan Grynspan
1
Mark H: el compilador omitirá la segunda cláusula si puede: así que si tiene una función que dice: foo (int c) {int i = 0; if (c <3 || ++ i == argc) printf ("Inside \ n"); printf ("i es% d \ n", i); Foo (2) imprimirá: Dentro de i es 0 y Foo (4) imprimirá: i es 1 (probado en gcc 4.4.3, pero también confié en este comportamiento para algunos códigos feos en icc)
J Teller
0

Mi caso es diferente. Quiero comprobar la superposición de dos rangos de tiempo. no debe haber una superposición de unidad de tiempo. aquí está la implementación de Go.

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

Casos de prueba

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

puedes ver que hay un patrón XOR en la comparación de límites

Ajeet47
fuente
-10

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 deberían funcionar de manera similar. Mi punto es que esto es micro-optimización.

Haywood Jablomey
fuente
Creo que has repasado las especificaciones aquí. Se supone que x1 a x2 es ascendente / descendente (de cualquier manera, está ordenado): no hay necesidad de un bucle, solo necesita verificar los elementos de cabeza y cola. Sin embargo, prefiero la solución min / max, simplemente porque es más fácil de leer cuando vuelves al código más tarde.
Mark H
12
-1: esto no es micro-optimización; Esto es elegir un algoritmo apropiado. Su algoritmo es O (n) cuando hay una simple opción O (1).
Simon Nickerson
Esto es lo que sucede cuando "la optimización prematura es la raíz de todo mal" se convierte en un principio religioso inviolable para el inepto en lugar de un comentario medio serio sobre algún patrón de comportamiento ocasional.
rghome