Buscar intersección de rango de números

Question

¿Cuál es la mejor manera de averiguar si dos rangos de números se cruzan?

Mi rango de números es 3023 a 7430, ahora quiero probar cuál de los siguientes rangos de números se cruzan con él: < 3000, 3000-6000, 6000-8000, 8000-10000,> 10.000. La respuesta debe ser 3000-6000 y 6000-8000.

¿Cuál es la manera matemática agradable y eficiente de hacer esto en cualquier lenguaje de programación?

Answer 1

Sólo una conjetura pseudo código:

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest) 
{ 
    Set<Range> results; 
    foreach (rangeToTest in setofRangesToTest) 
    do 
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range 
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range 
    results.add(rangeToTest); 
    done 
    return results; 
} 

Answer 2

Me gustaría hacer una clase de cocina y darle un método intersecciones booleanas (Rango). A continuación, se puede hacer un

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) } 

La intersección en sí es algo así como

this.start <= other.end && this.end >= other.start 

Answer 3

Esto depende en gran medida de sus rangos. Un rango puede ser grande o pequeño, y agrupado o no agrupado. Si tiene rangos grandes y agrupados (piense en "todos los enteros positivos de 32 bits que pueden dividirse entre 2), el enfoque simple con Rango (inferior, superior) no tendrá éxito.

Supongo que puedo decir lo siguiente : si tiene pocos rangos (agrupar o no agrupar no importa aquí), considere bitvectors. Estos pequeños bichos son extremadamente rápidos con respecto a la unión, intersección y prueba de pertenencia, aunque la iteración sobre todos los elementos podría tomar un tiempo, dependiendo de Además, dado que solo usan un bit para cada elemento, son bastante pequeños, a menos que les arroje rangos enormes.

si tiene menos rangos más grandes, entonces un rango de clase como el descrito por otros bastará. . Esta clase tiene el atributo es inferior y superior y la intersección (a, b) es básicamente b.upper < a.lower o a.upper> b.lower. Unión e intersección pueden implementarse en tiempo constante para rangos únicos y para rangos compisite, el tiempo crece con el número de subintervalos (por lo tanto, no desea demasiados rangos pequeños)

Si tiene un gran espacio donde sus números pueden ser, y los rangos están distribuidos en un desagradable fasion, debería echar un vistazo a los diagramas de decisión binarios (BDD). Estos nifty diagramas tienen dos nodos terminales, verdadero y falso y nodos de decisión para cada bit de la entrada. Un nodo de decisión tiene un bit que mira y dos nodos gráficos siguientes: uno para "bit es uno" y otro para "bit es cero". Dadas estas condiciones, puede codificar gamas grandes en espacios pequeños. Todos los enteros positivos para números arbitrariamente grandes se pueden codificar en 3 nodos en el gráfico, básicamente un nodo de decisión único para el bit menos significativo que va a False en 1 y a True en 0.

Intersection y Union son bastante elegantes algoritmos recursivos, por ejemplo, la intersección básicamente toma dos nodos correspondientes en cada BDD, recorre el 1-edge hasta que aparezca un resultado y comprueba: si uno de los resultados es el False-Terminal, crea un 1-branch al False- terminal en el resultado BDD. Si ambos son el True-Terminal, cree un 1-branch para el True-terminal en el resultado BDD. Si se trata de otra cosa, crea una rama en este algo-else en el resultado BDD. Después de eso, comienza una minimización (si la rama 0 y la rama 1 de un nodo van al mismo BDD/terminal siguiente, quítelo y extraiga las transiciones entrantes al objetivo) y estará dorado.Incluso fuimos más allá de eso, trabajamos en la simulación de la adición de conjuntos de enteros en los BDD para mejorar la predicción del valor con el fin de optimizar las condiciones.

Estas consideraciones implican que sus operaciones están limitadas por la cantidad de bits en su rango numérico, es decir, por log_2 (MAX_NUMBER). Solo piense en ello, puede interceptar conjuntos arbitrarios de enteros de 64 bits en tiempo casi constante.

Más información puede ser, por ejemplo, en el Wikipedia y los documentos referenciados.

Además, si los falsos positivos son soportables y solo necesita una comprobación de existencia, puede mirar los filtros Bloom. Los filtros Bloom usan un vector de valores hash para verificar si un elemento está contenido en el conjunto representado. Intersección y unión es tiempo constante. El principal problema aquí es que obtienes una tasa creciente de falsos positivos si llenas demasiado el filtro de floración. Información, nuevamente, en el Wikipedia, por ejemplo.

Hach, set representation es un campo divertido. :)

Answer 4

en Python

class nrange(object): 
    def __init__(self, lower = None, upper = None): 
     self.lower = lower 
     self.upper = upper 
    def intersection(self, aRange): 
     if self.upper < aRange.lower or aRange.upper < self.lower: 
      return None 
     else: 
      return nrange(max(self.lower,aRange.lower), \ 
          min(self.upper,aRange.upper)) 

Answer 5

Si está utilizando Java Commons Lang Range tiene un método overlapsRange (rango Rango).