Cómo buscar un rango a partir de un conjunto de rangos contiguos para un número determinado

Question

En pocas palabras, esto es lo que estoy tratando de hacer:

tengo una colección de Range objetos que son contiguos (no superpuestos, sin espacios entre ellos), cada uno de los cuales contiene un start y end int y una referencia a otro objeto obj.Estos rangos no tienen un tamaño fijo (el primero podría ser 1-49, el segundo 50-221, etc.).Esta colección podría llegar a ser bastante grande.

Espero encontrar una manera de buscar el rango (o más específicamente, el objeto al que hace referencia) que incluye un número determinado sin tener que recorrer toda la colección verificando cada rango para ver si incluye el número.Estas búsquedas se realizarán con frecuencia, por lo que la velocidad y el rendimiento son clave.

¿Alguien conoce un algoritmo/ecuación que pueda ayudarme?Estoy escribiendo en Java.Puedo proporcionar más detalles si es necesario, pero pensé que intentaría mantenerlo simple.

Gracias.

Answer 1

Si suena como si quisieras usar un TreeMap, donde la clave es la parte inferior del rango y el valor es el Range objeto.

Luego, para identificar el rango correcto, simplemente use el floorEntry() método para obtener muy rápidamente el más cercano (menor o igual) Range, que debería contener la clave, así:

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

Dado que el árbol siempre está ordenado según el orden natural del límite inferior del rango, todas sus búsquedas serán, en el peor de los casos, O (log (n)).

Querrá agregar algunas comprobaciones de cordura para cuando su clave esté completamente fuera de los límites (por ejemplo, cuando la clave está más allá del final del mapa, devuelve la última Range en el mapa), pero esto debería darle una idea de cómo proceder.

Answer 2

Suponiendo que sus búsquedas son de suma importancia y que puede ahorrar memoria O(N) y aproximadamente O(N^2) tiempo de preprocesamiento, el algoritmo sería:

• presentar una clase ObjectsInRange, que contiene:inicio del rango (int startOfRange) y un conjunto de objetos (Set<Object> objects)
• introducir un ArrayList<ObjectsInRange> oir, que contendrá ObjectsInRange ordenado por el startOfRange
• para cada Range r, asegúrese de que exista ObjectsInRange (llamémoslos a y b) tal que a.startOfRange = r.start y b.startOfRange = b.end.Entonces, para todos ObjectsInRange x entre a, y hasta (pero sin incluir) b, agregar r.obj a su x.objects colocar

La búsqueda entonces es la siguiente:

• para entero x, encuentra tal i eso oir[i].startOfRange <= x y oir[i+1].startOfRange > x
• nota: i ¡Se puede encontrar con bisección en tiempo O (log N)!
• tus objetos son oir[i].objects

Answer 3

Si la colección está en orden, entonces puede implementar una búsqueda binaria para encontrar el rango correcto en tiempo O(log(n)).No es tan eficiente como el hash para colecciones muy grandes, pero si tiene menos de 1000 rangos, puede ser más rápido (porque es más simple).