Búsqueda de rango en Java

Question

Supongamos que tengo una matriz no ordenada de ranges superpuesto. Cada range es solo un par de números enteros begin y end. Ahora quiero encontrar si un key dado pertenece a al menos uno de los ranges. Probablemente, también debo saber que el ranges pertenece.

Podemos suponer que la matriz ranges tarda ~ 1M y se adapta a la memoria. Estoy buscando un algoritmo fácil, que utiliza solo colecciones JDK estándar sin bibliotecas de partes 3d y estructuras de datos especiales, pero funciona razonablemente rápido.

¿Qué sugeriría?

Answer 1

Si no necesita saber lo que intervalo contiene el punto (EDIT: Creo que es probable que sí, pero yo a dejar esta respuesta para los demás con esta pregunta que no lo hacen), entonces

1. Preprocese los intervalos calculando dos matrices B y E. B es los valores de comenzar en orden ordenado. E es los valores de fin en orden ordenado.

2. Para consultar un punto x, utilice la búsqueda binaria para buscar el índice mínimo i tal que B [i]> x y el menor índice j tal que E [j] ≥ x. La cantidad de intervalos [comienzo, final] que contiene x es i - j.

---

class Interval { 
    double begin, end; 
} 

class BeginComparator implements java.util.Comparator<Interval> { 
    public int compare(Interval o1, Interval o2) { 
     return Double.compare(o1.begin, o2.begin); 
    } 
}; 

public class IntervalTree { 
    IntervalTree(Interval[] intervals_) { 
     intervals = intervals_.clone(); 
     java.util.Arrays.sort(intervals, new BeginComparator()); 
     maxEnd = new double[intervals.length]; 
     initializeMaxEnd(0, intervals.length); 
    } 

    double initializeMaxEnd(int a, int b) { 
     if (a >= b) { 
      return Double.NEGATIVE_INFINITY; 
     } 
     int m = (a + b) >>> 1; 
     maxEnd[m] = initializeMaxEnd(a, m); 
     return Math.max(Math.max(maxEnd[m], intervals[m].end), initializeMaxEnd(m + 1, b)); 
    } 

    void findContainingIntervals(double x, int a, int b, java.util.Collection<Interval> result) { 
     if (a >= b) { 
      return; 
     } 
     int m = (a + b) >>> 1; 
     Interval i = intervals[m]; 
     if (x < i.begin) { 
      findContainingIntervals(x, a, m, result); 
     } else { 
      if (x <= i.end) { 
       result.add(i); 
      } 
      if (maxEnd[m] >= x) { 
       findContainingIntervals(x, a, m, result); 
      } 
      findContainingIntervals(x, m + 1, b, result); 
     } 
    } 

    java.util.Collection<Interval> findContainingIntervals(double x) { 
     java.util.Collection<Interval> result = new java.util.ArrayList<Interval>(); 
     findContainingIntervals(x, 0, intervals.length, result); 
     return result; 
    } 

    Interval[] intervals; 
    double[] maxEnd; 

    public static void main(String[] args) { 
     java.util.Random r = new java.util.Random(); 
     Interval[] intervals = new Interval[10000]; 
     for (int j = 0; j < intervals.length; j++) { 
      Interval i = new Interval(); 
      do { 
       i.begin = r.nextDouble(); 
       i.end = r.nextDouble(); 
      } while (i.begin >= i.end); 
      intervals[j] = i; 
     } 
     IntervalTree it = new IntervalTree(intervals); 
     double x = r.nextDouble(); 
     java.util.Collection<Interval> result = it.findContainingIntervals(x); 
     int count = 0; 
     for (Interval i : intervals) { 
      if (i.begin <= x && x <= i.end) { 
       count++; 
      } 
     } 
     System.out.println(result.size()); 
     System.out.println(count); 
    } 
} 

Answer 2

Ordenar los rangos numéricamente por una costumbre Comparator, a continuación, para cada tecla k build una gama de un elemento [k, k] y hacer un binary search para esta gama con un diferente Comparator.

El Comparator para la búsqueda de compare(x,y) deberían volver

• <0 si x.max < y.min
• >0 si x.min > y.max
• 0 lo contrario (sus dos argumentos rango de superposición).

Según lo observado por @Per, necesita un Comparator diferente, más estricto para la clasificación, pero las dos primeras cláusulas aún se mantienen.

Esto debería funcionar incluso si los rangos se superponen, aunque es posible que desee fusionar los rangos superpuestos después de la clasificación para acelerar la búsqueda. La fusión se puede hacer en O (N) vez.

Esto es en efecto una estática interval tree, es decir, uno sin O (lg N) inserción o deleción, de la misma manera que una matriz ordenada puede ser considerado un árbol binario de búsqueda estática.

Answer 3

Creo que esto es lo que busca: http://en.wikipedia.org/wiki/Interval_tree

, pero echa esta solución más simple para ver si se ajusta a sus necesidades: Using java map for range searches

Answer 4

solución simple con O (n) la complejidad:

for(Range range: ranges){ 
    if (key >= range.start && key <= range.end) 
    return range; 
} 

Se puede aplicar un algoritmo más inteligente si conocemos más información acerca de los rangos. ¿Están ordenados? ¿Están superpuestos? y así sucesivamente

Answer 5

Dada su especificación, me inclinaría a ordenar los rangos por tamaño, con los rangos más amplios primero (use un Comparador personalizado para facilitar esto). Luego simplemente itere a través de ellos y devuelva verdadero tan pronto como encuentre un rango que contenga la clave. Debido a que no sabemos nada más sobre los datos, por supuesto, los rangos más amplios son los más propensos a contener una clave determinada; buscarlos primero podría ser una (pequeña) optimización.

Puede preprocesar la lista de otras maneras.Por ejemplo, podría excluir cualquier intervalo que esté completamente encerrado por otros rangos. Puede ordenar por begin y salir temprano tan pronto como encuentre un valor begin mayor que su clave.