math - valores - buscarh con dos condiciones
Buscar intersección de rango de números (5)
¿Cuál es la mejor manera de averiguar si dos rangos de números se cruzan?
Mi rango de números es 3023-7430 , ahora quiero probar cuál de los siguientes rangos de números se cruzan con él: <3000, 3000-6000, 6000-8000, 8000-10000,> 10000. La respuesta debería 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?
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))
Esto depende en gran medida de tus 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.
Creo que puedo decir lo siguiente: si tienes pequeños rangos (agrupar o no agrupar no importa aquí), considera bitvectors. Estas pequeñas criaturas son extremadamente rápidas con respecto a las pruebas de unión, intersección y pertenencia, aunque la iteración sobre todos los elementos puede demorar un tiempo, dependiendo del tamaño. Además, debido a 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 será suficiente. Esta clase tiene los atributos inferiores y superiores, y la intersección (a, b) es básicamente b.upper <a.lower o a.upper> b.lower. La unión y la intersección se pueden implementar en tiempo constante para rangos únicos y para rangos compisite, el tiempo crece con el número de subintervalos (por lo tanto, no se desean demasiados rangos pequeños)
Si tiene un gran espacio donde sus números pueden ser, y los rangos se distribuyen en un desagradable fasion, debería echar un vistazo a los diagramas de decisión binarios (BDD). Estos ingeniosos 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 algoritmos recursivos bastante elegantes, por ejemplo, la intersección básicamente toma dos nodos correspondientes en cada BDD, recorre el 1 hasta que aparece un resultado y comprueba: si uno de los resultados es el False-Terminal, cree un 1 -Branco a la 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, se inicia 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.
Se puede obtener más información, por ejemplo, en la Wikipedia y en los documentos mencionados.
Además, si los falsos positivos son soportables y solo necesita una verificació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 la Wikipedia , por ejemplo.
Hach, la representación establecida es un campo divertido. :)
Haría una clase Range y le daría un método boolean intersects (Range). Entonces puedes 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
Solo una adivinanza de 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;
}
Si está utilizando Java Commons, Lang Range tiene un método OverlapsRange (Rango de rango).