java - ozuna - Un algoritmo de intersección de rango mejor que O(n)?

ozuna 2018

Question

La intersección de rangos es un problema simple pero no trivial.

Ya ha sido respondida dos veces:

• Buscar intersección de rango de números
• Comparación de los intervalos de fechas

Las primeras soluciones son O (n) y la segunda solución es para una base de datos (que es menor que O (n), por supuesto).

Tengo el mismo problema, pero para una n grande y no estoy dentro de una base de datos.

Este problema parece ser muy similar a Store 2D points para la recuperación rápida de los que están dentro de un rectángulo, pero no veo cómo se correlaciona.

Entonces, ¿en qué estructura de datos se almacenaría el conjunto de rangos, de modo que una búsqueda en un rango cuesta menos que O (n)? (Crédito adicional por usar bibliotecas disponibles para Java)

EDITAR:

Quiero obtener un subconjunto de todos los rangos de intersección, lo que significa que el rango de búsqueda podría intersecar múltiples rangos.

El método que debe ser menor que O (n) en Java es:

public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}

Donde Range es solo una clase que contiene un par de inicio y fin int.

Esta no es una pregunta imposible, ya tengo la solución, solo quería ver si había una manera más estándar / más simple de hacerlo

Answer 1

Así como un árbol cuádruple funciona para un conjunto de puntos 2d, un árbol binario simple debería funcionar para este caso. Construye un árbol con tus rangos.

Para explicar más: cada nodo en el árbol contiene dos enteros, el comienzo y el final del rango, y los dos hijos si no es un nodo hoja. Para encontrar los rangos que abarca su rango de entrada, comenzando en la parte superior del árbol

 - if the node range intersects the input range:
- if it''s a leaf node, then add the range to your result list
- if it''s not a leaf node, then traverse down to the child nodes and repeat this process.

Debería ser O (logN)

Más detalles: el árbol binario estaría estructurado como una versión 1-d de un árbol cuádruple. Cada nodo tendría tres enteros (lo siento, dije dos arriba, pero ahora me doy cuenta que necesita tres), el más bajo representa el valor más bajo del rango más bajo que está debajo de este nodo, el más alto representa el valor más alto del rango más alto que está debajo de este nodo y el pivote. El hijo izquierdo abarcaría desde el nodo más bajo hasta su pivote. El niño correcto se extendería desde el pivote de este nodo hasta el más alto de este nodo. Si solo hay un rango que va desde "más bajo" hasta "más alto", no tendrías un pivote y esto sería una hoja. Lo ideal sería elegir los pivotes para cada nodo para mantener el árbol equilibrado.

Answer 2

Cuando tuve este problema, utilicé una matriz ordenada de rangos y una búsqueda binaria para buscar intersecciones. Este es (creo) el rendimiento O (log n), con un poco de sobrecarga para manejar rangos que se superponen.

La respuesta a su pregunta es, creo, derivable del código a continuación, pero no llega a la inserción. Presento el código completo para evitar confusiones por el contexto diferente. Necesitaba insertar un rango de puntos de código Unicode en una lista de rangos de puntos de código.

- EDITAR -

La adaptación del código a continuación para determinar intersecciones de rangos múltiples implica una búsqueda directa trivial desde el punto de inserción hasta que se encuentre un rango que ya no se cruza.

- FIN EDITAR -

La clase Range contiene:

final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}

Rango de inserción:

public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can''t overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}

Búsqueda binaria:

static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}

Answer 3

El enfoque estándar es usar un árbol de intervalos .

En ciencias de la computación, un árbol de intervalos es una estructura de datos de árbol para mantener intervalos. Específicamente, le permite a uno encontrar eficientemente todos los intervalos que se superponen con cualquier intervalo o punto dado. A menudo se utiliza para consultas en ventanas, por ejemplo, para encontrar todas las carreteras en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmentos.

La solución trivial es visitar cada intervalo y probar si se cruza con el punto o intervalo dado, que requiere O (n) tiempo, donde n es el número de intervalos en la colección. Dado que una consulta puede devolver todos los intervalos, por ejemplo, si la consulta es un intervalo grande que intersecta todos los intervalos en la colección, esto es asintóticamente óptimo; sin embargo, podemos hacerlo mejor si consideramos algoritmos sensibles a la salida, donde el tiempo de ejecución se expresa en términos de m, el número de intervalos producidos por la consulta. Los árboles de intervalo tienen un tiempo de consulta de O (log n + m) y un tiempo de creación inicial de O (n log n), mientras que limita el consumo de memoria a O (n). Después de la creación, los árboles de intervalo pueden ser dinámicos, lo que permite una inserción y eliminación eficiente de un intervalo en O (log n). Si los puntos finales de los intervalos están dentro de un pequeño rango entero (por ejemplo, en el rango [1, ..., O (n)]), existen estructuras de datos más rápidas [1] con tiempo de preproceso O (n) y tiempo de consulta O ( 1 + m) para informar m intervalos que contienen un punto de consulta determinado.

Answer 4

Esto depende de su problema exacto, en la pregunta vinculada, los rangos en los que distintas, ninguna parte común, y la búsqueda de rango podría abarcar múltiples rangos. Si su problema es el mismo, es realmente fácil: tome una matriz de rangos, ordénelos por sus valores más bajos (ya que no se superponen, esto también sería el mismo orden ordenado por sus valores superiores).

Ahora solo haga un binsearch para el valor inferior de su objetivo (o más pequeño si no es exacto) y otro para el valor superior del objetivo (o mayor si no es exacto). Los índices resultantes son los rangos que están cubiertos. Debe verificar si los rangos de los índices están incluidos o excluidos, pero son solo 2 comprobaciones. Complejidad general O (log n).

Answer 5

Parece que necesitas una clase que implemente la interfaz SortedSet. TreeSet es la implementación que se envía con la API principal.

Tenga un juego que contenga los rangos ordenados por el valor más bajo, y uno ordenado por el valor más alto.

Luego puede implementar el equivalente del algoritmo de base de datos usando los conjuntos en memoria.

En cuanto a si esto es realmente más rápido que O (n), no podría decirlo.

Answer 6

Si los rangos se superponen, y uno quiere recuperar todos los rangos que se superponen (o contienen) un rango objetivo dado, la mayoría de las soluciones anteriores no parecen funcionar.

Como algunos han señalado, si (en el peor de los casos) todos los rangos se cruzan con el rango objetivo (por ejemplo, si el rango objetivo es {0..MAXINT} o similar) entonces, por supuesto, toma O (n) para regresar los n rangos.

Pero, ¿no es el caso interesante y típico / promedio, donde solo un% muy pequeño de los n rangos totales se cruzan con el rango objetivo? Llame al número que se cruza con "m" - en ese caso, es posible que pueda hacerlo tan bien como O (m). Y si n = 10 ^ 9 ym = 10, esa es una diferencia decisiva.

Considere el caso simple de un documento de texto que tiene varias regiones marcadas para su "tipo"; quizás quiera encontrar todas las unidades marcadas que contienen o se cruzan con un rango contiguo de texto dado (por ejemplo, un párrafo). En HTML, XML o similares, estos solo pueden ser antepasados ​​de los nodos de texto que contienen al menos algunos caracteres del rango objetivo. En representaciones típicas con punteros padres en cada nodo, eso es O (m) - mucho mejor que O (n), especialmente porque m es (para rangos objetivos cortos o síncronos) simplemente la profundidad de anidamiento del árbol, que tiende a ser incluso menor que En n (n) porque los documentos XML grandes en la práctica se vuelven más complicados y no más profundos.

El caso interesante es más difícil: ¿qué sucede si sus "elementos" no forman un árbol como en XML, pero pueden superponerse como en MECS, CLIX, LMNL y algunos otros sistemas? Aún desea encontrar todas las regiones / "elementos" que se superponen a su objetivo, pero no se organizan tan fácilmente.

Por otro lado, debería poder hacerlo muy bien porque los rangos marcados en muchas aplicaciones son con frecuencia pequeños: hay muchas más palabras, oraciones y párrafos en un libro que capítulos. Entonces, aunque puede haber un gran número de rangos que comienzan antes del objetivo y un gran número que termina después de él, la intersección será muy pequeña en promedio.

Creo que eso es lo que estaba haciendo la persona que pregunta original, y me temo que no vi una respuesta que aborde ese problema. Si no es de lo que se trataba la pregunta original, me gustaría plantearla como una nueva pregunta.

Answer 7

Editar: Parece que esta solución es más o menos un árbol de intervalos . Se puede encontrar una implementación más completa de un Árbol de Intervalos here .

class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};

Prep O (n log n):

1. Crea la lista de rangos
2. Elija los puntos de pivote (posiblemente mediante el uso de una lista ordenada de las fechas de finalización).
3. Construye tu árbol

Buscar:

1. Utilice la búsqueda binaria para encontrar el primer pivote que sea> = TestRange.End

2. Atraviesa el árbol hasta el pivote> TestRange.Start

   2a. Agrega las hojas a tu resultado.

Ejemplo:

Rangos:

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 4
• 2 - 4
• 0 - 5
• 4 - 5
• 2 - 6
• 3 - 7

Árbol:

 4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2

Answer 8

Rangos no superpuestos:

Prep O (n log n):

1. Haz una matriz / vector de los rangos.
2. Ordenar el vector por el final del rango (romper los vínculos ordenando por el inicio del rango)

Buscar:

1. Utilice la búsqueda binaria para encontrar el primer rango con un valor final de> = TestRange.Start

2. Iterador comenzando en la búsqueda binaria hasta que encuentre un Inicio> Rango de prueba. Fin:

   2a. Si el rango es el rango actual dentro del TestRange, agréguelo a su resultado.

Answer 9

Rangos superpuestos:

Prep O (n log n):

1. Haz una matriz / vector de los rangos.
2. Ordenar el vector por el final del rango (romper los vínculos ordenando por el inicio del rango)

3. Haz un segundo vector de ints. Esto representa el punto en el que puede dejar de buscar.

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
   stop[i] = min(Ranges[i].start, stop[i+1]);
   }

Buscar:

1. Utilice la búsqueda binaria para encontrar el primer rango con un valor final de> = TestRange.Start

2. Iterador comenzando en la búsqueda binaria hasta detener [i]> TestRange.End:

   2a. Si el rango es el rango actual dentro del TestRange, agréguelo a su resultado.